본문 바로가기

📚전공

 (31)
[자료구조] 그래프 그래프란?- 노드(node)와 노드들을 연결하는 간선(edge)을 하나로 모아 놓은 자료구조- ex) 트리: 사이클이 허용되지 않는 그래프그래프 관련 용어 정리정점(vertex): 노드를 정점이라고 표현하기도 한다.인접 정점(adjacent vertex): 간선으로 직접 연결된 정점 혹은 노드차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 위 그래프에서 A의 차수는 3이다.진출차수(out-degree)/진입차수(in-degree) : 방향그래프에서 사용되는 용어진입차수 는 외부 노드에서 들어오는 간선의 수진출 차수 는 한 노드에서 외부로 향하는 간선의 수,그래프의 특징그래프의 순회는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)으로 할 수 있다.그래프에는 루트 노드, 부모-..
[알고리즘] 위상 정렬 (Topological Sort) 위상- 항목 간의 상대적인 위치나 순서를 의미 (컴퓨터 과학에서의 특별한 의미)- 즉, 어떤 노드(작업, 과목 등)가 다른 노드보다 먼저 와야 하는지, 또는 먼저 수행되어야 하는지에 대한 순서의 구조(structure)를 뜻함.위상 정렬- 방향 그래프에서 노드들 간의 선후 관계(의존성)를 고려해 순서를 정렬하는 것- DAG(Directed Acyclic Graph)에만 적용이 가능하다. (사이클이 발생하는 경우 위상 정렬을 수행할 수 없다)위상 정렬 알고리즘 특징1. 현재 그래프는 위상 정렬이 가능하지2. 위상 정렬이 가능하다면 그 결과는 무엇인지위상 정렬 수행 알고리즘 설명1. 진입차수가 0인 정점을 큐에 삽입합니다.2. 큐에서 원소를 꺼내 열결된 모든 간선을 제거합니다.3. 간선 제거 이후에 진입차수..
[알고리즘] 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..

티스토리툴바