흰 스타렉스에서 내가 내리지

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def preorder(self, res=[]): res.append(self.val) if self.left is not None: self.left.preorder(res) if self..

# 배낭 문제 - n개의 물건과 배낭이 있고, 각 물건에 대해 가치와 무게가 알려져 있다. - 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치는? - 배낭문제는 물건을 쪼갤 수 있는 Fraction Knapsack Problem과 물건을 쪼갤 수 없는 0-1 KnapSack Problem이 있다. - 배낭문제는 대표적인 DP 문제이다. https://www.acmicpc.net/problem/12865 N, K = map(int, input().split()) weight = [0] value = [0] for _ in range(N): w, v = map(int, input().split()) weight.append(w) value.append(v) t = [[0]*(K+1) f..

x의 n-거듭제곱인 x^n 을 계산하기 # 1. 억지기법 def slow_power(x, n): result = 1.0 for i in range(n): result *= x return result 3행의 반복문에 의해 n에 비례하는 시간이 거릴고, 따라서 시간복잡도가 O(n)이다. # 2. 축소 정복을 이용한 거듭제곱 1번 방법대로 x^10을 구하려면, 총 9번의 곱셈이 필요하다. 하지만 곱셈 한 번으로 x^2를 구하고, 이를 4번 곱하면, 총 5번의 곱셈으로 x^10을 구할 수 있다. 더 복잡하게 한다면, (x^2) * ( (x^2)^2 )^2 와 같은 방식으로, 총 4번의 곱셈으로 x^10을 구할 수 있다. def power(x, n): if n == 0: return 1 # 종료 조건 elif ..

목차 서로소 집합 :: union-find 신장 트리 :: Spanning Tree 크루스칼 알고리즘 프림 알고리즘 위상 정렬 :: Topology Sort # 1. 서로소 집합 :: Disjoint Sets "서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조" - 서로소 집합을 union-find 자료구조 라고 부르기도 한다. - union과 find, 이 2개의 연산으로 조작할 수 있다. 1. union : - 2개의 집합을 하나의 집합으로 합치는 연산이다. 2. find : - 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 스택과 큐 자료구조가 push와 pop 연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 union과 find 연산으로 구성된다. - 트리 자..

외판원 문제 (Traveling Salesman Problem, TSP) TSP문제는 해밀토니안 사이클을 이용해 다음과 같이 정의된다. 가중치 그래프 G = (V, E)가 주어졌다. G에서 모든 가능한 해밀토니안 사이클 중에서 경로의 합이 최소인 사이크르이 경로의 합을 구하라. 완전 탐색을 이용하면 항상 확실한 해를 구할 수 있다. 임의의 한 점을 출발점으로 잡고 아직 가보지 않은 모든 이웃 정점으로 계속 이동하면서 검사하면 된다. 그래프가 N개의 정점을 갖는 완전그래프라면 모든 해밀토니안 사이클은 (N-1)! 개가 된다. 임의의 도시를 출발점으로 잡는다. 이 도시를 시작으로 하여 (N-1)!가지의 순열 객체를 생성한다. 모든 순열 객체에서 경로의 합을 구하고, 경로의 합이 최소인 순열 객체와 경로 합을..

탐욕 알고리즘 (Greedy Algorithm) 매 단계마다 항상 최선일 것 같은 선택을 하면 전체적으로도 최선의 선택을 하게 된다는 알고리즘이다. 탐욕 알고리즘의 두 가지 조건 최적 부분 구조 (optimal substructure) : 어떤 전체 문제에 대한 최적해는 부분 문제(subproblem)에 대한 최적해를 포함하고 있습니다. 탐욕 선택 특성 (greedy choice property) : 부분적으로 최적의 선택을 계속하면 전역적으로 최적해에 도달할 수 있다.

에라토스테네스가 발견한 소수를 찾는 방법이다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. import math n = 1000 arr = [True for i in range(n+1..

재귀 함수를 이용한 이진 탐색 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return binary_search(arr, target, start, mid -1) else: return binary_search(arr, target, mid + 1, end) 반복문을 이용한 이진 탐색 def binary_search(arr, target, start, end): while start target: end = mid - 1 else: start = mid + 1 return N..

arr = [1, 2, 3] def dfs(arr, sol, visited): # Base Case if len(arr) == len(sol): print(sol) return for i in range(len(arr)): if not visited[i]:# 노드에서 같은 원소가 중복되는 경우 - 백트래킹 visited[i] = True sol.append(arr[i]) dfs(arr, sol, visited) sol.pop()# 노드에서 하나의 순열을 완성한 경우 - 백트래킹 visited[i] = False dfs(arr, [], [False]*len(arr)) # 실행 결과 # [1, 2, 3] # [1, 3, 2] # [2, 1, 3] # [2, 3, 1] # [3, 1, 2] # [3, 2, 1..

arr를 deepcopy하지 않고 dfs한 결과와, dfs함수 첫줄에 arr를 deepcopy한 결과 비교 import copy arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] def dfs(arr, i): if i>=10: return print(f'{i} : {arr}', end = ' ') if arr[i] == 0: print(f'arr[{i}] is already 0.') else: print() arr[i] = 0 dfs(arr, i+2) dfs(arr, i+3) dfs(arr, 2) import copy arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] def dfs(arr, i): arr = copy.deepcopy(arr) if i>=10: return ..