자서전

5626번: 제단 (acmicpc.net) 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 시간 복잡도: O(N * H/2) 알고리즘: DP 말이 꼬여있어서 어렵습니다. 하지만 보면, i번째 제단과 i-1번째 제단 혹은 i+1번째 제단의 차이는 1 이상 날 수 없습니다. 이는 계단 수 문제랑 비슷한데, 변형되었습니다. 조건은 다음과 같습니다. 시작은 0이여야 합니다. 따라서 1번째 제단의 입력이 0 혹은 -1이 아니라면, 바로 0을 출력합니다. 끝 또한 0이여야 합니다. i번째 제단이 -1이 아닌 경우 i 빼고 모든 값을 0으로 초기화합니다. i번째 제단을 j로 설치하는 경우의 수는 i-1번째를 j, j+1, j-1로 설치하..

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (acmicpc.net) 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 시간 복잡도: O(Nlog^2N) 알고리즘: 트리의 순회; 중위 순회 DP 이 문제는 생각을 잘 하면 풀리는 것 같습니다. 먼저 하나의 문제를 예시로 들겠습니다. 정수 리스트 S가 주어졌을 때, 연속 최대 부분 합을 구하는 것입니다. 이게 무슨 소리냐면, 연속한 ..

1. Barn Painting (G1) - From. USACO 2017 December Contest Gold 2번 시간 복잡도: O(N) 알고리즘: 트리 DP 말할 것 없는 간단한 트리 DP 문제입니다. DP 테이블을 다음과 같이 둡시다: ≫ dp[i][j] = i번째 노드를 j 색으로 칠할 때 경우의 수 이때, 현재 노드에 대해서 경우가 2가지 있고, 현재 노드에 연결된 노드에 대해 3가지 경우가 있습니다. 우선 현재 노드에 대한 경우를 봅시다. N-1. 이미 색이 안 칠해진 경우 N-2. 이미 색이 칠해진 경우 그리고, 연결된 노드에 대한 경우를 봅시다. I-1. 이미 색이 안 칠해진 경우 I-2. 이미 색이 칠해졌는데, 현재 노드와 색이 다른 경우 I-3. 이미 색이 칠해졌는데, 현재 노드와 색..

13907번: 세금 (acmicpc.net) 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 시간 복잡도: O(N^2logN + NK) 알고리즘: 다익스트라 최적화 예제 힌트를 보고 깨달으셨을 것입니다. 이 문제는 일반적인 최단 거리 알고리즘으로 풀어서는 안 됩니다. 따라서 저희는 이렇게 접근할 수 있습니다: "최단거리가 바뀌는 조건은 무엇일까?" 최단거리가 바뀌는 조건을 한 번 찾아봅시다. 힌트에서 보듯, 세금이 j만큼 인상할 때마다, ..

중간고사가 다가오네요. 그 와중에 PS를 하고 있습니다. 1. 숫자 박스 (G2) - KOI 2003 고등부 2번 시간 복잡도: O(N^3) 알고리즘: DP Only DP 문제입니다. dp 테이블을 다음과 같이 나타냅시다. ≫ dp[idx][a][b] = idx까지 숫자를 설치했을 때, 1번째 줄의 박스를 a개, 2번째 줄의 박스를 b개 설치했을 때 최댓값 4가지 방법이 있습니다. 1번째 줄에 a번째 박스만 설치하기 2번째 줄에 b번째 박스만 설치하기 둘 다 설치 안하기 둘 다 설치하기 여기서 3번째 경우는 항상 손해이므로 배제해서, dp 테이블을 채워나갑니다. 예외 처리를 많이 해주어야 하는 것이 포인트입니다. 더보기 #include #include using namespace std; #define ..

