본문 바로가기

알고리즘

 (401)
7854. 최약수 [1. 정의] 최약수: 앞에 어떤 숫자를 붙여도 자기 자신을 약수 갖는 수. 예제 2 앞에 어떤 수를 붙여도 해당 수는 2를 약수로 갖는다. 12 5 앞에 어떤 수를 붙여도 해당 수는 5를 약수로 갖는다. 38275 [2. 요구 사항] 임의의 숫자 X 가 있을 때, X 보다 작거나 같은 최약수의 개수 X 의 범위는 [1, 10^9] [3. 해결 방법] 주어진 조건을 만족하는 수를 다음과 표현 할 수 있다. T = (R+X) T % X == 0 X = a*10^N + b*10^(N-1) + ... + z*10^0 각 계수는 모두 0 이 아닌 자연수 N < 9 인 경우 0 < [a ~ z] < 10 N == 9 인 경우, a == 1 이고 [b ~ z] 는 모두 0 R = a`*10^(N+1) + b`*10..
최소 신장 트리 그래프와 관련된 알고리즘 중 여기서는 최소 신장 트리(Minimum Spanning Tree, 이하 MST)의 구현에 대해 살펴보겠다. MST는 가중치가 있는 무방향 그래프의 한 부분 집합으로서, 그 특징은 그래프를 구성하는 가중치의 합이 최소인 연결 그래프(간선의 개수 == 정점의 개수 - 1) 라는 것 이다. 이러한 MST를 구하는 알고리즘에는 크게 두 가지가 있는데, 첫번째는 크루스칼 알고리즘이고, 두번째는 프림 알고리즘이다. 여기서는 먼저 크루스칼 알고리즘을 간략히 정리하고, 그 구현에 대해 살펴보겠다. 1. 간선을 가중치를 오름차순으로 정렬한다. 2. 남아있는 간선 중 최소 가중치의 간선을 선택 3. 해당 간선을 MST에 추가 시 사이클이 발생하면 제외, 발생하지 않으면 추가. 4. 간선의 개수..
같은 것이 있는 순열 aaaabbbccd 를 나열 할 때 서로 다른 순서쌍의 개수를 구하는 문제는 확률과 통계라는 과목에서 많이 다루었던 문제이다. 그 개수는 10!/(4!*3!*2!*1!) 이렇게 구했던 거로 기억한다. 이번에는 이러한 순서쌍이 실제로 어떻게 생성되는지 코드로 구현해 볼 차례이다. 내가 구현한 코드의 알고리즘은 다음과 같다. 111 22 3 이 있다 했을 때, 먼저 1은 총 3개가 있다. 그래서 1의 자리를 먼저 배치한다. [1][][][][][], - 1c [1][1][][][][], - 2c [1][1][1][][][], - 3c 여기서 중요한 부분은 1c에서 2c로 넘어 갔을 때 해당 1은 1c에서 선택된 자리 다음부터 선택 할 수 있다는 것이다. 이를 통해 111 이 중복되는 것을 막을 수 있다. 예..
중복 조합 고등학교 확률과 통계라는 과목에서 중복조합에 대한 내용을 공부한적이 있다. 그 중 중복조합과 관련된 문제 중 가장 일반적인 문제가 a + b + c = 6 일 때 음이 아닌 정수 의 (a, b, c) 쌍이 몇개 인지 구하는 것이다. 이 문제를 중복 조합 공식으로 풀면 그 개수만 알 뿐 어떤 조합이 생기는지는 알 수 없다. 그래서 이를 코드로 작성하면 아래와 같다. static void comb() { for (int a = 0; a
이진 탐색 이진 탐색은 순차 탐색에 비해 평균적으로 빠르지만 탐색에 대상이 되는 배열이 정렬된 상태임이 보장되어야 한다. 또 정렬된 배열이 오름차순인지 내림차순인지 따라 내부 구현이 살짝 달라지게 된다. 여기서는 오름차순 배열을 대상으로 하겠다. int bin_search(int * arr, int len, int target) { int l = 0, r = len - 1; int mid; while (l
Graph, DFS and BFS 그래프를 표현하는 방법에는 크게 두가지가 있다. 첫번째는 인접행렬이고, 두번째는 인접리스트이다. 전자는 정점이 N개라면 N * N 만큼의 메모리가 필요하며, (2차원 배열) 후자는 간선의 개수만큼의 메모리만 필요하다. (연결 리스트) 그러나 탐색관점에서 본다면 전자의 경우는 A라는 정점에 연결된 여러개의 정점들에 바로 접근 할 수 있지만, (인덱스를 통해) 후자의 경우는 리스트이기 때문에 그렇게 할 수는 없다. (list->next->next...) 그래서 메모리와 탐색 측면에서 그래프를 표현하는 방법으로 C++의 vector를 이용 할 수 있다. vector의 push_back을 이용하여 아래와 같은 형태의 그래프를 표현 할 수 있다. V Adj ---------- A ->[][] B ->[][][] ..
병합정렬 시간복잡도가 O(nlogn) 인 정렬 알고리즘이다. divide & conquer 의 대표적인 예라 볼 수 있다. 동작방식은 아래를 재귀적으로 한다. 1. 배열을 절반으로 분할 한다. 2. 분할 된 배열을 병합한다. void merge_sort(int * arr, int len) { if (len merge -> arr1 = {5} & arr2 = {4} -> arr[] = {4, 5} -> arr1[] = {4, 5}, 여기서 arr1 == arr 2) merge_sort(arr + 3, 3) : 4, 5 | {3, 2, 1} ->merge_sort(arr + 2, 1) & merge_sort(arr + 2 + 1, 2) -> merge_sort(arr + 2 + 1, 1) & merge_sort(ar..
삽입정렬 void selection_sort(int * arr, int len) //오름차순 { for (int i = 1; i = 0; j--) { if (val < arr[j]) arr[j + 1] = arr[j]; else break; } arr[j + 1] = val; } } 시간복잡도가 O(n^2) 인 정렬 알고리즘 중 하나이다. 이미 정렬된 경우 O(1)의 성능을 보인다. 5, 4, 1, 2, 3 이 함수의 인자로 전달 되면 0번 인덱스는 이미 정렬되어 있다고 가정하면서 정렬을 시작한다. 1) 5 | 4, 1, 2, 3 에서 4를 선택한다. j = 0 이므로 아래 반복문을 시작한다. arr[1] = ..
달팽이 배열 (1)-> (1)-> (1)-> (1)-> (1)-> (~2)↑ (1)-> (1)-> (1)-> (2)↓ (~2)↑ (~2)↑ (1)-> (2)↓ (2)↓ (~2)↑ (~1)
소인수분해 모든 수는 소수의 곱으로 이루어져 있다. 그래서 어떠한 수를 소수들의 곱으로 분해하는 것을 소인수분해라 한다. 72 = 8 * 9 = 2^3 * 3^2, 소수인 2와 3의 곱으로만 이루어져 있다. void prime_factorization(int a) { // int div = 2; while (a % div == 0) { // a /= div; cout

티스토리툴바