몽상실현개발주의

[BOJ] 11729 / 하노이 탑 이동 순서 / Python 파이썬 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 유명한 하노이의 탑 문제를 부할정복으로 푸는 문제이다. 마지막 원판을 3번 장대로 옮기기 위한 방법은 다음과 같다. 마지막 원판을 제외한 원판을 2번 장대로 옮기기 마지막 원판을 3번 장대로 옮기기 2번 장대의 모든 원판을 3번 장대로 옮기기 그리고 마지막 원판을 옮기기 위해서는 그 이전의 원판들의 작업이 진행..

[BOJ] 1780 / 종이의 개수 / Python 파이썬 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 풀이 [BOJ] 1992 / 쿼드트리 문제의 심화 문제이다. 쿼드트리에서는 주어진 2차원 배열을 2x2 분할 하였다면, 이번 문제에서는 3x3으로 분할 하여 해결 하였다. import sys input = sys.stdin.readline N = int(input()) maps = [] for _ in range(N): maps..

[BOJ] 1992 / 쿼드트리 / Python 파이썬 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할정복의 기본적인 문제이다. 재귀를 이용하여 가장 작은 부분문제를 해결하는 것으로 전체의 문제를 해결 할 수 있었다. 전체가 같은지 조건을 검사 조건에 부합하지 않다면, 1 - 2 - 3- 4 분면으로 나누기 나눠진 4분면들을 각각 검사 조건에 부합하지 않다면, 1 - 2 - 3- 4 분면으로 나누기 부분 문제가 가장 작은..

[BOJ] 11728 / 배열 합치기 / Python 파이썬 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 주어지는 두 배열을 합쳐 정렬하는 문제이다. 파이썬에서 제공되는 sort() method 로 쉽게 해결하였다. N, M = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split()))..

[BOJ] 10816 / 숫자 카드 2 / Python 파이썬 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 [BOJ] 10815 / 숫자 카드 문제의 응용 문제이다. 처음 시도로는 해당하는 카드의 index 를 이분탐색을 진행하여 찾고, 그 index 를 기준으로 앞뒤를 탐색하는 방법을 구상하였지만 시간초과가 되어버렸다. 그 다음으로는 index 를 시작 숫자로 하여 다시 이분탐색을 하는 방법을 사용 ..

[BOJ] 10815 / 숫자 카드 / Python 파이썬 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 주어진 숫자만큼 이분탐색을 연속으로 하는 문제이다. for 문 안에서 이분탐색을 진행하여 간단하게 풀었다. N = int(input()) cards = list(map(int, input().split())) cards.sort() M = int(input()) nums = list(map(int, in..

[BOJ] 2110 / 공유기 설치 / Python 파이썬 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 풀이 방법을 떠올리기가 힘들었던 이진탐색 문제였다. "공유기 사이의 거리를 최대로 하는 설치 간격" 을 찾는 문제인데 이 조건을 "집 사이의 간격이 X 이상이 가능한 집의 수 == 공유기 대수" 로 다시 생각하여야 풀 수 있었다. 집 사이의 간격을 이진탐색으로 찾기 간격을 주어진 집..

[BOJ] 2805 / 나무 자르기 / Python 파이썬 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진탐색의 기본 문제이다. 주어진 나무의 높이들을 빼주면서 결과를 비교하여, 탐색 범위를 좁혀 주는 방식으로 이진탐색을 하였다. res = M : 자를 높이 증가 N, M = map(int, input().split()) trees = list(map(int,..