Simple Explain

#1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 다음과 같이 사고했다.테스트 케이스의 모든 경우의 수를 작성해본 결과, 작은 수의 카드 집합끼리 합치는게 최소값을 도출하는 방법이란걸 알 수 있었다.  음 좀 어려웠다. 처음 사고대로 구현했는데 시간초과가 났다. 틀린코드from collections import dequen = int(input())nums = [int(input()) for _ in range(n)]nums.sort()nums = deque(nums)answer = 0while len(nums) >= 2: # print(answer, nums) tmp = nums.popleft() + nums.popleft() answer += ..

#1987 알파벳 (https://www.acmicpc.net/problem/1987) 과거 소마를 준비하던 시절 포기했던 문제였다.    틀린 코드r, c = map(int, input().split())graph = [[x for x in input()] for _ in range(r)]alpha = set(graph[0][0])dr = [1, -1, 0, 0]dc = [0, 0, 1, -1]answer = 0def solve(x,y, length): global answer answer = max(answer, length) for i in range(4): nr = x + dr[i] nc = y + dc[i] if 0  무엇이 문제였을까?? 아..

#1517 버블 소트 https://www.acmicpc.net/problem/1517  버블정렬에서 발생하는 swap의 횟수를 구하는 알고리즘이다. 개념을 간단히 설명하면 버블 정렬은, 옆 인덱스와 크기를 비교해서 값의 위치를 찾아가는 형태의 정렬방법이다.따라서, 옆 인덱스와 값을 교환하는 swap이라는 행위가 발생한다.https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html [알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development BlogStep by step goes a long way.gmlwjd9405.github.io반만 합병정렬은 분할정복의 접근법으로 정렬을 진행하는 방법이다.https://gmlwj..

#11444 피보나치 수 6 https://www.acmicpc.net/problem/11444 제일 처음 접근했던 방식은, DP를 재귀로 돌리는 형태였다. import syssys.setrecursionlimit(10000)n = int(input())division = 1000000007dp = [0, 1]def find_fibo(n): # print(n) if n 하지만 재귀의 깊이가 너무 깊어졌다. 거의 반 포기상태로 참고자료를 봤고,점화식을 훨씬 더 함축적으로 개선해야함을 느꼈다.  최종적으로 파악한 점화식은 다음과 같다.*출처https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-11444-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%..

#11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660  역시 반복문으로 막 푸니까 시간초과가 난다. 과거에 DP를 풀었던 기억을 되내이며 고민했다.2차원으로 DP를 진행하면 된다.  import sysinput = sys.stdin.readlinen, m = map(int, input().split())maps = []dp = []# make dp and store originfor i in range(n): nums = [int(x) for x in input().split()] # store origin maps.append(nums) # make dp tmp = [] if i == 0: idx_0 = nums..

#1238 파티 https://www.acmicpc.net/problem/1238 처음 dfs, bfs를 고민하다가 다익스트라라는 사실을 깨달았다. import heapq, sysINF = sys.maxsize n, m, x = map(int, input().split())maps = [[] for __ in range(n+1)]for _ in range(m): start, dest, weight = map(int, input().split()) # 단방향 도로 maps[start].append([weight, dest])# 다익스트라 돌리기# 전체 -> x 방향,# x -> 전체 방향def dijkstra(n, start): heap = [] heapq.heappush(..

#1753 최단경로 https://www.acmicpc.net/problem/1753 import sysimport heapqINF = sys.maxsizen, e = map(int, input().split())target = int(input())# 0번 인덱스는 사용하지 않음. 1~nmaps = [[] for _ in range(n + 1)]# visited = [[False] * (n + 1) for _ in range(n + 1)]for i in range(e): start, end, weight = map(int, input().split()) # 방향그래프 maps[start].append((end, weight))q = []heapq.heappush(q, (0, target..

#11403 경로찾기 https://www.acmicpc.net/problem/11403  너무 어렵게 생각했다.bfs를 여러번 돌리면 되는데,뭔가 한 번의 함수 실행으로 완벽하게 해결하고 싶어서 더 고민을 했다.  하하하하하하 n = int(input())links = [[int(x) for x in input().split()] for __ in range(n)]# bfsanswer = [[0 for _ in range(n)] for __ in range(n)]def bfs(start): # print(start) q = [start] visited = [0 for _ in range(n)] while q: prev = q.pop(0) for i in r..

#30804 과일탕후루 https://www.acmicpc.net/problem/30804 투포인터가 처음이라서 자료를 참고하면서 했다. 이름만 들었을 때 간단한 개념일 것 같아서 별도로 학습하지 않았지만생각보다 고려해야할 점이 많았다.  중요한 점은, right는 순차적으로 증가하되 left는 특정 조건을 만족할 때 갱신해야한다는 점이다.물론, 모든 문제에서 이럴 것 같지는 않다.  투포인터의 장점은, O(n)의 시간복잡도로 해결할 수 있다는 점이다.되게 좋은 솔루션을 배운 기분이다.  import sysinput = sys.stdin.readlinen = int(input())fruits = [int(x) for x in input().split()]# 투 포인터 알고리즘# left,right 포인터..

#21736 헌내기는 친구가 필요해 (https://www.acmicpc.net/problem/21736)  유난히 바쁜 날이라만만해보이는 문제로 (class 4 중) 빠르게 풀었다. n, m = map(int, input().split())campus = []visited = []q = []for i in range(n): row = [x for x in input()] v = [False for _ in range(m)] for j in range(m): # O는 빈 공간, X는 벽, I는 도연이, P는 사람이다 if row[j] == "I": q.append([i, j]) v[j] = True elif ro..