몽상실현개발주의

[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,..

[BOJ] 1654 / 랜선 자르기 / Python 파이썬 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색의 기본 문제이다. 첫 시도는 완전 탐색으로 접근하였지만 당연히 시간초과가 발생 하였다. 가장 기본적인 이분 탐색의 구조로 해결 하였다. import sys input = sys.stdin.readline K, N = map(int, input().split()) lines = [] for _ i..