다차원 배열
2563. 색종이
색종이
분류: 구현
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
코드
# 100x100의 0으로 이루어진 2차원 리스트
entire = [[0 for _ in range(100)] for _ in range(100)]
x_max = 0
for _ in range(int(input())):
x, y = map(int, input().split())
x_max = max(x_max, x + 10)
for i in range(x, x + 10):
for j in range(y, y + 10):
entire[i][j] = 1
answer = 0
for i in entire[:x_max]:
answer += sum(i)
print(answer)
설명
- 0으로 이루어진 100x100의 2차원 리스트를 평면상의 x, y 좌표라고 생각
- 입력받은 x, y부터 x+10, y+10 까지의 2차원 리스트의 원소를 1로 변경
- 리스트의 1의 값들을 모두 더하면 검은 영역의 넓이를 구할 수 있다.
- x_max를 사용하는 이유
이중 for문을 사용할 때 x를 상위 반복 변수로 사용했기 때문에 프롬프트에서는 아래와 같은 방향으로 데이터가 입력
x행을 기준으로 반복문이 진행되기 때문에 x_max값만 따로 저장하여 100x100의 전체 리스트를 모두 반복하지 않고 1의 값이 존재할 수 있는 마지막 행인 x_max까지만 반복
2566. 최댓값
최댓값
분류: 구현
9×9 격자판에 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.
최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.
코드
table=[]
max_num = 0
for _ in range(9):
line = list(map(int,input().split()))
table.append(line)
max_num = max(max_num, max(line))
for i in range(9):
for j in range(9):
if table[i][j]==max_num:
print(max_num)
print(i+1, j+1)
break설명
- table 리스트에 입력받은 81개의 값을 저장
- 한 행마다 입력을 받을 때 해당 행의 max값과 이전까지의 max값을 비교하여 81개의 값 중 최댓값을 저장
- 데이터를 저장한 table 리스트를 반복하면 해당 값이 저장한 max값과 일치하면 최댓값과 해당 행, 열을 출력하고 반복문을 종료
- 최댓값이 복수인 경우 한 곳의 위치만 출력하면 되기 때무네 한 행의 값을 입력받으면서 max값을 구하여 반복문을 모두 돌지 않아도 최댓값을 발견하는 순간 반복문을 종료 가능
1920. 수찾기
수찾기
분류: 자료 구조, 정렬, 이분 탐색
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
코드
n = input()
a = sorted(map(int, input().split()))
m = int(input())
number = list(map(int, input().split()))
def binary_search(a_list, number, start, end):
if a_list[start] <= number <= a_list[end]:
mid=(start + end) // 2
if a_list[mid] == number:
return 1
else:
if a_list[mid] > number:
return binary_search(a_list, number, start, mid)
else:
return binary_search(a_list, number, mid+1, end)
else:
return 0
start,end=0, len(a)-1
for i in number:
print(binary_search(a, i, start,end))
설명
- 이분 탐색은 정렬이 된 자료에서 사용할 수 있기 때문에
sorted()를 사용하여 입력받은 a값들을 정렬 - 초기 세팅은 리스트의 처음과 끝 인덱스를 start, end라 한다.
- 리스트가 정렬되어 있기 때문에 입력받은 x가
a_list[start] ~ a_list[end]범위에 포함되지 않으면 0을 반환 - 재귀를 사용하여 이분 탐색 구현
1654. 랜선 자르기
랜선 자르기
분류: 이분 탐색, 매개 변수 탐색
만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
코드
import sys
k, n = map(int, input().split())
lan_list = [int(sys.stdin.readline().strip()) for _ in range(k)]
left, right = 1, max(lan_list)
def binary_search(lan_list, left, right, n):
mid = (left + right) // 2
if left > right:
return mid
lan_cnt = 0
for i in lan_list:
lan_cnt += i // mid
if lan_cnt >= n:
return binary_search(lan_list, mid + 1, right, n)
else:
return binary_search(lan_list, left, mid - 1, n)
print(binary_search(lan_list, left, right, n))
설명
- 랜선을 잘라 생긴 개수를 n을 기준으로 이분 탐색을 구현
- n이 될 수 있는 lan의 길이 중 가장 긴 값을 출력해야 하기 때문에
lan_cnt==n이 반환 조건이 아닌 left가 right보다 커진 시점을 반환 조건으로 한다. - 입력값이 매우 많을 경우
input()보다sys.stdin.readline().strip()을 사용하는 것이 빠르다
2805. 나무 자르기
나무 자르기
분류: 이분 탐색, 매개 변수 탐색
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
코드
import sys
n, m = map(int, input().split())
h_list = list(map(int, sys.stdin.readline().strip().split()))
left, right = 0, max(h_list)
def binary_search(h_list, left, right, m):
mid = (left + right) // 2
if left > right:
return mid
m_len = 0
for i in h_list:
if i > mid:
m_len += i - mid
if m_len >= m:
return binary_search(h_list, mid + 1, right, m)
else:
return binary_search(h_list, left, mid - 1, m)
print(binary_search(h_list, left, right, m))
설명
- 랜선 자르기와 코드가 매우 비슷하다.
- 중간에 m미터를 구하는 과정에서 조건문이 추가되는데 나무의 높이가 mid보다 클 경우에만 나무의 길이를 저장하는
m_len에 누적
