본문 바로가기

알고리즘

 (403)
각 언어 별 배열 정렬 방법 정리 [1. 개요] 각 언어 별 배열을 정렬하는 방법을 정리하도록 한다. 각 언어 별 표준 라이브러리에서 제공하는 정렬은 보통 O(nlogn) 으로 구현되어 있다. 기본적으로 오름차순으로 정렬하는 방법을 정리하고, 내림차순은 정렬 판단 시 사용 되는 함수를 반대로 구현하거나 배열을 역순으로 조회하면 된다. [2. C언어] [3. C++] [4. go] => 기타 알고리즘 문제 풀이 참조 [5. python] [6. rust] => 작성 필요
최소신장트리. [1197] [1. 문제 설명] 그래프가 주어졌을 때, 최소 신장 트리의 가중치를 출력한다. [2. 풀이 접근] A. 크루스칼 알고리즘 edge 를 가중치를 기준으로 하여 오름차순 정렬한다. 가중치가 낮은 edge 부터 tree 에 추가하도록 한다. => edge 추가로 인해 cycle 이 발생하는 경우, 이번 edge 는 버리도록 한다. tree 에 추가된 edge 개수가 정점의 개수 - 1 일 때 까진 반복한다.\ => cycle 여부 판별을 union-find 를 이용하면 전체 알고리즘은 정렬 시간에 가장 큰 영향을 받는다. (최적의 union-find 는 거의 상수 시간으로 동작 하기 때문이다.) => 시간복잡도: O(ElogE) B. 프림 알고리즘 임의의 정점에서 시작한다. (보통 번호가 가장 빠른 노드) ..
소수 판정 [1. 개요] 어떠한 자연수가 소수인지 판별 할 수 있는 방법에 대해 정리한다. [2. 알고리즘] 단순한 방법 => 소수는 1과 자기자신으로만 나누어 떨어지므로, => 2 부터 N-1 까지의 자연수 중 나누어 떨어지는 것이 있는지 확인 한다. => 단일 자연수 N에 대해서 시간 복잡도는 O(N) 이 된다. N 의 절반까지만 확인 => N 의 제곱근 까지만 확인 => [3. 에라토스테네스의 체] 특정 범위 내 모든 소수를 찾을 때 매우 유용하다. 시간 복잡도가 O(nlog(logn)) 이다. 원리 최초 모든 수를 소수라 가정 '1'은 소수가 아니라고 망킹 '2' 는 소수이므로, 2의 배수를 모두 소수가 아니라고 마킹 '3' 은 소수이므로, 3의 배수를 모두 소수가 아니라고 마킹 다음 수 에 대해서 반복, ..
Meet in the middle. [1450] [1. 문제 설명] N 개의 물건을 최대 C 만큼의 무게를 넣을 수 있는 가방에 넣을 수 있는 경우의 수를 구한다. N 은 30 이하의 자연수 C 는 10억 이하의 자연수 [2. 풀이 접근] 이 문제는 동적 계획법으로 풀이가 가능하다. 단, 완전 탐색 중 i 번째 물건을 포함할지 말지를 결정할 때, 아래에 대해서 메모이제이션 할 수 있어야 한다. i번째 물건의 index 현재까지 누적된 무게 그러나 문제에서 C 는 최대 10억이 될 수 있으므로, 메모리가 부족하여, 다른 접근법이 필요하다. 다시 완전 탐색으로 돌아와서 생각해보면, 문제는 탐색의 개수가 너무 많다는 것이다. 재귀의 각 단계에서 i번째 물건 선택여부가 존재하니, 총 탐색 개수는 2N 이다. N 이 최대 30이니, 대략 10억 정도 된다. 여..
투 포인터 .[1644] [1. 문제 설명] 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다. (N https://testkernelv2.tistory.com/378 소수 리스트를 구할 수 있으므로, 부분 합을 구하면 나머지는 여타 다른 문제들과 비슷하다. head 와 tail 을 옮겨가면서 주어진 자연수가 되는지 확인하는 것이다. [3. 코드]
투 포인터. [1806] [1. 문제 설명] 10,000 이하의 자연수로 이루어진 길이 N 인 수열에서 연속된 부분 합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구한다. [2. 풀이 접근] 먼저 부분 합을 구한다. 연속된 부분 합을 찾기 위한 탐색을 해야 하는데, 자연수로 이루어진 수열의 부분 합은 값이 증가할 수 밖에 없으므로, 여기서는 head 와 tail 을 맨 앞에서 부터 움직이도록 한다. 최초 head 를 고정 시킨 상태에서 tail 을 움직이면서 부분 합이 S 이상이 되는지 확인하도록 한다. S 이상이 된 경우 head 를 움직이도록 한다. head 를 움직인 경우 S 미만이 되면, tail 을 움직이도록 한다. 부분 합은 오름차순으로 되어있기 때문이다. === 실수했던 사항 === 불가능 한 경우 ..
05. 조합 탐색 - 예제2 [1. 문제 설명] m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다. 각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때, 각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 최소 몇가지의 음식을 해야하는가? [2. 풀이 접근] NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다. 탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만, 모든 입력에 대해 최적해를 찾아낼 수는 없다. 예제) ??? 완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만, 시간 내에 동작하지 않는다. 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다. 매 재귀 호출마다 아직 먹을 음식이 없는 친구를..
05. 조합 탐색 [1. 개요] 동적 계획법이나 분할 정복 등의 문제 해결 방법을 모든 문제에 적용 할 수 없다. 캐시를 위한 메모리를 너무 많이 사용하거나 적절한 분할 방법이 없는 경우가 존재하기 때문이다. 이 경우 완전 탐색에서 다시 돌아와 생각 해야 한다. 부분 답과 완성된 답의 집합을 탐색공간이라 부른다. 완전 탐새의 수행 시간은 탐색 공간의 크기에 비례한다. 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라 부르기로 한다. 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하지 않는다. [2. 가지치기 기법] pruning 기법은 현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 구한 최적해보다 나쁘면 탐색을 더 하지 않는다. 똑똑한 가지치기 기법들은 ..
투 포인터 https://testkernelv2.tistory.com/369
투 포인터. [3273] [1. 문제 설명] n 개의 서로 다른 양의정수로 이루어진 수열에서 두 수의 합이 x 가 되는 쌍의 개수를 찾는다. [2. 풀이 접근] 투 포인터 란? 배열 형태에 자료 구조에 순차적으로 접근 해야 할 때, 배열 내 두개의 위치를 기록하면서 하는 방식 병합정렬에서 나눈 두 배열을 다시 병합하는 방식을 생각하면 된다.. ↓ ↓ [head] ........[mid].......[tail] 포인터 혹은 index 를 각각 배열의 시작(head) 과 끝(tail) 에 위치 시키고, head 또는 tail 을 이동시키면서 처리하는 방식 head 와 tail 이 역전되는 순간 탐색을 종료하게 된다. 특별한 경우 간단하게 생각할 수 있는 O(N2) 알고리즘을 O(N) 으로 풀 수 있게 해준다. 가급적 정렬 시킨 배열..

티스토리툴바