소파와 바보개의 블로그

그리디 알고리즘 (Greedy Algorithms)?그리디 알고리즘은 항상 그 순간에 할 수 있는 최고의 선택을 하면서 문제를 해결하는 방식입니다. 선택을 되돌리는 것은 없고 최고의 선택만을 하면서 바로 결과를 도출합니다. 그러므로 매우 효과적이기는 합니다. 그러나 항상 모든 문제에 대한 최적의 답을 구해주지는 않습니다. 동전 문제(Coin Problem)그리디 알고리즘을 적용할 수 있는 예시로는 동전의 단위가 주어졌을 때, K원을 만들기 위한 최소 동전 갯수를 찾는 문제가 있습니다. 예를 들어 {1, 5, 10, 20, 50, 100, 200} 단위의 동전을 가지고 540원을 만드는 최소 동전 갯수를 찾는 문제입니다. 이 경우 가능한 큰 동전부터 금액이 모두 차감될 때까지 다 사용해보는 greedy한 ..

백트래킹(Bactracking)?백트래킹 알고리즘은 비어있는 상태에서 시작해서 단계별로 확장해 나가는 방법입니다. 정답을 만들어 나가는 여러가지 방법을 재귀적으로 생성합니다. N*N의 체스판에 N개의 Queen을 서로 공격하지 못하도록 배치하는 경우의 수를 찾는 문제가 대표적인 백트래킹 문제입니다. N=4 인 경우를 예시로 들면, Queen을 서로 공격하지 못하게 하려면 같은 row에 존재해서는 안되기 때문에, 백트래킹으로 한개의 row씩 확장해 나갈 수 있습니다. 아래와 같은 형태로 row 마다 queen을 배치후 다음 row로 진행 시키면서 현재 상태가 유효한 상태인지를 확인하다보면 마지막 level에 도달한 경우 queen 들이 서로 공격하지 못하도록 배치된 경우가 됩니다.  2025.02.21 -..

완전 탐색 (Complete Search)?완전 탐색은 어떤 알고리즘 문제라도 해결할 수 있는 일반적인 방법입니다. 이 방법은 가능한 모든 해결책을 만들고 그 문제에서 원하는 최고의 해결책을 선택합니다. 이 방법은 항상 정답을 도출할테니, 문제에 대해 완전 탐색할 시간이 주어진다면 아주 좋은 방법이겠지만 문제를 해결하는데 있어 너무 느리다면 다른 방법들을 사용해야할 것입니다.Subset 만들기완전 탐색문제를 해결하기 위해 N개의 요소에 대하여 가능한 모든 부분집합(subset)을 생성할 필요가 있습니다.예를들면 {A, B, C}의 subset은 {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}입니다. 이는 A, B, C 3가지 요소에 대해 가능한 모든 경우의 수를 도출..

자료 구조(Data Structures)? 메모리에 데이터를 저장하는 방법입니다. 각각의 자료 구조들은 저마다의 장단점을 가지고 있기 때문에 문제를 풀기위해 적절한 자료 구조를 선택하는 것이 중요합니다. C++의 standard 라이브러리에는 중요한 자료 구조들이 내장되어 있어 그 것들을 사용하는 것이 좋습니다.Dynamic Arrays프로그램의 실행 중에 크기가 변할 수 있는 배열입니다. 그 중 C++에서 가장 많이 사용되는 것은 vector 입니다.일반적인 배열과 거의 유사하게 사용할 수 있습니다. vector의 사이즈가 증가하면 새로운 배열이 할당되고 새로운 배열로 요소들을 옮기는 식으로 동작합니다.  그러나 자주 발생하는 작업은 아니고, 평균적인 push_back 의 시간 복잡도는 O(1) 입니다..

Binary Search?배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생성된다면 별다른 방법이 없겠지만 배열이 정렬되어 있다면 훨씬 더 빠른 시간에 수행할 수 있는 좋은 방법이 있습니다. Binary Search는 정렬된 배열에서 요소를 O(logN) 시간에 찾아냅니다.Binary Search Implementation 1 일반적인 구현 방식으로, 초기 상태에는 모든 배열 요소가 탐색 대상입니다. 그러나 step이 진행될 때마다, 탐색 대상을 절반으로 줄입니다. 각 단계에서는, 탐색 대상의 중간 요소를 확인합니다.  만약 중간 요소가 탐색 대상과 같다면 탐색은 종료..

