[백준] 1717번 집합의 표현 파이썬 풀이
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 접근 방식 union-find 방식 인덱스를 원소 값으로 갖는, 길이 (n + 1)짜리 리스트를 생성한다. 인덱스가 3이라면, 인덱스 3은 정수, list[3]은 해당 정수가 속한 집합을 의미한다. 따라서 정수 1과 3을 합치고, 정수 4와 5를 합치면 리스트는 위와 같아진다. 이처럼 여러 숫자(노드)가 있고, 두 개의 숫자를 선택하여 두 개가 같은 집합..
[백준] 1992번 쿼드트리 파이썬 풀이
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. 접근 방식 문제 해결 흐름을 대략적인 슈도 코드로 파악하자. 1. is compressible? 2. if so, print 1 or 0 3. else, a. print ( b. split into 4 c. then go back to 1 d. print ) 코드를 작성하기 전에 먼저 문제를 읽으며, 어떤 흐름으로 코드를 작성해야 하는지 정리했다. 가장 먼저 압축 가능 여부를 파..
[백준] 1074번 Z 파이썬 풀이
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 접근 방식 방문하는 r행 c열이 위치하는 사분면에만 집중하자. N = 3, r = 7, c = 7일 때를 예시를 들면 다음과 같다. 7행 7열은 첫 번째 그림에서 제 4사분면에 위치한다. 따라서 나머지 제 1, 2, 3사분면에 있는 임의의 칸을 몇 번째로 방문하는지는 알 필요가 없으며, 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 사실만 중요하다. 재귀를 통해 제 4사분면..
[백준] 1991번 트리 순회 파이썬 풀이
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 방식 왼쪽 자식, 오른쪽 자식을 가지는 Node 클래스를 구현하자. 배열로 이진 트리를 표현하는 것보단 실제 이진 트리와 비슷하게 구현하는 편이 더 수월할 것이라고 생각했다. 따라서 실제 이진 트리의 노드처럼 왼쪽 자식, 오른쪽 자식을 갖는 Node 클래스를 작성했다. 딕셔너리로 트리를 표현하자. key는 해당 노드의 value, value는 해당 노드 인스턴스를 저장한다. ..