본문 바로가기

알고리즘

 (401)
최장 증가 부분 수열. [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. 코드] 이분 매칭으로 구하는 방법은 생략.
이분매칭. [2188], [11375] [1. 문제 설명] https://www.acmicpc.net/problem/2188 https://www.acmicpc.net/problem/11375 [2. 풀이 접근] 각 그룹에 속한 정점 번호는 1부터 시작이므로, 배열의 크기는 각각 N+1, M+1 이 되어야 한다... 문제 11375 에 경우 인접 행렬은 1000x1000 크기의 배열이 필요하다. (dfs 시간복잡도) 인접 리스트가 좀 더 효율적이다. 속도 향상을 위해 다른 알고리즘을 적용할 수 있다. [3. 코드] [3-1. 코드]
동적계획법. [11727] [1. 문제 설명] https://www.acmicpc.net/problem/11727 [2. 풀이 접근] 놓아야 하는 블록은 3가지 유형이 존재한다. 1*2 유형의 블록은 항상 같은 블록을 쌍으로 배치할 수 밖에 없다. 2*2 유형의 블록은 1*2 유형의 블록을 배치하는 경우와 같은 경우로 볼 수 있다. 위 두가지 블록을 배치하려면 적어도 남은 직사각형의 길이가 2 이상이 되어야 한다. 경우의 수를 따지는 문제로, 재귀의 종료조건 달성 시, 한가지 경우를 달성한 것이며, 이 때, 그 경우의 수 1을 반환하도록 한다. 부분 문제는 어떤 블록을 배치 시, 남은 직사각형을 어떻게 배치 할 지 결정하면 된다. f(n) = f(n-1) + 2*f(n-2) [3. 코드]
네트워크 유량. [11405] [1. 문제 설명] https://www.acmicpc.net/problem/11405 [2. 풀이 접근] [3. 코드]
이분 탐색, 하한 / 상한 값 탐색 [1. 개요] 정렬 된 배열에 같은 값을 갖는 원소가 여러 개일 경우 단순한 이분 탐색은 찾고자 하는 값에 해당하는 인덱스 중 가장 앞서는 값을 준다고 보장 할 수 없다. 물론, C++ 기준 std::lower_bound, upper_bound 를 사용하면 가능하겠지만, vector 사용 없이, 단순 배열을 대상으로 lower_bound, upper_bound 에 해당하는 기능 구현에 관한 내용을 정리한다. [2. 하한 / 상한] 하한 값 : 대상 값보다 같거나 작은 값 중 가장 큰 값 상한 값 : 대상 값보다 큰 값 중 가장 작은 값 최소값, .... 하한 값 ≤ 대상 값...

티스토리툴바