https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 처음 딱 읽었을 때 풀이방법이 떠오르지 않았다. 왜 스택 생각이 안났을까.. 알고리즘 분류를 먼저 보고 풀었다면 고민도 안하고 풀 문제였어서 아쉬웠다.. 풀이방법은 간단하다. 기타의 각 줄마다 스택을 만들어 놓고 새로 누를 줄이 스택의 상단보다 작으면 pop을 해나가는 식으로 체크를 하면 된다. 이미 누르고 있는 프렛이 입력으로 또 주어질 수 있다는 점만 주..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 그래프 탐색 파트의 문제들을 개념부터 차근차근 복기하고 있다. 나이트의 이동은 가장 기본적인 그래프 탐색 문제에서 방향이 8가지로 늘어난것 말고는 다른게 없다. 별다른 제약조건이 없는 상태에서의 최단거리 문제이므로 BFS를 사용했다. 문제 유형에 따라 풀이방법을 나름 정형화 시키고 있다. dx, dy 를 쓴다거나 is_possible의 이름으로 배열 체크 함수를 만든다거나.. 확실히 이정도 수준의 ..
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 브론즈 문제지만 counting sort에 대해 알고있지 않다면 풀 수 없는 문제이다. 리스트의 정렬을 생각하면 우선 그 리스트를 온전히 다 입력받은 상태에서 어떤 정렬 방식을 쓰는 것이 가장 효율적일까를 생각하겠지만 이 문제의 경우 입력값의 개수 N 이 최대 10,000,000이기 때문에 이를 다 입력받으면 메모리 초과가 발생한다. 그렇다면 모든 원소들을 입력받지 않고 정렬을 진행해야 한다는 것인데.. 힌트는 입력..
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 간단한 그래프 탐색 문제. 알고리즘 분류에는 플로이드-와샬 이 포함되어 있는데, 간선 사이 가중치가 없고 i에서 j로 가는 경로가 있는지만 체크하면 되는 문제라 일반적인 DFS로 해결하였다. 인접행렬 형태로 받은 간선 정보를 이용하여 간선이 존재하는 기본 좌표를 [start, now] 형태로 stack에 넣어놓고 stack에서 하나씩 pop해 가며 DFS를 수행한다. 문제를 풀어보면서 아직 BFS보다 DFS 구현이 조금 낯선 느낌이 들었다..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 기본적인 BFS문제. 이전에도 풀어보았지만 코딩테스트 전 점검을 위해 다시 한번 풀어보았다. 확실히 이전보다는 수월하게 해결하였지만 토마토가 하나도 없을 때, 익을 수 있는 토마토가 존재하지 않을 때의 예외 처리 순서가 잘못돼 70~80 퍼센트 대에서 오답이 나왔다. 틀릴만한 부분이 예외처리 밖에 없어서 어렵지 않게 찾을 수 있었지만 코테에서는 한번 말리면 시간을 꽤나 잡아..
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 설명만 보면 무언가 흔히 봤던 문제 같지만 배열이 4개로 나누어져 있다. 거기다 입력값은 최대 4000개까지 가능해서 왠만한 방식으로는 그냥 바아아로 시간초과가 나버린다. 여러 방식들을 시도해 보았으나 가장 마음에 드는 방법은 역시 딕셔너리를 쓰는 거였다. 문제를 풀어볼수록 파이썬에 딕셔너리가 있어서 정말 감사하다~ 는 생각이 들었다. 특정 이분 탐색 문제는 조금만 코드를 ..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이제까지 풀던 이분탐색 문제의 조오금 고급 버전..! 전체적인 구성은 이전의 문제들과 동일하지만 is_possible에서의 조건을 조금 더 구체적으로 분리해 주어야 한다. 사이트에 반례가 많이 없어서 예외처리를 해주는데 시간이 조금 걸렸다. 내 코드가 조금 더러운것 같기도.? 1. lo, hi, mid를 정할때, mid는 배열의 (최대-최소) /..
https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 간단한 이분 탐색 문제인데 문제 조건을 제대로 보지 않았다. 처음에는 틀렸습니다가 계속 뜨길래 bisect의 left와 right에 대해 내가 잘못 생각한 줄 알고 다른 곳을 고치고 있었는데 원인은 그냥 인풋 받고 나서 정렬 안해서 오답이 뜨는 거였다. 문제에 나와있는 테케에는 입력받는 점들이 오름차순으로 되어 있지만 문제 조건에는 입력받는 점들이 정렬된 채로 들어온다는..