CS/Algorithm

다이나믹프로그래밍(Dynamic Programming)

📔 다이나믹프로그래밍(Dynamic Programming)이란 하나의 문제는 단 한 번만 푸는 방법! 다이나믹프로그래밍 (이하 DP) 작은 문제를 해결하여 큰 문제를 해결하는 분할정복과 유사하다고 생각할 수 있지만, 분할정복의 경우 한번 풀었던 문제를 다시 푸는 비효율적인 단점을 가지고 있다. (일부 경우 제외 (병합정렬)) 분할정복과 DP의 차이를 보여주는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열: 바로 앞과 앞앞 두 칸의 숫자의 합을 구해서 나타내는 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 분할정복을 이용한다면 이미 구한 숫자들을 다시 계산하는 단점이 있다. 위의 사진을 보면 13을 구하는게 2번, 12 3번, 11 3번 계산하는 것을 볼 수 있다. 이런 문제를 ..

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..

서로소 집합(Disjoint-set)

📔 서로소 집합(Disjoint-set) 이란 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들( 교집합이 없는 상태 ) 집합에 속한 하나의 특정 원소를 통해 각각의 집합들을 구분 ( 이를 대표자라고 함 ) 상호 배타 집합을 표현하는 방법 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표로 한다 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 트리 하나의 집합을 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 make_set(x) find_set(x) union(x,y) 📔 서로소 집합(Disjoint-set) 구현 def make_set(x): p[x] = x def find_set(x):..

깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란 깊이를 우선으로 하여 탐색을 수행하는 알고리즘 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법! ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것! 경로를 찾고 싶을 떄 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 ) 스택으로 사용시 이웃 중 가장 뒤에 있는 것부터, 재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다. 📔 깊이 우선 탐색(DFS) 구현 def dfs(c): print(c, end=' ') for neighbor in adj[c]: # c의 이웃 중 if visited[neighbor] == 0: # 방문 아직 안한 친구이면 visited[neig..

너비 우선 탐색(Breath First Search, BFS)

📔 너비 우선 탐색(BFS) 이란 너비를 우선으로 하여 탐색을 수행하는 알고리즘 최단경로(최단길이)를 찾을 때 주로 사용한다. 큐와 그래프로 해결한다. (파이썬에서는 데크(deque)를 쓰면 속도가 빠름) 📔 너비 우선 탐색(BFS) 구현 from collections import deque # 인접리스트 # 노드: 1,2,3,4,5,6,7 n = 7 adj = {x: [] for x in range(1, n + 1)} edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ] # 무방향 그래프이므로 반대쪽도 성립 for edge in edges: s, e = edge adj[s].append(e) adj[e].append(s) print(adj) # bfs..

계수 정렬(counting sort)

📔 계수 정렬(counting sort) 이란 작은 범위 조건이 있는 경우에 한해서 빠른 알고리즘 시간복잡도: O(N), 최악의 경우 O(N^2) 크기를 기준으로 갯수만 세주면 된다. 비교정렬 X 📔 계수 정렬(counting sort) 구현 N = 5 # 5 이하인 수들을 정렬해라 numbers = [1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 3, 3, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5] print(f'정렬 전: {numbers}') count_list = [0] * (N + 1) for number in numbers: count_li..