목록코딩테스트 (130)
코딩하는 해맑은 거북이
해당 글은 백준 1717번 문제 '집합의 표현'을 다룬다. 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 설명 해당 문제는 그래프의 유니온 파인드 해결법으로 풀 수 있다. 1. N+1 개의 노드에 대해 자기자신으로 부모를 초기화 해준다. 2. union시 더 작은 값으로 부모를 지정해준다. 3. 같은 집합인지 판별하기 위해, 부모를 찾아 비교해준다. 또한, 주의할 점은 재귀한계를 설정해주지 않았더니 ..
해당 글은 백준 14502번 문제 '연구소'을 다룬다. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 설명 해당 문제는 3개의 벽을 세울 수 있는 모든 경우의 수에 BFS를 하여 0의 갯수가 최대인 값을 구하면 된다. 3개의 벽을 세울 수 있는 경우는 조합을 통해 구하고, 새로운 배열에 대해서는 deepcopy 함수를 사용하였다. 코드 from itertools import combinations from collections import deque..
해당 글은 백준 2210번 문제 '숫자판 점프'을 다룬다. 문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 설명 해당 문제는 방문 체크를 하지 않은 DFS로 해결할 수 있다. 중복 방문 가능하므로 방문 체크를 하지 않고, 문자열의 길이가 6이 되면 result에 결과값을 담고 함수를 종료한다. 단, result 배열에는 중복되는 값들이 들어가 있을 수 있으므로 set 함수를 통해 중복을 제거하여 ..
해당 글은 백준 16926번 문제 '배열 돌리기 1'을 다룬다. 문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 설명 해당 문제는 deque의 내장함수인 rotate를 사용해서 해결하였다. 배열의 겉부분 한줄씩 queue에 넣고 rotate 하여 수정된 arr를 출력해주면 된다. 코드 from collections import deque n, m..
해당 글은 백준 2776번 문제 '암기왕'을 다룬다. 문제 https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 설명 해당 문제는 의외로 간단하게 풀 수 있는 문제이다. arr1에는 여러본 숫자도 하나만 저장되면 되므로 list가 아닌 set으로 입력받으면 된다. 처음에 list로 입력받았을 때, 시간초과 에러가 떠서 이분탐색으로 풀어야하나 했지만 중복만 제거하여 간단하게 풀 수 있었다. 코드 T = int(input()) for t in range(T)..
해당 글은 백준 11048번 문제 '이동하기'을 다룬다. 문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 설명 해당 문제는 DP로 해결할 수 있다. DP로 (n, m)까지 3가지 방향으로 이동하면서, 사탕을 가장 많이 가져갈 수 있는 값으로 업데이트한다. 코드 n, m = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input()..