본문 바로가기

알고리즘

 (395)
분할 정복. [5904] [1. 문제 설명] https://www.acmicpc.net/problem/5904 [2. 풀이 접근] 생성 되는 문자열은 Left / Middle / Right 로 구성 되고 있으며, 여기서 Left 와 Right 는 서로 같다. 최소 어느 정도의 k 일 때 해당 문자열이 찾고하는 위치를 포함하게 된다. 여기서, Left 와 Middle 의 문자열 각각의 길이를 알 수 있기 때문에 찾고자 하는 문자열이 Left 와 Middle 의 속하는지 확인하고, Left 에 속하면 재귀 호출을 반복하고, Middle 에 속하면 M 인지 O 인지 바로 알 수 있다. 마지막으로 Right 에 속하는 경우는 Left 에 속하는 것과 같다고 볼 수 있으므로, 찾고자 하는 문자의 위치를 Left 와 대칭되는 위치로 변경하..
이분탐색. [2473] [1. 문제 설명] https://www.acmicpc.net/problem/2473 [2. 풀이 접근] 먼저 두 용액의 조합을 모두 찾는다. 이제 각 조합에 대해서 한 용액만 첨가하여 0에 가장 가까워지는 조합을 찾아내도록 한다. 주석 참조 삼분 탐색 (?) [3. 코드]
이분탐색. [2467] [1. 문제 설명] https://www.acmicpc.net/problem/2467 [2. 풀이 접근] 용액을 하나 정한다. 전체에 대해서, 이 용액과 더해서 그 합이 0에 가장 가까워 지는 용액을 이분 탐색으로 찾는다. 용액들이 이미 정렬 된 상태이므로, 이분 탐색 시 두 용액의 합이 0보다 작다면 # 양수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 (mid ~ hi] 구간을 잡아야 한다. 0보다 크다면 # 음수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 [lo ~ mid) 구간을 잡아야 한다. [3. 코드]
이분탐색. [1253] [1. 문제 설명] https://www.acmicpc.net/problem/1253 [2. 풀이 접근] 풀이 시 주의 할점 std::lower_bound 에 대응되는 sort.Search() 는 하한 값 중 가장 먼저 오는 index 를 반환한다. 중복된 값에 대해서도 확인이 필요한 경우, upper_bound 에 해당하는 index 까지 구할 필요가 있다. 즉, [lo, hi) 까지 순차적으로 확인 해 볼 필요가 있다. 시간 복잡도는 O(N^2 logN) 인데, N 의 최대가 2,000 이므로, 현실적인 시간 내에 해결 가능하다. [3. 코드]
최장 증가 부분 수열. [12738] [1. 문제 설명] https://www.acmicpc.net/problem/12738 [2. 풀이 접근] LIS 관련 문제 접근은 보통 아래와 같은 방식으로 진행한다. 완전 탐색 동적 계획법 (완전 탐색에서 부분 문제에 대한 메모이제이션 적용) 완전 탐색 접근법은 아래와 같다. 수열 A[0] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[1] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[2] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 이런 방식을 수열의 끝까지 적용하면 구할 수 있으나, 시간복잡도가 O(2^N) 가 되므로, 길이가 1백만 이상인 수열에 대해서는 현실적인 시간내에 구할 수 없다. 다만 여기서 중복문제가 있다는 것을 인지하면, 메모이제이션을 적용하여 조금 더 빠..
정렬. [10825] [1. 문제 설명] https://www.acmicpc.net/problem/10825 [2. 풀이 접근] 전체 데이터를 구조체 형태고 감싸서 해당 배열을 정렬하는 방식으로 구현 할 수 있지만, 이렇게 할 경우, 불필요한 복사가 발생 하게 된다. 각 데이터를 순서대로 입력받아 각각의 배열에 저장하고, 각 배열 내 데이터를 가리키는 인덱스 배열을 생성한다. 이 인덱스 배열을 정렬하여 구현하도록 한다. [3. 코드]
비트마스킹. [1062] [1. 문제 설명] https://www.acmicpc.net/problem/1062 [2. 풀이 접근] 단어를 읽기 위해서는 적어도 a,n,t,i,c 총 5개의 문자는 가르쳐야 한다. 즉, k-5 개를 가르쳐서, 읽을 수 있는 단어 개수를 최대로 해야한다. 단어에 나오는 문자 위주로 탐색해본다. z 를 포함하는 단어가 없다면, 굳이 z 를 가르칠 필요는 없다. 또, 가장 많이 나오는 문자를 가르쳐서는 안된다. zb q zb 일 때, 한 문자만 가르칠 수 있다면, q를 선택하는게 더 낫다. 조건 중, 단어의 길이는 최대 15 이 중, 5개 문자가 필수 이므로, 최대 10 10개중 선택할 수 있는 경우의 수 중 최대는 대략 10 combination 5 현실적인 시간 내에 모든 경우를 확인 해볼 수 있다...
완전 탐색. [15686] [1. 문제 설명] https://www.acmicpc.net/problem/15686 [2. 풀이 접근] 각 치킨 집에 대해서 해당 지점을 폐업하는 경우와 폐업하지 않는 경우에 대해서 완전탐색을 수행한다. 탐색 중, 남은 치킨 집 개수가 M 개 일 때, 도시의 치킨 거리를 구하며, 남은 치킨 집 개수가 M 개가 아닌데, 더 이상 확인해 볼 치킨 집이 없다면, MAX 값을 반환하도록 한다 [3. 코드]
동적계획법. [9461] [1. 문제 설명] https://www.acmicpc.net/problem/9461 [2. 풀이 접근] 완전 탐색에서 시작한다. 중복되는 부분문제를 파악한다. 메모이제이션을 적용한다. 위 그림에서 가운데 길이가 1인 정삼각형을 P(1) 그 왼쪽 정삼각형을 P(2) P(2) 의 위쪽 정삼각형을 P(3) 로 정의하고, 나선 방향으로 식을 정리하면 아래와 같게 된다. p(1) = 1 p(2) = 1 p(3) = 1 p(4) = p(3)+p(1) = 2 p(5) = p(4) = 2 p(6) = p(5)+p(1) = 3 p(7) = p(6)+p(1) = 4 # p(1)==p(2) p(8) = p(7)+p(3) = 5 p(9) = p(8)+p(4) = 7 p(10) = p(9)+p(5) = 9 p(11) = p(..
이분 매칭. [9576] [1. 문제 설명] https://www.acmicpc.net/problem/9576 [2. 풀이 접근] 이분 매칭으로 접근하는 방법 사람에서 책 으로 연결리스트를 구축 # 이 과정에서 책 번호의 범위에 대한 조건이 반영 된다. 이 상태에서 이분 매칭을 구한다. 탐욕법으로 접근하는 방법 책 번호 범위가 가장 작은 사람 부터 책을 할당한다. # 정당성 입증 필요.. 이분 매칭에서 탐욕법을 적용하는 것이 아니라 이분 매칭 풀이법과 탐욕법으로 해결하는 방법이 있다고 보면 되고, 이분 매칭은 탐색 과정 의미를 알 필요가 있다. [3. 코드] 이분 매칭으로 구하는 방법은 생략.

티스토리툴바