개발윗미

그리디 알고리즘은 매 선택에서 당장 눈 앞에 보이는 최적인 답을 선택하도록 하는 알고리즘이다. 대표적인 예제로는 거스름 돈 문제가 있다. 예를들어, 거스름 돈 1260원을 내주어야할 때 10원짜리 동전을 126개 내어주는 것보다는 500원짜리 동전 2개, 100원짜리 동전 2개, 50원짜리 동전 1개, 10원짜리 동전 1개로 총 6개의 동전을 내어주는 것이 더욱 편리하다. 그러므로 그리디 알고리즘은 무조건 큰 경우 혹은 무조건 작은 경우대로 문제에 접근하여 수행된다. [예제] #include int main() { int input, result = 0; scanf("%d", &input); result += input / 500; input %= 500; result += input / 100; inp..

문자열 매칭 알고리즘은 특정한 글이 존재할 때 그 글 내에서 하나의 문자열을 찾는 알고리즘이다. 특정한 글 H e l l o 위와 같이 특정한 글이 Hello 로 존재하고 문자열 ll을 찾는다고 가정할 때 (1) 먼저 찾을 문자열인 ll을 가장 앞에 위치시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l (2) 매칭이 이루어지지 않았으므로 다음 한 칸 이동시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l (3) 매칭이 이루어지지 않았으므로 다음 한 칸 더 이동시켜 해당 문자열이 동일한지 확인한다. 특정한 글 H e l l o 찾을 문자열 l l => 해당 문자열에 대하여 매칭이 이루어진 것을 확인할 수 있다. [예제] #includ..

이분 매칭은 집단이 존재할 때 A 집단이 B 집단을 선택하는 방법이다. 아래와 같이 숫자 집단과 알파벳 집단이 있다고 가정하고, 1번은 알파벳 A, B, C 를 선택하고 2번은 알파벳 A를, 3번은 알파벳 C를 선택했다고 할 때 이분 매칭은 모든 숫자가 각각의 알파벳을 선택하여 가장 많이 연결되는 경우를 탐색할 수 있도록 한다. (1) 먼저 알파벳 A가 아무 번호에도 연결되어 있지 않기 때문에 1번이 알파벳 A를 선택한다. (2) 2번이 A를 선택하는데 A는 1번에 연결되어 있기 때문에 A를 점유하고 있는 1번부터 다시 출발하여 A를 제외하고 다른 곳에 연결될 수 없는지 확인한다. (3) 1번은 알파벳 B에 연결될 수 있기 때문에 B에 연결하고 2번은 A에 연결한다. (4) 3번이 B를 선택하는데 B는 ..

위상 정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 주의할 점은 위상 정렬은 사이클이 발생하지 않는 방향 그래프 즉, DAG(Directed Acyclic Graph)에만 수행이 가능하다. 왜냐하면 위상 정렬은 기본적으로 시작점이 존재해야 하는데 사이클 그래프에서는 시작점부터 찾을 수 없기 때문이다. 위상 정렬을 수행하는 과정은 아래와 같다. 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2 1 여기서 진입차수는 해당 정점에 들어오는 간선의 수이다. 즉, 정점6은 정점4와 정점5에서 간선이 들어오기 때문에 진입차수가 2이다. 또한, 정점1은 들어오는 간선이 없기 때문에 진입차수는 0이다. (1) 진입차수가 0인 정점1을 큐에 삽입한다..

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 2차원 배열로 나타내면 아래와 같다. 0 5 INF(무한) 8 7 0 9 INF(무한) 2 INF(무한) 0 4 INF(무한) INF(무한) 3 0 위 표는 현재까지 계산된 최소 비용이며, 이러한 2차원 배열을 반복적으로 갱신하여 모든 최소 비용을 구하는 과정은 아래와 같다. (1) 노드 1을 거쳐가는 경우 [ 2->3 ] 노드 1을 거쳐가야 하기 때문에 1을 포함하지 않은 경우들만 계산해주면 된다. 0 5 INF(무한) 8 7 0 [ 2->3 ] [ 2->4 ] 2 [ 3->2 ] 0 [ 3->4 ] INF..

에라토스테네스의 체는 소수를 찾는 방법이다. 여기서 소수는 1과 자기자신을 약수로 가지는 모든 자연수이며, 대표적으로 2, 3, 5, 7, 11, 13, ... 등이 존재한다. 우선, 에라토스테네스의 체를 사용하지 않고 기본적인 소수 판별 코드는 다음과 같다. [소수 판별 기본 코드] #include bool isPrimeNumber(int x) { for(int i=2; i

다이나믹 프로그래밍은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 다이나믹 프로그래밍으로 피보나치 수열의 문제 점을 해결할 수 있는데, 피보나치 수열은 특정한 숫자를 구하기 위해 특정한 숫자 바로 앞에 있는 수와 두 칸 앞에 있는 수의 합을 구하는 방식이다. 피보나치 수열은 동일한 문제를 다시 풀어 비효율적이라는 문제점이 있다. 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다는 가정 하에 사용이 가능하다. 다이나믹 프로그래밍을 통해 피보나치 수열의 문제점을 해결하기 위해서는 이미 계산한 결과를 배열에 저장함으로써 나중에 동일한 계산을 해야할 때 저장된 값을 단순히 반환하도록 한다. [예제] #include int d[..

이진 트리는 데이터의 탐색 속도 증진을 위해 사용하는 구조이다. 완전 이진 트리가 아닌 이진 트리는 배열로 표현하기 어렵기 때문에 포인터(Pointer)를 사용하는데, 포인터를 통해 특정한 Root에서 자식 노드로 접근할 수 있다. 이진트리 데이터 탐색 순회 방식은 전위순회, 중위순회, 후위순회 총 3가지가 존재한다. 1. 전위순회 (Preorder Traversal) (1) 자기 자신을 처리한다. (2) 왼쪽 자식을 방문한다. (3) 오른쪽 자식을 방문한다. 2. 중위순회 (Inorder Traversal) (1) 왼쪽 자식을 방문한다. (2) 자기 자신을 처리한다. (3) 오른쪽 자식을 방문한다. 3. 후위순회 (Postorder Traversal) (1) 왼쪽 자식을 방문한다. (2) 오른쪽 자식을..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 크루스칼 알고리즘은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 그림과 같은 그래프에서 정점은 7개, 간선은 11개 이다. 가장 적은 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 6개 이다. 즉, 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 노드 개수 -1 이다. 최소 비용 신장 트리는 거리를 기준으로 오름차순 정렬을 한 후 그래프를 연결함으로써 만들 수 있다. 주의할 점은 정렬된 순서에 맞게 그래프에 포함시키기 전에 사이클이 형성되면 안된다. 그렇기 때문에 사이클 테이블을 먼저 확인한 후, 만약 사이클을 형성하는 경우에는 간선을 포함하지 않도록..

유니온 파인드 알고리즘은 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여 서로 같은 그래프에 속해 있는지 판별하는 그래프 알고리즘이다. 그림과 같이 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 그림에 대해 구체적으로 설명하자면, (1) 노드가 모두 연결되지 않은 상태에서의 각 노드의 부모노드는 자기 자신을 가리킨다. (2) 1과 2를 연결하면 2의 부모노드는 더 작은 값인 1 이다. (3) 2와 3을 연결하면 3의 부모노드는 더 작은 값인 2 이지만, 재귀 함수를 통해 결과적으로 1이 부모노드가 된다. [예제] #include int getParent(int parent[], int x) { if(parent[x] == x) return x; return parent[x] = getPar..