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의 이름으로 배열 체크 함수를 만든다거나.. 확실히 이정도 수준의 ..
정렬 알고리즘은 단골 면접 질문이다. 최근에 본 면접에서도 특정 정렬 알고리즘에 대해 설명해 보라는 질문을 받았다. 학교 수업 때나 코테 준비를 하면서 여러 가지 알고리즘을 접해 보았고 전반적으로 이해는 하고 있지만 막상 면접 때 일목요연하게 답하려 하니 만만치 않았다. 그래서 이번에 한꺼번에 다시 정리를 하면서 면접 때 답변한 방식도 대강 정해 놓으려 한다. 1. 거품 정렬 Bubble Sort 시간복잡도: O(n^2) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 각 리스트를 한 번씩 훑을 때마다 가장 끝 자리의 원소는 정렬에서 제외된다. 각 회전마다 하나의 원소씩 제외하고, 각 원소의 길이 -1(두 개씩 비교하기 때문) 만큼 회전을 반복하기 때문에 ..
백준 문제를 풀다가 계수 정렬에 대해 알게되었다. 상황에 따라서는 상당히 매력적인 배열 방식인 것 같다. 원리는 간단하다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] 라는 리스트가 있을 때, 리스트를 차례대로 돌면서 해당 원소가 몇 번 나왔는지 체크하면 된다. 코드로 살펴보면 다음과 같다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] cnt = [0 for _ in range(8)]# A에서 나올 수 있는 원소의 최댓값 + 1 for a in A: cnt[a] += 1 print(cnt) # [0, 1, 1, 3, 2, 1, 1, 1] for i in range(1, 8): for _ in range(int(cnt[i])): print(i, end= ' ') # ..
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개까지 가능해서 왠만한 방식으로는 그냥 바아아로 시간초과가 나버린다. 여러 방식들을 시도해 보았으나 가장 마음에 드는 방법은 역시 딕셔너리를 쓰는 거였다. 문제를 풀어볼수록 파이썬에 딕셔너리가 있어서 정말 감사하다~ 는 생각이 들었다. 특정 이분 탐색 문제는 조금만 코드를 ..