1. Cow Contest (G4) - From. USACO January 2008 Contest Silver 1번 시간 복잡도: O(N^2) 알고리즘: DFS 그래프 문제입니다. 순위를 특정하려면, 앞에 있다고 확신할 수 있는 소의 수와 뒤에 있다고 확신할 수 있는 소의 수가 전체 소의 수에서 1을 뺀 값이 되어야 합니다. 예를 들어, { (1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (6, 4), (6, 1) } 의 입력이 주어졌을 때, node 번호를 가진 소 뒤에 있는 소들의 관계는 다음과 같습니다: 여기서 node 번호가 붙은 소 뒤에 있는 소의 수는 dfs를 통해 쉽게 구현할 수 있습니다. 또한, 앞에 있는 소들의 관계는 간선의 방향을 뒤집어 다시 dfs로 탐색합니다...

5419번: 북서풍 (acmicpc.net) 좌표 압축 + 세그먼트 트리 + 스위핑으로 풀 수 있는 문제이다. 만약 i번째 점이 좌표 (xi, yi)에 있다고 하자. 그렇다면, i번째 점으로 항해할 수 있는 점들은 yi보다 y좌표가 높고, xi보다 x좌표가 낮은 점들의 집합인 것이 자명하다. 여기서 xi보다 x좌표가 낮은 점들은 스위핑을 하며 자동적으로 구해지고, yi보다 y좌표가 높은 점들은 세그먼트 트리로 구할 수 있다. 우리는 X 좌표순으로 오름차순 정렬, 같다면 Y 좌표로 내림차순 정렬하면 스위핑을 할 수 있는 상황이 만들어진다. 정렬 순서대로 쭉 훑어나가면, i번째 좌표 기준으로 갱신된 점의 좌표는 xi보다 왼쪽에 있는 점들밖에 갱신이 안 되었기 때문에, 그저 yi보다 높은 좌표를 가진 점들만 ..

14572번: 스터디 그룹 (acmicpc.net) 14572번: 스터디 그룹 첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 105, 1 ≤ K ≤ 30, 0 ≤ D ≤ 109) 이어 N명의 학생에 대한 정보가 아래와 같이 주어진다. M d (0 ≤ M ≤ K, 0 ≤ d ≤ 109): 해 www.acmicpc.net 이 문제는 그리디 + 투 포인터로 풀 수 있다. 임의의 그룹원 집합 알파에 대해 "그룹 내에서 가장 잘 하는 학생과 가장 못 하는 학생의 실력 차이가 D 이하여야 한다." 가 성립하는 그룹원 A 를 더한 집합이, 집합 알파보다 항상 효율성이 크므로, 이 로직으로 풀 수 있다. 그냥 하면 시간초과가 나니, 정렬과 투포인터를 사용해 O(NK) 에 풀..

제목에서 알 수 있듯이, LIS 문제를 O(N log N)의 시간복잡도로 세그먼트 트리를 이용하여 풀 수 있다. 예제로 9 9 5 4 6 1 3 7 10 2 라는 입력이 주어진다고 해보자. 여기서 LIS는 무엇일까? LIS = { 5, 6, 7, 10 }, 혹은 { 4, 6, 7, 10 }, 혹은 { 1, 3, 7, 10 } 등으로, 길이는 4이다. 우리는 만약에 N >= 10,000 이상의 입력이 들어온다면, O(N^2)의 dp 알고리즘으로는 풀 수 없으므로, O(N log N) 의 풀이를 알아야 한다. 그리고 우리는 세그먼트 트리를 활용한 구간 최댓값을 구하는 것으로 이를 풀 수 있다. 예제를 예로 들겠다. 배열 요소가 저장된 배열을 S라 할 때, S는 다음과 같이 표현된다. S 9 5 4 6 1 3..

https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 난이도(객관적): Platinum V 난이도(개인적): Gold I (BOJ 2618 하위호환) 문제 난이도도 환상인 문제이다. 이 문제는 dp를 사용하여 풀 수 있는데, dp 테이블을 다음과 같이 나타내면 된다. dp[i][j] = 상덕이가 현재 i번째 인덱스, 희원이가 j번째 인덱스에 있을 때 드는 힘의 최솟값 일 때, dp[i][j] = min( dp[i][max(i, j) + 1] + 희원 ..