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/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제도 방향이 8가지로 늘어났다는 점만 제외하고는 아주 기본적인 문제였다. DFS와 BFS 모두 가능하지만 최근에 너무 BFS만 사용한것 같아 이번엔 DFS로 코드를 짜봤다. import sys sys.stdin = open('input.txt', 'r') sys.setrecursionlimit(10**6) dy = (0,1,0,-1,1,1,-1,-1) dx = (1,0,-1,0,-1,1..
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이기 때문에 이를 다 입력받으면 메모리 초과가 발생한다. 그렇다면 모든 원소들을 입력받지 않고 정렬을 진행해야 한다는 것인데.. 힌트는 입력..
지난주 코딩 테스트를 보는데 숫자로 이루어진 한 집합이 다른 집합의 부분집합에 해당하는지 여부를 파악해야 하는 문제가 있었다. 인터넷 검색이 허용되는 시험이어서 다행히 바로 검색해 해결했지만 이정도 함수들은 외워두는게 좋을 것 같아서 이렇게 다시 한 번 정리하게 되었다. 1. 합집합 (Union) 집합 연산에서 합집합에 해당하는 함수는 set.union과 OR연산자 |가 있다. a = {1, 2, 3, 4} b = {3, 4, 5, 6} print(set.union(a, b)) # {1, 2, 3, 4, 5, 6} print(a | b) # {1, 2, 3, 4, 5, 6} 2. 교집합 (intersection) 교집합 연산은 AND 연산자 & 또는 set.intersection 메서드를 사용한다. a ..
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 구현이 조금 낯선 느낌이 들었다..