본문 바로가기

알고리즘

 (405)
우선순위 큐. [7662] [1. 문제 설명] https://www.acmicpc.net/problem/7662 [2. 풀이 접근] map 을 이용한 풀이와 우선순위 큐를 이용한 풀이가 있다. map 을 이용한 풀이 STL map 은 begin(): 최소, rbegin(): 최대가 됨을 이용한다. 우선순위 큐를 이용한 풀이 주의 점, min_int 에 - 부호 사용 시 overflow 발생으로 인한 오답 발생 -std::numeric_limits::min() max() 는 오버플로우 발생 안함... [3. 코드 - map] [3. 코드 - 우선순위 큐]
문자열 - kmp 알고리즘 [1. 개요] 문자열 검색 문제 문자열 H 가 문자열 N 을 부분 문자열로 포함하는지 확인 포함한다면, N 과 일치하는 부분 문자열의 시작 위치를 찾는 문제 N 이 H 에서 여러 번 출현한다면, N 이 출현하는 모든 위치를 반환해야 한다. 단순한 탐색 알고리즘의 경우 시간 복잡도는 O(|N| x |H|) 로, 입력되는 문자열의 길이가 매우 긴 경우(그리고 특정 형태의 입력에 대해서), 꽤나 비효율적인 알고리즘 이지만, 현실적인 경우에서 그런 경우는 흔하지 않다. KMP 알고리즘은 검색 과정에서 얻는 정보를 버리지 않고 활용하여, 동일한 문제에 대한 시간복잡도를 O(|N| + |H|) 로 상당히 개선할 수 있다. [2. 알고리즘 원리] KMP 알고리즘의 아래와 같은 특성을 이용한다. H[i...] 에서 N..
우선순위 큐. [1202] [1. 문제 설명] https://www.acmicpc.net/problem/1202 [2. 풀이 접근] 카테고리는 우선순위 큐를 이용해서 푸는 방법이지만, map 을 이용해서 풀 수 도 있다. map 을 이용한 풀이 기본적인 전략은 아래와 같다. 훔친 보석의 가격을 최대로 해야 하므로, 보석 가격 순을 내림차순 정렬 후, 하나 씩 가져가는 방식이다. 이 때, 보석 무게가 도둑이 갖고 있는 가방 들 중 어느 하나에 포함될 수 있어야 한다. 이 때 이분 탐색을 위해, 가방 무게 역시 오름차순으로 미리 정렬 되어 있어야 한다. 그래서 보석을 기준으로 iterate 하면서 보석을 선택적으로 취해 나가는 것이다. 단) 여기서 아래와 같은 문제가 있다. 이번 보석을 어느 가방에 넣었으면, 이 가방은 다음 탐색에서..
트리-DP. [1949] [1. 문제 설명] https://www.acmicpc.net/problem/1949 [2. 풀이 접근] 처음에는 완전 탐색 형식으로 풀어보고, 메모이제이션 해서 최적화 하는 방법으로 접근해보려 했는데, 이 때, 문제에서 조건 중 3번 조건을 다루기가 많이 까다로웠다. root 가 선택되지 않았을 때, 적어도 하나의 자식은 우수 마을로 선정되어야 한다. 자식 노드의 개수가 4 개일 때, 전체 경우의 수는 (2^4-1) 개 이다. # 전체 경우의 수에서, 모두 우수 마을이 아닌 경우를 뺀 개수 자식 노드의 개수가 늘어나면 지수 형태로 경우의 수가 늘어나므로, 적절한 풀이가 아니다. 찾아보니 일반적인 풀이는 아래와 같다. 부분 문제를 다음과 같이 정의 # 어떤 노드를 root 로 하는 서브 트리에서 최대 주..
트리. [2533] [1. 문제 설명] https://www.acmicpc.net/problem/2533 [2. 풀이 접근] 문제 조건에서 주어지는 그래프는 트리 형태이다. 어떤 노드에서 인접한 모든 노드가 얼리 어답터일 때만, 이 노드 역시 얼리어답터가 될 수 있다. leaf 노드인 경우, 이 노드가 얼리어답터가 될 수 없다. 트리에서 노드는 최소 2개 이상이다. Left - Root - Right 인 구조에서, Left 를 얼리어답터로 선정한다면, Right 역시 얼리어답터로 해야한다. => Root 만 얼리어답터로 선정하는 것이 더 낫다. 그래서, Leaf 노드 역시 얼리어답터가 되려면, Leaf 에 유일하게 연결되는 Parent 가 얼리어답터가 되어야 한다. Leaf 및 parent 를 얻기 위한 트리 구성 임의의 ..
트리. [2250] [1. 문제 설명] https://www.acmicpc.net/problem/2250 [2. 풀이 접근] [3. 코드]
스택. [1918] [1. 문제 설명] https://www.acmicpc.net/problem/1918 [2. 풀이 접근] 피연산자가 먼저오고, 연산자가 마지막에 오는 구조, 연산자 우선순위에 따라, 먼저 온 연산자 처리가 결정된다. 코드 주석 참조 [3. 코드]
스택. [2493] [1. 문제 설명] https://www.acmicpc.net/problem/2493 [2. 풀이 접근] [3. 코드]
스택. [10799] [1. 문제 설명] https://www.acmicpc.net/problem/10799 [2. 풀이 접근] [3. 코드]
이분탐색. [3020] [1. 문제 설명] https://www.acmicpc.net/problem/3020 [2. 풀이 접근] 이분 탐색을 이용한 풀이 => 코드 참조 부분 합을 이용한 풀이 장애물 별 높이에 대해서 해당 높이를 갖는 장애물이 몇개인지 저장 할 수 있다. H 는 최대 500,000 이므로, 1,000,000 개의 메모리 확보 가능 이분 탐색을 이용한 풀이와 마찬가지로 접근 해 볼 수 있다. 구간 합을 이용해서 어떤 높이 r 부터 H 까지 총 몇개가 있는지 확인 할 수 있다. [3. 코드]

티스토리툴바