[C_C++]이론 공부/알고리즘

[알고리즘 공부] 그리디(Greedy) 알고리즘

그리디 알고리즘(Greedy Algorithm) - 당장 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘 - 가장 단순한 형태이며, 난이도가 매우 낮은 알고리즘 중 하나. - 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있음. - 특정한 상황에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있음! 가장 대표적인 예제 : 거스름돈 문제 - 무조건 더 큰 화폐 단위부터 거슬러 주는 게 최적의 해 #include using namespace std; int main() { int n, result = 0; scanf("%d", &n); result += n/500; n %= 500; result += n/100; n %= 100; result += n/50;..

[알고리즘 공부] 플로이드 와샬(Floyd Warshall) 알고리즘

다익스트라 알고리즘 - 한 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 (1 → n의 최단경로) - 가장 적은 비용을 하나씩 선택해서, 그 적은 비용을 갖는 노드와 인접한 노드로 가는 비용을 계산해 알고리즘을 수행 - 가장 적은 비용을 가지는 노드를 하나씩 꺼내서, 그 노드를 거쳐가는 비용을 확인 플로이드 와샬 알고리즘 - '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 (n → n의 최단경로) - 거쳐가는 정점을 기준으로 최단거리를 구함 - 거쳐가는 노드를 하나씩 설정해서 확인 : 거쳐가는 정점을 반복문의 중심에 있게 함. 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열 형태로 출력하면 0 5 ∞ 8 7 0 9 ∞ 2 ∞ 0 4 ∞ ∞ 3 0 => 현재..

[알고리즘 공부] 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘 - DP(다이나믹 프로그래밍)을 활용한 대표적인 최단경로 탐색 알고리즘 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 DP로 분류 가능 (그리디로 분류되기도 함) 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 - 현재까지 알고 있던 최단경로를 계속해서 갱신 - 음의 간선을 포함할 수 없음. - 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나 (∵ 현실세계에서도 음의 간선이 존재하지 않으므로) 작동 과정 1. 출발 노드 설정 2. 출발 노드 기준으로 각 노드의 최소 비용 저장 3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 4. 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려해 최소 비용 갱신 5. 3~4 반복..

[알고리즘 공부] 에라토스테네스의 체

에라토스테네스의 체 - 가장 대표적인 소수(Prime Number) 판별 알고리즘 - 소수를 대량으로 빠르고 정확하게 구하는 방법 들어가기 전) 소수 구하는 간단한 알고리즘 모든 경우의 수를 다 돌면서 약수 여부를 확인하면 시간복잡도 O(N) => 비효율적 // O(N) #include bool isPrimeNumber(int x) { for (int i = 2; i < x; i++) if (x % i == 0) return false; return true; } int main() { printf("%d", isPrimeNumber(97)); return 0; } 약수들끼리 어느 수를 기점으로 대칭을 이룸. 그 기점이 되는 수가 판별하려는 수의 제곱근임. 특정한 숫자의 제곱근까지만 약수의 여부를 검증하..

[알고리즘 공부] 다이나믹 프로그래밍(DP, 동적 계획법)

다이나믹 프로그래밍(Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘 컴퓨터적인 사고력을 물어보기 적합해서 자주 출제되므로 확실하게 알아야 함. DP, 동적 계획법이라고도 함. 일반적으로 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 있음. (정렬과 같은 몇몇 요소에 대해서는 동일 문제 다시 풀지 않음. 그래서 병합이나 퀵 정렬은 매우 빠름). 특히 피보나치 수열 같은 경우에는 단순 분할 정복으로 풀면 심각한 비효율성을 낳음. (피보나치 수열 점화식: D[i] = D[i-1] + D[i-2]) 재귀로 풀게 되면 동일한 데이터를 반복적으로 불필요하게 계산해야함. 이미 해결한 문제를 다시 반복적으로 해결하기 때문에 비효율적. DP는 다음의 가정 하에 사용 가능 큰 문제..

[알고리즘 공부] 이진트리의 구현과 순회 알고리즘

이진트리(Binary Tree) 가장 많이 사용되는 비선형 자료구조 트리 자료구조를 활용한 대표적인 예시 데이터의 탐색 속도 증진을 위해 사용하는 구조 트리를 제대로 구현하기 위해서는 포인터를 사용해야 함. 포인터를 사용하면 특정한 root에서 자식 노드로 접근하는게 훨씬 간단하게 이루어질 수 있음. 힙 정렬을 구현할 때는 완전 이진 트리를 사용했기 때문에 배열로 표현할 수 있었지만, 완전 이진 트리가 아닌 이진 트리는 배열로 표현하기 어렵기 때문(∵ 데이터 낭비. 오른쪽으로만 뻗는 트리의 인덱스를 생각해 볼 것). 이진 트리에서 데이터를 탐색하는 법 3가지 전위 순회(Preorder Traversal) ① 먼저 자기 자신을 처리 ② 왼쪽 자식 방문 ③ 오른쪽 자식 방문 중위 순회(Inorder Trav..

[알고리즘 공부] 합집합 찾기(Union-Find), 크루스칼 알고리즘

유니온 파인드(Union-Find, 합집합 찾기) 대표적인 그래프 알고리즘. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부름. 여러개의 노드가 존재할 때 2개의 노드를 선택해, 현재 이 노드들이 서로 같은 그래프에 속하는지 판별. 나중에 strongly connected component, 크루스칼(Kruskal) 알고리즘 등과 같은 고급 알고리즘에서도 적용되는 원리로 활용도가 높으므로 잘 공부하고 넘어가는 것이 좋음. - 합침(Union) : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침 - Find 알고리즘 : 2개 노드의 부모 노드를 확인해 현재 같은 집합에 속하는지 확인하는 알고리즘 자식 1 2 3 4 5 6 부모 1 2 3 4 5 6 맨 처음에는 집합 자체가 각각 다 자기 자신..

[알고리즘 공부] BFS & DFS (C++)

들어가기 전) 스택 & 큐 스택과 큐는 컴퓨터공학에서 가장 기본이 되는 자료구조. #include #include 로 C++ STL 라이브러리 사용 가능 stack은 s.top(), queue는 q.front() 로 가장 위/앞의 값을 가져올 수 있다. BFS(Breadth First Searct, 너비 우선 탐색) 탐색할 때 너비를 우선으로 해서 탐색 수행하는 탐색 알고리즘 ‘최단경로’를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용. 준비물은 큐(Queue) 맹목적인 탐색을 하고자 할 때 사용하는 탐색 기법. 맨 처음에는 시작 노드를 큐에 삽입하면서 시작. 시작 노드는 방문 처리 후, 다음의 간단한 알고리즘에 따라 작동. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않..