목록코딩테스트 (130)
코딩하는 해맑은 거북이
해당 글은 백준 1992번 '쿼드트리' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 설명 처음에는 nxn 행렬을 모두 탐색하다가, (0, 0)의 값과 다르다면 4개로 나누어서 재탐색하는 분할정복 알고리즘으로 해결하였다. 주의할 점은 if문에 return으로 4분할로 재귀 후 종료할 수 있도록 해야한다. 코드 n = int(input()) arr = [list(map(int, input())) for _ in..
해당 글은 백준 1966번 '프린터 큐' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 설명 해당 문제는 리스트의 인덱스를 이용해서 간단하게 풀 수 있는지 알았지만, 3번째 테스트케이스를 진행하면서 중요도가 같은 문서들로 인덱스 접근은 어렵다고 느꼈다. 따라서 큐의 rotate와 popleft를 이용하여 해결하였다. 현재 큐의 0번째가 max 값이 아니라면 왼쪽으로 한 칸씩 회전시키고, max 값이라면 popleft를 하고 ..
해당 글은 백준 15652번 'N과 M (4)' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 1에서 N까지의 M개의 고른 수열을 구하는 문제이다. DFS로 1~4개의 숫자로 2개의 고른 수열을 고른다고 하면, 첫번째 수가 1일 때 1~4, 2일 때 2~4, 3일 때 3~4, 4일 때 4까지의 값을 출력해야 한다. 리스트에 for문을 이용해서 수를 추가해주고, 리스트의 갯수가 2개가 아니라면 수를 추가해서 DFS를..
해당 글은 백준 1343번 '폴리오미노' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 설명 해당 문제를 split으로 해결할 방법만 생각했었는데, 다른 사람의 코드를 통해 replace를 통해 엄청 간단하게 해결한 것을 보고 감탄하였다. replace로 'AAAA' 먼저 후, 'BB'를 진행하면 사전순으로도 가장 앞서므로 문제없이 해결할 수 있다. 코드 board = input() board = board.replace('XXXX', 'AAAA') board = board.replace('XX', 'BB') if 'X' i..
해당 글은 백준 12852번 '1로 만들기 2' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 설명 해당 문제는 DP로 간단하게 해결할 수 있는 문제인데, 순서도 같이 출력해주어야 하는 게 새로웠던 것 같다. 이를 위해 dp 리스트를 만들 때, 순서도 같이 저장할 수 있는 빈리스트도 추가하여 선언해주었다. DP로 최소값을 구하는 부분에 순서도 같이 저장해주는 부분만 추가해주면 된다. 코드 n = int(input()) dp = [[0, []] for _ in range(n+1)] dp[1][0] = 0 dp[1][1] = [1..
해당 글은 백준 4485번 '녹색 옷 입은 애가 젤다지?' 문제를 다룬다.문제https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지?젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주www.acmicpc.net 설명(0, 0)에서 (n-1, n-1)까지 이동할 때 최소 비용으로 가야하므로 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다. 이때 주의할 점은 heapq를 사용하므로 heappush할 때 비용이 먼저 위치하도록 한다! 코드import heapq dx = [-1, 1, 0, 0] dy = [0,..