Sorting in C++매번 정렬할 때마다 정렬을 직접 구현하는 것은 좋은 생각이 아닙니다. C++ 등의 Programming Language들은 좋은 내장 라이브러리를 제공합니다. 예를 들면, C++의 standard 라이브러리에는 배열과 다른 자료 구조들을 쉽게 정렬 할 수 있게 도와주는 sort function이 내장되어 있습니다. 이런 것들을 사용하면 시간도 절약할 수 있고 훨씬 더 좋은 성능을 내줍니다. 아래 코드는 vector를 오름차순으로 정렬합니다. vector v = {9, 8, 7, 5, 4, 2, 6}; sort(v.begin(), v.end()); // 2 4 5 6 7 8 9 아래 코드는 vector를 내림차순으로 정렬합니다. vector v = {9, 8,..

Counting Sort?O(NlogN) 에 정렬하지 않으려면 배열의 요소를 비교하는 것 외에 다른 정보를 이용해야 합니다.  Counting Sort는 만약 배열 내의 모든 요소가 0...c 사이의 정수라면 c = O(N)에 배열을 정렬합니다. Counting Sort는 bookkeeping 배열을 사용하며, 이 배열은 원본 배열의 값을 인덱스로 갖습니다. 원본 배열을 1회 순회하면서 이 배열에서 등장하는 빈도 수를 계산 합니다. 예를 들어, { 1 3 7 9 8 9 5 1 } 이라는 배열이 있을 때이것에 대한 bookkeeping 배열은 { 2 0 1 0 1 0 1 1 2 } 입니다. bookkeeping 배열 생성에는 O(N) 시간이 걸리고, 이 작업이 끝나게 되면 앞에서 부터 읽으면서 갯수 만큼 ..

Merge Sort?앞선 Bubble Sort와 같이 연속적인 요소들을 교환하는 방식이 아니라면 O(NlogN)에 정렬하는 것이 가능합니다. 그 중 한가지는 재귀(Recursion)를 기반으로 한 Merge Sort입니다. Merge Sort는 부분 배열인 [S ... E] 를 다음 과정으로 정렬합니다. 1. 만약 S와 E가 같다면 재귀 호출을 종료합니다.  2. S와 E의 중간 요소를 계산합니다. k = (S+E)/2 3. 재귀적으로 부분 배열을 정렬합니다. [S ... k] 4. 재귀적으로 부분 배열을 정렬합니다. [k+1 ... E] 5. 정렬된 부분 배열들, [S ... k] 와 [k+1 ... E] 를 정렬된 [S ... E] 로 합칩니다. Merge Sort는 부분 배열의 크기를 매 단계마다 ..

Bubble Sort?O(N^2)에 수행되는 간단한 알고리즘입니다.짧은 두개의 중첩된 Loop로 구성됩니다. Bubble Sort는 N개의 round가 있습니다. 각 round마다 배열의 요소들을 순회합니다.두개의 정확한 순서로 배치되어 있지 않은 연속적인 요소가 발견되면 두개를 변경합니다.아래와 같은 코드로 수행됩니다. REP(i, 0, N) { REP(j, 0, N-1) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } } 첫 번째 round가 끝나게 되면, 가장 큰 요소는 정확한 위치 (맨 끝)에 위치하게 됩니다.그리고 K 번째 round가 끝나게 되면 K 번째 큰..

시간복잡도란?알고리즘의 시간 복잡도는 알고리즘이 어떤 입력에 대해 얼마나 많은 시간을 사용할지를 추정합니다.시간복잡도를 계산하면 구현하지 않고도 충분히 빠른지 확인할 수 있습니다.Loops예를 들면, 아래 코드의 시간복잡도는 O(n) 입니다. for (int i=1; i 그리고 다음 코드의 시간복잡도는 O(n2) 입니다. for (int i=1; i 일반적인 알고리즘들은 연속적인 단계로 구성됩니다. 전체 시간복잡도는 가장 오래 수행되는 단일 단계의 시간복잡도입니다.그 이유는 가장 느린 단계에서 보통 코드의 병목 현상이 발생하기 때문입니다.아래 코드는 여러 단계로 구성되어 있지만 시간 복잡도는 O(N^2) 입니다. for (int i=1; i Complexity 분류다음은 일반적으로 사용되..