알고리즘

[알고리즘]그리디(Greedy, 탐욕법, 욕심쟁이기법)

그리디 알고리즘이란? 탐욕알고리즘, 욕심쟁이기법 이라고도 합니다. 매순간 최적이라고 생각하는 해를 선택해나가서 최종적으로 최적해에 도달하는 알고리즘이라고 할 수 있습니다. 그렇게 때문에 구한 해가 항상 최적임이 보장되지는 않아서 근삿값을 구하는 용도로 사용되기도 합니다. 탐욕법이 충족되기 위한 조건 앞의 선택이 이후의 선택에 영향을 주지않을 때 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해일때 이렇게 2가지 조건을 만족할 때 그리디알고리즘이 잘 작용합니다. 이 조건들을 만족하지 못하면 최적해를 구하지 못하고 근삿값은 구할 수 있습니다. 개념자체만 봤을 때는 이해가 잘 안될 수 있으니 예제를 봅시다. 예제1 - 거스름돈(백준 5585번) 잔돈으로 500, 100, 50, 10, 5, 1엔이 있고 1..

[알고리즘]퀵 정렬(Quick Sort)

퀵정렬이란? 퀵정렬은 이름그대로 빠른정렬, 즉 다른 정렬알고리즘에 비해 빠르다고 할 수 있습니다. 다른원소와의 비교를 통해 정렬이 이루어지므로 비교정렬에 속하고, 같은 수가 있는 경우 같은 수의 순서가 달라질 수 있어서 불안정 정렬에 속합니다. ex) 5(1), 5(2), 3, 2, 1 -> 1, 2, 3, 5(2), 51(1) 시간복잡도 최악의 경우 O(n^2) 평균 O(n log n) 알고리즘 임의의 수(pivot)를 고른다. 피벗을 기준으로 두 수를 비교하여 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다. 분할된 리스트 가운데에 피벗을 위치 시키고, 양쪽 리스트에 대해 재귀적으로 수행한다. 예제 가장 오른쪽에 있는 4를 pivot으로 정함. pivot을 제외하고..

[알고리즘]깊이우선탐색(DFS),너비우선탐색(BFS)

그래프 탐색이란? 하나의 정점에서 시작하여 다른노드와 이어진 간선을 통해 다른 모든 정점들을 한번씩 방문하는 것입니다. 깊이우선탐색, 너비우선탐색은 그래프 탐색의 기본이라고 할 수 있습니다. 깊이우선탐색(Depth-First Search) 새로운 노드가 탐색될 때마다 그 노드로 이동하고, 다시 돌아와서 새로운 노드를 탐색하는 방법 시작노드에서 시작 인접한 다른노드 탐색 탐색한 노드에서 인접한 노드 중 탐색되지않은 노드 확인 인접한 노드 중 탐색되지 않은 노드가 없으면 다시 되돌아오면서 탐색되지않은 노드 확인 만약 탐색되지 않은 노드가 있다면 탐색 소스코드(c++) #include #include using namespace std; int N, E; //노드개수, 에지개수 int U, V; //연결되어있..

[알고리즘]완전탐색(Brute-force)

브루트포스(brute force)알고리즘, 완전탐색이란 가능한 경우를 모두 탐색해보는 방법입니다. 예시로는 해킹 시 모든 가능한 경우의 비밀번호를 다 넣어보는 것 등이 해당됩니다. 특정 알고리즘을 쓰게 하기 위해 시간제한이 짧은 경우엔 시간초과가 나지만, 때로는 완전탐색을 하는 방법이 간단하고 확실한 방법일 수 있습니다. 예제 (c++) 백준 2309-일곱 난쟁이 9명의 키가 입력으로 주어지는데 키 합이 100이 되는 7명의 키를 출력하는 문제입니다. #include #include #include using namespace std; int main() { vector v; int sum = 0; int one = 0; int two = 0; for (int i = 0; i < 9; i++) { int..

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

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming)은 다른말로 동적계획법 이라고 합니다. 저도 처음에는 동적계획법을 듣고 왜 동적계획법일까? 했는데 이름 지으신분이 그냥 이 이름이 멋있어서 이렇게 지었다고 하네요... DP(다이나믹 프로그래밍)알고리즘은 백준 사이트 알고리즘별로 문제풀기에서 가장많은 문제수를 가지고 있어요! 그만큼 종류도 다양하고, 출제빈도도 높습니다. ​ DP는 작은문제를 풀어서 큰문제를 해결하는 알고리즘입니다. 여기서 주의할점은 작은문제들을 여러번에 걸쳐서 다시 푸는일이 없도록 어딘가에 값을 저장해두고, 필요할 때 그 값만 가져와서 사용한다는 점입니다. ​ 즉, 문제를 여러번 풀지않고 단 한번만 계산을 할 수 있는 거죠. ​ ​ 예) 피보나치 수열 위는 ..

