이름 못 정한 블로그

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다. 1 4 3 6 2 5 4 2 3 첫..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고,..

2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액..

오늘은 따로 강의가 있진 않았지만 3시까지 주어진 문제를 푸는 날이었다. 문제를 푸는 것 자체는 그리 어렵지는 않았다. 문제를 풀고나서 더 최적화를 해보려고 했는데 시간이 끝나버렸다... 이런 식으로 문제 푸는걸 많이 안 해봐서 너무 나이브했다. 아마 삼분 탐색을 좀 잘하면 더 높은 점수를 받을 수 있을 것 같았는데, 이제 해볼까하고 자리에 앉았더니 허무하게 코드 배틀이 끝나있었다... 그래도 풀긴 풀었다...

어느새 2주차도 거의 끝나간다. 처음에는 되게 가볍게 생각하고 시작했었는데, 하다 보니 해야 하는 양은 많지만 얻는 것도 꽤 많은 것 같다. 대면일 때는 어떻게 진행했는지 모르지만 대면이었다면 훨씬 재밌었을 것 같다. 오늘은 문제를 한 문제밖에 안 풀었다. 사실 한 문제 더 풀긴해야 한다. 그런데 문제가 파일 시스템을 구현하는 문제라 너무 하기가 싫었다. 학기 중에 핀토스 프로젝트를 하면서 한번 지나온 내용이라 차마 시작할 수가 없었다. 나중에 여유가 생기면 하든지 해야겠다.

17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. ..

오늘은 트리에 관한 내용이었다. 오늘은 강의도 몇 개 있었다. 연구실에서 빌드 돌리면서 강의보고 문제도 풀었다. 오늘은 3문제를 풀었는데 모두 그리 어려운 문제는 아니었다. 거의 다 개념을 묻는 문제여서 쉽게 풀 수 있었다. 그런데 문제의 내용은 쉬웠는데 조건을 맞추는 게 그리 쉽지 않았다. 내가 생각하기에 필요 없는 입력도 받아야만 했다. 백준에서 문제를 풀 때는 내가 보통 풀이수가 많은 문제를 풀다 보니 이미 다녀간 사람들이 오류를 많이 수정해놨는데 SWEA에서는 내 눈에도 이상한 게 몇 개 있다. 오류라고는 할 수 없겠지만 백준에 비해 가독성이 조금 떨어진다. 그래도 프로그래머스처럼 바로 결과 볼 수 있는 건 좋은듯하다 내일 수강신청 담아놓기라서 급하게 시간표를 짰는데 시간표 짠 이후부터 뭔가 정신..

11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 문제 각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다. 트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다. 아래 그림은 노드 9개로 이루어져 있는 3진 트리이다. 노드의 개수 N과..

11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다..

어제에 이어서 같은 내용으로 문제를 풀었다. 오늘은 총 3문제를 풀었다. 첫 번째 문제는 BFS에 관련 문제였다. 그런데 BFS를 구현하는 것이 중요하지는 않았다. 나는 LCA 알고리즘이 뭔지도 모르는 상태로 문제를 풀기 시작했는데, 두 시간 정도 붙잡고 있었음에도 문제를 푸는 게 쉽지 않았다. BFS 과정을 진행하면서 문제를 해결하려고 했었는데 그리 쉽게 되지 않았다. 게시판에도 나 같은 사람이 있길래 글을 확인해보니 LCA 알고리즘을 사용해보라는 댓글이 있어서 냉큼 LCA 알고리즘을 찾아봤다. 진짜 야무진 알고리즘이었다. 내가 구질구질하게 구현하려고 했던 알고리즘이 아주 깔끔하게 구현되어 있었다. 나는 O(logn)의 방법을 상상하지도 못했는데 세상에 똑똑한 사람들 진짜 많다. 백준에서 LCA 알고리..