-

[백준] 2413번 비슷한 순열 (C++) 문제 풀이 2413번: 비슷한 순열 1부터 n까지의 수들을 중복 없이 나열한 것을 순열이라 한다. 순열이 하나 주어졌을 때, 그 순열과 비슷한 순열들 중에서 제일 작은 것을 구하는 프로그램을 작성하시오. 순열이 비슷하다는 것은 www.acmicpc.net 개인적으로 재미있는 문제라고 생각해서 블로그에 포스팅 해야겠다고 생각했다. 2413번 비슷한 순열 분류 : 그리디 알고리즘 난이도 : 골드 2 정답률 : 41% 조건 각 숫자와 최대 1 차이가 나야한다. 가장 작은 순열을 찾아야 한다. 해당 조건을 자세하게 생각해보면 다음과 같은 특이점을 찾을 수 있다. (1) 모든 숫자가 1번씩 나타나야 하고, A에는 (A-1, A, A+1)만 사용 가능하므로, 만약 A라는 ..

문자열 탐색 중에서 가장 빠르다고 알려져있는 KMP 알고리즘에 대해서 정리해보겠다. KMP 알고리즘은 백준 사이트에서 최소 골드 2 등급을 받는 문제들로 난이도가 있는 편이다. 하지만, 한 번 정리하고 사용해보고 나면 그렇게 어렵게 느껴지지는 않아서, 해당 내용 정리해보려고 한다. 이중 배열로 문자열 탐색하기 일단, KMP 알고리즘을 사용하지 않고 문자열을 탐색해 보자. BADABCABDABCABCABDAB 라는 문자열 속에서 'ABCABDAB'라는 문자열을 찾으려면 어떻게 해야할까? 가장 쉽게 2중 for문을 통해 찾는 방법이 있다. 이때 찾을 문자열의 길이가 M, 대상 문자열의 길이가 N일 때의 시간 복잡도는 O(N*M)이 될 것이다. for(int i=0; i

최소 스패닝 트리란? 연결된 트리가 있을 때, 최소 개수 & 최소 비용을 가진 edge를 선택하여 모든 vertex가 연결된 트리를 만들고, 그것을 최소 스패닝 트리라고 부른다. 위의 그림에서 edge를 1개 이상 선택하여 부분 트리를 만들 수 있다. 그러나 그 중에서 모든 vertex가 연결되면서 비용이 최소가 되야 한다. 모든 vertex가 연결되면서 최소 비용이 되기 위해서는 vertex N개를 선택하기 위해서 edge는 N-1을 선택하는 것이 최소가 될 것이다. 크루스칼 알고리즘 최소 스패닝 트리를 구하는 알고리즘에는 크게 크루스칼 알고리즘과 프림 알고리즘이 있다. 그 중에서 크루스칼 알고리즘이 구현이 조금 더 쉬운 편이라서 해당 알고리즘을 자주 활용하는 편이다. 해당 알고리즘을 설명 후 구현까지..

처음에는 문제를 생각해본다,, (1) 브루트포스로 풀 수 잇을까? (2) 안되면 어떻게 풀지 ,,, 이분탐색은 O(N) → O(log2N)으로 줄일 수 있는 분할정복 알고리즘이다 이분탐색 전에는 배열이 모두 정렬되어 있어야 한다 예를 들어서 소주병 뚜껑에 어떤 숫자가 적혀있는 지 가장 빠르게 구하는 방법은 무엇일까? 뚜껑 숫자의 범위가 1~50일 경우에, (1) 1부터 50까지 다 질러본다 -> 브루트포스 방법이고, 총 O(N)의 시간복잡도를 가질 것이다. (2) 가운데(25)부터 시작해본다, 만약 UP일 경우 (26~50) 사이로 다시 탐색을 해본다. -> 결국 N개의 숫자를 모두 탐색하는 것이 아니라, 반씩 나누면서 범위를 좁히며 탐색하게 되고 결국 시간복잡도는 O(logN)이 된다. 구현방법 1 w..

구간 합을 더 빠르게 구하는 방법, 구간 합을 구하는 방법을 생각해 보자, A[1:10]까지의 배열 합 ? → O(n), 만약 n이 엄청나게 크다면 ,, ? → O(log n)만에 구간 합을 구하는 방법을 생각해 보자 😁 다음과 같은 트리를 만들자, 트리의 부모 노드는 항상 '합'을 저장하고 있다. 세그먼트 트리 만들기 위의 트리에서 11개의 노드를 저장하기 위해서 32개의 배열을 사용하고 있다. (트리 저장하는 방법 아시죠?) N개의 노드를 저장하기 위해서 넉넉하게 4*N개의 배열을 할당하는 것으로 시작하면 된다. 구간합을 구하기 위한 세그먼트 트리를 만드는 것은 재귀적으로 구현할 수 있다. int A[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} int tree[40] in..

배열의 누적합 구하기 O(n) 1차원 배열 A에서 A[3:10] 의 합을 구하라 푸는 방법은? A[0:x] 까지의 합을 저장하고 있는 pSum[x] 배열을 만든다 A[3:10] 까지의 합은 = pSum[10] - pSum[2]로 구할 수 있다 당연히 시간 복잡도는 O(n)이 된다 최대 누적합 구하기 다이나믹 프로그래밍을 사용 D[i] 자신을 포함하는 부분합을 만든다. 그때 부분합이 가능 큰 것을 저장한다. //A는 배열 D[1] = A[1]; ans = MIN; for(i=2; i=1; i--){ D2[i] = max(D2[i+1] + A[i], A[i]); } //k번째를 하나 빼고 구하는 누적합 for(k=2; k

어떤 문제에서 적용? 동일 부류인지 확인할 때 동일 부류가 아닌지 확인할 때 총 몇 개의 묶음인지 확인할 때 분리집합이란? 교집합이 존재하지 않는 둘 이상의 집합 분리집합을 만들어가는 과정, 그리고 코드 작성하기 해야할 것 첫번째, 내가 가리키는 부모의 숫자를 저장하자. // 초기화 과정 int p[10001]; for(i=1; i 메모이제이션을 사용하여 무려 [거의 O(1)]이 가능하다 int find(int n){ if(p[n] == n) return n; return (p[n] = find(p[n])); //경로 압축 } 3. 두 집합을 하나의 집합으로 합치는 과정 void union(int i, int j){ // i와 j에는 이미 경로압축이 다 되었음 p[p[j]] = p[i]; } if(fin..