본문 바로가기

📚전공/알고리즘

 (19)
[알고리즘] Disjoint Set (서로소 집합) - Union, Find Disjoint Set (서로소 집합) 두 개 이상의 집합을 형성할 때, 교집합이 공집합이 되도록 구성하는 자료구조 ex) A={1, 2, 3}과 B={4, 5, 6}은 서로소 집합 ex) C={1, 3, 5}과 D={3, 5, 7}은 서로소 집합이 아니다. Disjoint Set은 대개 Tree로 구성한다. 항상 Parent-Child관계와 Root Node가 존재한다. Disjoint Set 연산 Disjoint Set은 두 가지 연산을 지원한다. Union(x, y) x가 속하고 있는 집합과 y가 속하고 있는 집합을 합친다. 이때 x와 y가 같은 집합 내에 있다면 합치지 않는다. Find(x) x가 속하고 있는 집합을 구한다. Python 코드 parent = [p for p in range(v+1..
[알고리즘] 에라토스테네스의 체 (소수 찾기) 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견했다고 한다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수..
[알고리즘] 완전탐색 완전탐색 알고리즘은 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 갖고 있어 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 하면 적절하다. 완전탐색 알고리즘을 활용하는 방법 완전탐색 알고리즘으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다. 1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다. 2) 가능한 모든 방법을 다 고려한다. 3) 실제 답을 구할 수 있는지 적용한다. 여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다. ① Brute Force 기..
[알고리즘] 플로이드 와샬 ( Floyd-warshall ) 플로이드 와샬 플로이드 와샬은 최단경로를 DP(Dynamic Programming)형태의 문제로 정의하고 풀어낸다. 모든 정점 쌍의 경로에 대해 기존 경로(i -> … -> j)가 최단 경로 인지, 어느 한 정점을 경유해서 가는 경로(i -> … -> k -> … -> j)가 최단 경로인지 비교한다. 이것을 경유지를 1 ~ N번 정점으로 놓고 계산한다. 계산이 완료되면 어느 한 경로가 어디를 경유하든 최단거리임이 만족된다. 이 알고리즘이 왜 DP인가? -> 쉽게 설명하면 [기존 경로] VS [다른 기존 경로]의 재조합이다. 기존 경로를 사용해서 새로운 경로를 만들기 때문에 DP이다. ShortestPath(i, j, k) shortestPath(i, j, k)라는 문제는 i번 정점에서 j번 정점까지, 1..
[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) 출발점에서 모든 점으로 가는 최소거리를 각각 구하고 싶을 때 사용한다. 음수 가중치는 사용이 불가능하다. 음수 가중치가 없기 때문에 최단 경로가 확정된 정점들과 연결된 정점 중 출발점에서 가장 거리가 짧은 정점은 최단거리임을 확장할 수 있다. 거리가 3인 정점이, 3보다 더 긴 경로를 타고 더 빠르게 갈 수 없는 것처럼 말이다. 알고리즘 1. 출발점으로부터 가장 거리가 짧은 정점 X를 구한다. 2. 정점 X까지의 거리를 정점 X의 최단 거리로 확정한다. 3. 정점 X를 경유하는 경로와 비교해, 연결된 정점들의 거리를 갱신한다. 4. 1~3을 반복한다. 시간 복잡도 1번 과정을 선형 탐색을 이용하게 되면 O(V^2), V는 노드의 개수 -> 방문하지 않은 노드 중에서 최단 거리..
[알고리즘] binary search(이진 탐색/이분 탐색) 정렬된 list에서 query item을 찾아서 위치를 return한다. 1. list를 오름차순으로 정렬한다. 2. left = 0, right = n-1부터 시작한다. 3. middle = (start + end) / 2라고 두고 list[middle]과 query를 비교한다. 1) query list[middle]이면 left를 middle+1로 둔다. 이때 query가 list에 없으면 무한루프를 돌 수가 있다. 따라서 left right면 없다고 return한다.) 이진 탐색 소스코드: 재귀적 구현 (Python) def binary_se..
[알고리즘] [그래프 탐색] DFS(깊이 우선 탐색) DFS는 Depth First Search로 깊이 우선 탐색이다.현재 정점에서 갈 수 있는 정점까지 계속 탐색하는 방법이다.탐색한 정점은 다시 탐색하지 않는다.BFS에 비해 간단하나, 단순 검색 속도 자체는 BFS에 비해 느리다.모든 노드들을 탐색해야 하는 경우에 많이 사용한다.인접 행렬로 구현할 경우에는 O(N^2)의 시간복잡도를 갖고 인접 리스트로 구현하면 O(N+E)의 시간복잡도를 갖는다. 재귀함수나 스택을 사용해 구현한다.1. 스택을 사용하여 구현1) 시작점을 스택에 넣는다.2) 반복문 안에 들어간다.3) 가장 위에 있는 노드를 변수에 저장하고 pop한다.4) 현재 노드가 방문 된 노드라면 visit배열에 체크한다.5) 현재 노드와 연결된 노드 중에서 방문하지 않은 노드를 스택에 push한다.6)..
[알고리즘] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누고 그 작은 부분 문제들이 반복되는 것을 이용하여 풀어가는 방법이다. 모든 작은 문제들을 단 한번만 풀어야 하며, 그 결과를 어딘가 기록해 둠으로써 재사용한다. 부분 문제를 푸는 순서에 따라서 Top-Down과 Bottom-up으로 나뉜다. 메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 ㅁ누제들의 결과값을 저장하는 것을 의미한다. 메모이제이션을 통해 이미 결과값이 기록되는 특정 문제가 반복될 때, 불필요한 계산은 패스하고 기록되어 있는 값만 불러오면 아주 빠르게 해결할 수 있다.

티스토리툴바