Hello, Freakin world!

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 해결하는데 굉장히 오래 걸렸습니다. 계속 분할 정복 방식으로 구간을 나눠 최적의 공유기 위치를 설치하려는 방식으로 접근했기 때문인데, 이 방식은 가능함의 여부를 떠나서(아마도 시간 제한에 걸릴 듯) 문제가 굉장히 복잡해지게 합니다. 관점을 살짝 바꿔야 합니다. 실제 수직선 위의 구간을 나눠가면서 공유기를 설치하는게 아니라, 최적화할 값들의 범위의 구간을 나..

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 문제 풀이 얼리 어답터(EA)를 이용해 모든 아이디어를 퍼트리기 위해서는 다음의 규칙이 필요합니다. 1. 현재 노드가 EA인 경우 - 자식 노드가 EA인 경우 - 자식 노드가 EA가 아닌 경우 2. 현재 노드가 EA가 아닌 경우 - 모든 자식 노드가 EA여야 한다. 위의 규칙을 적용해 트리 구조에서 재귀를 이용해 해결할 수 있습니다. 재귀를 이용해 구현할 때, 리프노드에서의 종결 조건과 맞물려서 최소값..

www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 한달 전인가? 너무 어려워서 패스했던 문제였습니다. 그런데 지금은 풀리네요. 풀이가 보였습니다. (오오... 성장해버렸구나) 저는 DP와 비트마스킹을 이용해 풀었습니다. DP 문제를 풀 때 역시 가장 중요한 건 부분 문제를 정의하는 겁니다. arrageStudent(i, previousRowStatus) : 0 ~ i번째 영역에서 이전 행의 상태가 previousRowStatus 일 때 배치할 수 있는 최대 학생 수 위처럼 정..

www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 문제 풀이 모든 지원자 중 자신보다 면접, 서류 분야 점수가 더 낮은 사람이 존재하는 경우 탈락하게 됩니다. 입력이 크기 때문에 N^2 로는 통과할 수 없습니다. 아래의 그림을 살펴보면 힌트를 얻을 수 있습니다. 빨간색으로 체크 친 지원자가 떨어지게 되는데, 해당 포인트는 점선으로 이뤄진 영역에 임의의 포인트를 포함합니다. 먼저 x축으로 입력을 정렬한 후 어떤 포인트를 포함하는 경우는 ..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 바로 전에 LIS 문제를 풀었음에도 한참 헤맸습니다. 기존 LIS 로직을 그대로 쓰려면 입력 배열을 정렬할 필요가 있습니다. 정렬을 하지 않으려면 따로 처리를 해줘야 하는데 이 부분을 간과했네요. 정렬이 필요한 이유는 전깃줄이 꼬이는 조건과 관계가 있습니다. 줄 a,b가 있다고 할 때 줄이 꼬이지 않는 조건은 다음과 같습니다. - a.start b...

www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 이 문제를 계기로 다시 종만북을 펼쳐서 DP를 다시 공부했는데, 새로운 깨달음을 얻을 수 있었습니다. 지금까지 DP 문제를 풀 때, 어떤 유형는 메모이제이션을 이용해 풀어야 되고 어떤 문제는 점화식을 찾아서 바텀업으로 풀어야 된다는 식으로 문제를 분류했었는데 그럴 필요가 없었습니다. 이때까지 바텀업 방식의 풀이를 이용했지만 약간은 불편했습니다. 뭔가 직관적이지 않다라는 느낌을 지울 수 없었기 때문입니다. 그럼에도 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 그래프의 최단 거리 알고리즘을 기반으로 하는 구현 문제입니다. 이 문제의 포인트는 역시 최단 거리의 물고기를 찾고 선택하는 과정에 있습니다. 저도 여기서 한참 헤맸는데요. 문제의 조건을 이렇습니다. 1. 최단 거리의 물고기가 여러 마리일 때, 위쪽에 있는 물고기가 먼저 우선 순위를 가진다. 2. 높이가 같다면 왼쪽에 있는 물고기의 우선 순위가 더 높다. 제가 이 문제에서 헤맸던 이유는 ..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제를 제대로 이해하려면 기존의 기본적인 BFS 개념에 차원을 하나 더해야됩니다. 지도 위에 두 개의 층이 있다고 생각할 수 있습니다. 하나는 벽을 부수지 않은 경로를 표시하는 지도, 하나는 벽을 부수고 이동하는 경로를 나타내는 지도. 아래의 그림을 보면 쉽게 이해할 수 있을겁니다. 대부분의 간단한 BFS 예제들은 행렬 상의 2차원 평면에서 움직이지만, 이 문제는 벽을 부쉈는지 ..

www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA 은 간단하게 트리 구조의 특성을 이용해 단순하게 해결했는데, 이번 문제는 효율성을 고려하지 않으면 풀 수 없었습니다. 영어로 LCA로 검색을 해보면 이 문제에 관해 여러 가지 풀이가 존재한다는 걸 알 수 있습니다. cp-algorithms.com/graph/lca.html Lowest Common Ancestor - O(sqrt(N)) and O(log N) with O(N) preproces..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 트리 구조의 특성을 생각해보면 풀이를 떠올릴 수 있다. 트리 구조에서 하나의 노드는 다수의 자식을 가질 수 있지만 부모 노드를 오직 하나만 가진다. 그렇기 때문에 각 노드에서 부모 노드의 참조를 저장해두면 두 개의 노드에서 따라올라가면서 최소 공통 조상을 찾을 수 있다. 까다로운건 이 문제에서 입력으로 트리를 구성하기 위해서는 일단 양방향 노드 그래프를 만들어야 되는데, 나는 그냥 한번 임시 트리를 만들..