https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 보자마자 DP인건 알겠는데, 1시간동안 고민해도 답이 안보여서 풀이 아이디어를 보고 푼 문제이다. 이 문제는 내가 한번도 풀어본 적 없는 유형의 문제였다. 처음에는 '9876543210' 이라는 기본 틀에다가 앞뒤로 숫자를 붙이는 걸 고민했다. 당연히 뻘짓이었다 ㅋㅋ 12부터는 98767543210 이런식으로 기본틀 사이에 숫자가 들어갈 수 있기 때문이다. 이게 뻘짓이라는 걸 깨닫기까지 40분이 걸렸다.. 그 다음으로는 구간DP를 떠올렸다. 길이가 i 이고 첫숫자가 j 마지막 숫자가 k 인 수의 개수 이런식으로 DP를 ..
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 분리집합 + 그래프 탐색 문제이다. 주어진 입력에서 연결요소의 개수를 세면 된다. 같은 연결요소인지 아닌지 구분하기 위해 나는 분리집합을 사용했는데, 2차원 분리집합 구현은 처음이라 조금 애를 먹었던 것 같다. 그냥 단순무식하게 튜플을 있는 그대로 비교했는데, 다른 방법도 있을 것 같다. 내가 사용한 알고리즘 1. 모든 배열을 순회하면서 아직 방문하지 않은 노드..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 사이클에 속하지 않는 노드의 개수를 세는 문제이다. 생각보다 최적화를 깐깐하게 요구했던 문제이다. 하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다. 살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ (21.12.17 오전 10시 30분 기준) 물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ 이 문제의 알고리즘 분류는..
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다. 다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다. 물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다. 처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데, 혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다. 그리고 시간차이는 내장 자료형을 쓰는 편이 ..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다. (그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.) 펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다. 어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다. 따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면 dp[s][e] = dp[s+1][e-1] + 2 이다. 단, 위 점화식의 조건은 dp[s+1][..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 응용한 단순 구현문제이다. 내가 푼 알고리즘은 다음과 같다. 1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고, 문은 맵에 문 위치를 저장한다. (이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.) (열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.) 2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다. 문을 열..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 자료구조를 사용하는 그리디 문제이다. 우선해야하는 조건이 2개가 엮여 있어서 난이도가 있는 문제였다. 나는 그리디 알고리즘 강의를 다시 복습해서 보고나서 아래와 같은 사고로 문제를 풀었다. 결국 그리디도 최적해를 구하는 알고리즘 중 하나인데, 이 문제에서 구해야하는 것은 '보석 가치 합의 최대'이다. 그렇다면 일단 보석의 가치만 놓고보면..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다. 아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ 얼떨떨한 기분으로 푼 문제, '도시분할계획'이다. 이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다. 처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나..