[알고리즘]삽입정렬(Insertion Sort)

삽입정렬이란? 두번째 수부터 자신 왼쪽의 수와 비교하여 내가 더 작으면 왼쪽으로 이동하고, 크면 오른쪽 위치를 유지합니다. 위치를 유지했으면 그 수에 대한 비교는 종료 왼쪽으로 이동했으면, 다시 자신의 왼쪽 수와 비교를 반복합니다. 내 왼쪽과 비교 내가 더 크면 현재 위치 유지 내가 더 작으면 왼쪽 수와 교체(swap) 다시 1번단계부터 비교 반복 마지막 수 까지 비교완료하면 종료 시간복잡도 최악의 경우는 역으로 정렬되어 있는 경우 n-1, n-2, ... 1만큼 비교하여 시간복잡도 O(n^2)입니다. 소스코드(C++) #include using namespace std; void insertion_sort(int arr[],int size){ //삽입정렬 for(int i = 1;i0&&arr[j-1]..

[알고리즘]선택정렬(Selection Sort)

선택정렬이란? 선택정렬은 앞에서부터 쭉 탐색하면서 가장 작은 수를 찾습니다.(오름차순의 경우) 그리고 그 수를 (정렬되지 않은 부분의)맨앞의 수와 교체합니다. 이 과정을 정렬되지 않은 수가 1개 남을 때까지 반복하면 됩니다. 이 때 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 탐색은 정렬되지 않은 부분에 대해서만 이루어 집니다. 주황색 - 정렬된 부분 흰색 - 정렬되지 않은 부분 하늘색 - 정렬되지 않은 수 중 가장 작은 수 정렬되지 않은 부분에서 가장 작은 수를 찾는다. 정렬되지 않은 부분의 맨 앞의 수와 가장 작은 수를 교환(swap)한다. 교환된 가장 작은 수는 정렬된 부분이 된다. 정렬되지 않은 부분에서 위 과정을 반복하고, 모두 정렬되면 종료 시간복잡도 가장 작은 수를 찾는데..

[알고리즘]버블 정렬(Bubble Sort)

정렬 알고리즘에는 대표적으로 병합정렬, 퀵정렬, 삽입정렬, 선택정렬, 버블정렬 등이 있습니다. 이번에는 그 중에서 제일 간단하게 구현할 수 있는 버블 정렬을 알아보겠습니다! 버블 정렬(오름차순) 버블 정렬은 앞에서부터 두수를 비교하며 가장 큰수를 찾고, 남은 수를 다시 두개씩 비교하며 그 다음으로 큰 수를 찾는 과정을 원소가 1개 남을 때까지 반복하는 정렬 알고리즘입니다. 시간 복잡도 위 예시에서 n = 5이므로 제일 큰 숫자인 5를 찾는데까지 4번(=n-1번)이 걸리고 다음으로 큰 숫자인 4를 찾는데까지 3번(=n-2번)이 걸립니다 총 4+3+2+1번이 걸립니다. n개의 수를 정렬하는 시간은 n-1+n-2+n-3+...1이므로 ((n-1)(n-2))/2 = O(n^2)입니다. 최선, 최악의 경우 모두 ..

[백준-9020]골드바흐의 추측(C++)

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수 www.acmicpc.net 모든 짝수는 두 소수의 합으로 표현할 수 있다는 것이 골드바흐의 추측입니다. 짝수가 주어졌을 때 합으로 표현할 수 있는 두 소수를 찾으면 됩니다. (여러개일 경우 차이가 가장 적은 두 소수를 찾으면 됩니다) 예) 8 = 3+5 10 = 5+5 16 = 5+11 이전에 포스팅한 소수찾기 문제를 응용하면 풀 수 있는 문제입니다. 문제 해결한 알고리즘 주어진 짝수를 n이라 하겠습니다..

[백준-1978]소수 찾기(C++)

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 입력받은 수 중에서 소수의 개수를 찾는 간단한 문제입니다. 예전에 프로그래머스에서 풀어봤는데 그 때 막코딩으로 풀었다가 계속 시간초과 났던게 생각나네요ㅜㅜ 우리가 수학시간에 배워서 알고있던 소수의 정의로 푸는 것 보다 좀더 빠르게 구현할 수 있는 소수찾는 알고리즘이 있습니다. 소수 찾는 알고리즘 소수 배열이 있다고 생각해봅시다. 소수 배열에는 일단 확실히 소수인 2만 들어가있습니다. 2부터 시작해서 3,4,5,6,7,8,9... 이 수들이 소수인지 판별해볼건데요 방..