자서전

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] + 희원 ..

3줄 요약: DP 난 도대체 왜 팰린드롬을 분할하는 것인지 모르겠다. 어느 문제에서는 유사회문인지를 출력하라 하지 않나, 어느 문제에서는 공장을 개설하지 않나... 팰린드롬은 내가 제일 싫어하는 문제 중 하나이다. 이 문제를 풀 때는 DP를 두 번 사용하여 풀 수 있다. dp[i][j] = i번째 문자부터 j번째 문자까지 회문인지 체크하는 dp dp2[i] = i번째 인덱스에서 분할 개수의 최솟값 dp[i][j]가 약간 이해가 안 갈 수 있는데, 예를 들어보자. 문자열 'BOTTOM' 에서 제일 앞의 인덱스를 1이라고 할 때, dp[1][6]은 false이고, dp[2][5]는 true, dp[3][4]도 true... 이렇게 볼 수 있다. 이를 어떻게 구현할까? dp[i][j] 가 true이고, str..

1949번: 우수 마을 (acmicpc.net) 3줄요약 트리 DP 문제풀이 우리는 문제에서 주어진 3가지 조건들을 만족해나가면서 풀어야 한다. 여기서 우리가 주목해야 할 점은 3번 조건이다. 우리는 약간 생각해보면 3번 조건이 1, 2번 조건에 통합된다는 것을 알 수 있다. 애초에 인접한 마을이 모두 우수 마을이 아니면, 2번 조건이 성립하지 않으므로 그냥 그 마을을 우수 마을로 선정하는 것이 더 이득일 수 있다. 즉, 3번 조건을 만족하지 않는 해가 있다면 그것은 최적의 해가 아니라는 소리다. 이제 진짜 문제풀이로 가보도록 하자. dp[node][a] 를 정의한다. (a = 이 마을을 우수 마을로 설정할 것이면 1, 아니면 0) Top-Down 방식(dfs)로 해결한다: 만약 a가 1이라면, dp[n..

3줄요약 그리디 정렬 구현 서론 하고 싶은 얘기는 없다. 본론 이 문제는 그리디로 풀 수 있다. 사람의 수도 아닌, A 혹은 B에서 떨어진 거리에 대하여 정렬하지 않고, A와 B의 거리의 차가 큰 순서대로 정렬한다. 그리고 정렬한 배열의 i = 0~N-1 에 대해 다음의 4가지 경우를 생각한다. 만약 a가 더 크다면, 그리고 지금 있는 풍선 수로 i번째 인덱스의 팀의 사람들을 충당할 수 있을 때의 경우 a가 더 크지만 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우 b가 더 크고, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 있을 때의 경우 b가 더 크지만, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우 이 경우들에 대해 각각 알맞은 처리를 하면 된다. 코드는 밑에 있다...

3줄요약 그리디 서론 이 문제는 여러모로 함정이 많은 문제이다. 대표적으로, 입력 데이터가 오름차순이더라도 문제에서 따로 명시된 정보가 없으면 정렬해야 한다는 것이다. 아이디어가 굉장히 빨리 떠올랐기 때문에, 10분만에 풀 수 있었다. 본론 우선 먼저 나는 냅색 문제로 접근을 시도했다. 하지만 N

3줄요약 아이디어 최소 스패닝 트리 정렬 서론 이 문제는 최소 스패닝 트리에 아이디어를 결합한 문제이다. 골드 1치고는 매우 어렵다고 생각한다. 본론 N

3줄요약 백트래킹 빡구현 서론 이 문제를 보고 처음에 난감했었다. 이 문제가 어떻게 골드 4인지 모를 만큼 감이 안 잡혔다. 이 문제를 브루트포스로 풀면 최대 O(9^81) 의 시간복잡도가 나오기 때문에, 이 문제는 브루트 포스로 풀 수 없다. 하지만, 백트래킹을 잘 하면 1억번의 연산 밑으로 해결할 수 있다는 생각이 들어 실행에 옮겼다. 본론 이 문제는 사전순으로 앞서는 것을 출력해야 하기 때문에, 체크를 다음의 순서로 해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ... 다음의 순서대로 진행하되, 그 자리에 숫자를 넣었을 때 안되는 경우를 미리 체크해 주면서 백트래킹을 실행하면, 문제가 풀린다. 코드는 밑에 있다. #..

3줄요약 다익스트라 (Similar to KCM Travel, but has lil different) dfs인줄 알았는데 또익스트라 서론 다익스트라 문제이다. 이 문제는 영양가가 넘쳤다. KOI 2016 고등부 2번문제이기도 하고, (나는 중학생이지만) 다익스트라와 기본적인 사고방식을 성장시키기 좋은 문제였다. 본론 기본적인 다익스트라 문제와는 다르게, 이 문제는 다익스트라를 2번 실행해야 한다. 첫 번째로 모든 정점에서부터 j번째 정점으로 가는 최단거리를 구하는 다익스트라, ( 시간복잡도: O(V * E * log(V) ) 두 번째로 첫 번째에서 구한 dist[i][j] 배열을 토대로 1번 정점에서 V번 정점으로 가는 최단거리를 구하는 다익스트라이다. ( 시간복잡도: O (V^2 * log(V) ) ..