본문 바로가기

알고리즘/Baekjoon

 (196)
우선순위 큐. [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. 코드 - 우선순위 큐]
우선순위 큐. [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. 코드]
부분 합. [2143] [1. 문제 설명] https://www.acmicpc.net/problem/2143 [2. 풀이 접근] 부분 합, 이진 탐색을 조합하여 풀 수 있는 문제이다. 하나의 배열에서 부 배열의 모든 합의 조합은 최대 106 개 이다. 여기서 중복된 값은 제거하면 안된다. 합이 같아도, 부 배열을 이루는 원소가 다르거나, 부 배열을 이루는 원소의 위치가 다르기 때문이다. 즉, 각 경우가 고유한 조합이기 때문이다. 즉, 두개의 배열에서 각 부 배열의 합의 조합은 최대 1012 개 이다. 정답 출력을 위해서는 8byte 크기의 정수형 변수를 사용해야 한다. 중첩 for 문으로 구하면 시간 초과가 발생하니, 좀 더 빠른 탐색을 고민해야 한다. 부분 합 부 배열의 합을 O(1) 에 구할 수 있다. O(N^2) 에 부 ..

티스토리툴바