본문 바로가기

알고리즘

 (419)
... [1762] [1. 문제 설명]https://www.acmicpc.net/problem/1762[2. 풀이 접근]완전 탐색시간 초과 발생 사유...선형 탐색 안에서 이분 탐색 시, 선형 탐색 하는 양이 더 많아지게 된다면,,이분 탐색의 장점이 사라짐.즉, 서로 연결 된 두 점의 동시에 연결 되는 점을 찾기 위해서,선형 탐색 (outer) - 이분 탐색 (inner) 조합을선형 탐색 (outer) 의 대상이 되는 노드 의 차수가 항상 더 낮은 값이 오도록 하는 편이 좋다.[3. 코드]
mo`s. [13548] [1. 문제 설명]https://www.acmicpc.net/problem/13548[2. 풀이 접근]동일한 숫자의 발생 횟수를 저장할 배열이 필요함. (occurs)index: 수열의 원소value: 현재 구간에서 해당 원소의 발생 횟수발생 횟수에 대해서 해당 횟수만큼 존재하는 숫자의 개수. - 3이라는 원소가 4번 발생하고, 5라는 원소가 4번 발생한 경우- 4번 발생한 원소의 개수는 2개가 된다.index: 횟수value: 횟수만큼 존재하는 숫자의 개수.즉, 쿼리에 대해서 각 포인터가 (Left, Right) 넓혀지는 방향으로 움직이는 경우.구하고자 하는 최대 값이 갱신 되는지 확인 하도록 한다.반대로, 각 포인터가 좁혀지는 방향으로 움직이는 경우.현재 포인터가 가리키는 원소 a 의 발생 횟수가 1..
제곱근 분할법 [1. 개요]배열에 대한 제곱근 분할법이란배열을 길이의 제곱근 단위로 나누어 구간에 대한 쿼리를 처리하는 것이다.즉, 오프라인 쿼리 처리에서 매우 유용하지만, 수정이 불가능한다는 단점이 있다.[2. 상세]배열의 특정 구간에 대해 최대값, 최소값 등을 계산해야 한다고 할 때,세그먼트 트리 등을 이용해 처리할 수 도 있지만, 배열을 특정한 크기로 묶어서(이하 블록) 아래와 같이 처리 할 수 있다.쿼리 구간 [L, R] 이 블록 들에 interleave 한 경우 쿼리 구간 [L, R] 이 전체 블록을 포함 하는 경우전체 배열의 길이를 N , 블록의 크기를 K 라 할 때, 1번 경우는 아래와 같다.L 이 왼쪽 블록에 포함되고R 이 오른쪽 블록에 포함 됨.이 경우, 쿼리의 시간복잡도는 2K2번 경우는 전체 구간이..
제곱근 분할법. [13546] [1. 문제 설명]https://www.acmicpc.net/problem/13546[2. 풀이 접근]완전 탐색으로 풀이L -> R 방향으로 배열을 순회하면서배열의 값을 index 로 하여 배열의 값의 최초 출현 위치를 기록하고,2회 이상 출현 시, 최초 저장 된 위치를 이용하여 구하고자 하는 길이를 계산 하고,필요 시, 전체 결과를 갱신하도록 한다.완전 탐색 풀이는 배열의 길이와 쿼리의 개수로 보아 그 시간 복잡도는 O(NK) 이고,N 과 K 모두 최대 100,000 이므로, 시간 조건을 만족하지 못함. 여기서, 배열 내 값이 변하지 않고 현재 쿼리의 결과가 나중 쿼리 결과에 영향을 주지 않으므로 오프라인 알고리즘 적용을 고려해 볼 수 있다. 오프라인 알고리즘으로 풀이제곱근 단위로 배열을 분할 및 mo..
차분 배열 [19551] [1. 문제 설명]https://www.acmicpc.net/problem/19951[2. 코드]
차분 배열 [1. 개요]차분 배열은 배열을 효율적으로 구간 단위로 갱신 할 수 있도록 해주는 자료 구조이다.[a. b] 구간에 대해서 +k 를 하고,[c, e] 구간에 대해서 +m 을 하고,...이와 같은 방식으로, 구간 내 변화가 발생한다고 했을 때,단순한 방법으로는 각 구간을 iterate 하면서 업데이트 하는 방법 이 있지만,결국 필요한 구간 만큼 iterate 해야 하는 상황이 발생하게 된다.즉, 쿼리 개수 (Q) 와 구간의 길이 (L) 에 대해서 시간 복잡도 O(Q * L) 이 발생하게 된다. 그러나 차분 배열을 이용하면 동일한 작업에 대해서 시간 복잡도를 O(Q + L) 로 낮출 수 있다.[2. 차분 배열의 정의]어떤 배열 A 가 있을 때, 차분 배열 D 는 아래와 같이 정의 된다.D[0] = A[0]D..
radix tree [1. 개요] [3. 코드]
라빈-카프 [3033] [1. 문제 설명]https://www.acmicpc.net/problem/3033[2. 풀이 접근]완전 탐색으로 접근부분 문자열이 발생할 수 있는 대상은 아래와 같다.부분 문자열의 길이는 1 부터 L-1 까지길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L2) 의 시간 복잡도 발생이분 탐색으로 접근길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다."ABCDE"FGH"ABCDE"XYZ=> ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재..
라빈-카프 알고리즘 [1. 개요] [2. 해시 함수 구현]해시 충돌을 최대한 적게 발생 시키게 하기 위해 K 와 mod 값을 선택해야 하는데두 값 모두 소수 (prime number) 로 선택하는 편이 좋다고 한다.K: 31, 53, 101, 127, 131, 137, ...mod: 1e9+7 과 같은 큰 수. (1e9+3, 1e9+9)# 십만자리 : 1e5+3# 백만자리 : 1e6+3특히 K 는 문자열의 상황에 따라 다른데,알파벳 소문자로 구성 된 경우 : 31, 127, 131, ...알파벳 대소문자 + 숫자 로 구성된 경우 : 53, 131, 911, ...그 외, 257, 997, 1009최소 31 부터 소수 인 값을 선택하면 좋음특히, 거듭제곱 등의 연산이 발생하기 때문에 overflow 에 유의하도록 한다.
포함-배제의 원리. [16565] [1. 문제 설명]https://www.acmicpc.net/problem/16565[2. 풀이 접근]여러 집합의 합집합의 원소 수를 셀 때,각 집합의 크기를 더한 뒤 겹치는 부분(교집합)을 빼거나 더하는 과정을 반복하여 정확한 전체 개수를 구하는 방법. 가령, 1이상 100 이하의 자연수 집합에서 2 또는 3의 배수의 개수를 구해야 할 때,2의 배수 개수를 구하고, 3의 배수를 구하여 서로 더하면,6의 배수가 중복되어 더해진다. (교집합이 되어버림) 따라서, 6의 배수 개수를 전체 결과에서 빼야 정확한 개수를 구할 수 있다.[3. 코드]

티스토리툴바