코딩테스트 준비 (48) 썸네일형 리스트형 전위 순회, 중위 순회, 후위 순회 전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순 중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식 후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리 재귀 + dp + 조합 공식 서로소 집합 알고리즘 find_parent(x) 메소드가 최상단 부모 노드를 바로 재귀적으로 찾아 반환해 준다. 이를 이용하는 union_parent(x, y) 메소드는 두 노드를 비교하여 작은 노드를 큰 노드의 부모 노드로 연결시킨다. 해당 문제는 연결 요소의 개수를 세는 문제이므로 union_parent(x, y)을 통해 연결을 끝낸 뒤 각 노드의 부모노드를 set 자료형 안에 담아서 해결했다. itertools의 combinations를 이용한 부분수열 합 문제 combinations(arr, num)는 arr에 조합을 뽑을 리스트를 넣어주고, num에 조합의 크기를 적어주면 된다. 그 자체로는 와 같이 객체를 반환하므로 list() 안에 넣어서 리스트 형태로 사용해야 한다. 큐 자료구조 문제 백준 요세푸스 문제 DP - 중 1. 백준 - 카드 구매하기 카드 개수에 따른 최대가격을 담는 dp 리스트를 만들고, 각 카트의 가격을 저장하는 리스트를 만든다. dp[1] = p[1]이 되고, dp[2] = dp[1] + p[1] 혹은 dp[0] + p[2]가 된다. 이중 반복문을 통해 모든 경우를 확인하며 가장 큰 값을 dp[i]에 넣는다. 2. 백준 동전 - 1 3. 백준 - 이동하기 4. 백준 - 쉬운 계단 수 - 2차원 DP 각 자리수에서 맨 뒤에 올수 있는 숫자의 개수(0~9) 0 1 2 3 4 5 6 7 8 9 자리수(1) 0 1 1 1 1 1 1 1 1 1 자리수(2) 1 1 2 2 2 2 2 2 2 1 자리수(3) 1 3 3 4 4 4 4 4 3 2 위의 규칙을 살펴보자. 자리수가 1일때, 각 숫자들이 맨뒷자리에 올 수.. 가장 긴 증가하는 부분 수열 (LIS) 1 단계는 다이나믹 프로그래밍만 사용하면 됨. - 자기보다 작은 인덱스이며 자신의 값보다 작은 값들 중에서 dp 값이 가장 큰 놈에게 1 더해준 값이 자신의 dp 값이 된다. 백준 N과 M (1) - 백트래킹 - dfs N, M = 4, 2인 경우 스택을 이용한 백트래킹 - dfs 깊이우선탐색 처음에 s = []인 상태로 반복문으로 들어감. s = [1]인 채로 f() 재귀함수로 들어감. 반복문에서 s = [1, 2]가 된 채로 다시 f() 재귀함수로 들어감. len(s) == 2이므로 출력되고 리턴. 2가 pop으로 나오고 그다음 s = [1, 3]이 재귀함수로 들어감 이전 1 2 3 4 5 6 다음
