격자 안에서 완전 탐색
완전탐색 : 문제가 정의하는 문제 공간을 전체적으로 탐색해보는 것. 간단하게 말하면 문제에서 정의한 조건에 따라서 나올 수 있는 모든 경우의 수를 컴퓨터에게 다 해보게 하는 것.
1. 최고의 33위치
https://www.codetree.ai/missions/2/problems/best-place-of-33?&utm_source=clipboard&utm_medium=text
우선 예제의 과정을 알아보자.
어떤 문제가 나오든 완전 탐색은 한 번쯤 생각해볼만한다. 항상 모든 문제에 대해 완전 탐색이 가능한 지 따져보자!
위 예시 문제에서는 N N 격자를 벗어나지 않으면서, 3 3 크기 격자 내에 들어올 수 있는 최대 동전의 수를 구해야한다.
완전탐색을 진행할 때 시간복잡도는 우선 하나의 과정에 대한 시간 복잡도를 계산하고 반복 횟수를 구한다.
위 문제에서는 1*3 의 박스로 가로를 이동한다고 하면 n-2번을 거친다. 그런데 이게 n 행까지 있으므로 nx(n-2) 이다. O(n^2) 이므로 해당 문제에서 시간 제한 내에 있다. 따라서 완전 탐색으로 풀 수 있다.
내가 짠 코드
n = int(input())
positions = [list(map(int, input().split())) for _ in range(n)]
max_coins = 0
for i in range(n-2):
for j in range(n-2):
now_coins = 0
for k in range(j, j+3):
now_coins += positions[i][k]
now_coins += positions[i+1][k]
now_coins += positions[i+2][k]
max_coins = max(now_coins, max_coins)
print(max_coins)보완점
- 한 번에 여러 일을 하기 보다는 작업을 쪼개보기
- 순차적으로 어떻게 일을 진행할 지 확인하기
2. 행복한 수열의 개수
입력 형식
첫 번째 줄에는 격자의 크기를 나타내는 n과 연속해야 하는 숫자의 수를 나타내는 m이 공백을 사이에 두고 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 격자에 대한 정보가 주어집니다. 각 줄에는 각각의 행에 대한 정보가 주어지며, 이 정보는 1이상 100이하의 숫자가 각각 공백을 사이에 두고 주어집니다.
1 ≤ m ≤ n ≤ 100
출력 형식
2n개의 수열들 중 행복한 수열의 수를 출력해주세요.
입력
3 2
1 2 2
1 3 4
1 2 3
출력
2
이번에도 예시로 살펴보자 우선은 격자의 크기 n이 3이다. 이는 3x3배열임을 의미한다. 그리고 m 이 2로 연속해야하는 수가 2개 이상이어야함을 의미한다. 1. 3개의 행을 살펴보면서 연속하는 수가 2개 이상임을 확인한다. 2. 3개의 열을 살펴보면서 연속하는 수가 2개이상임을 확인한다. 그러면서 조건에 맞는 행 또는 열의 개수를 구하면 된다.
1행을 살펴보면 [1,2,2] 이다. 여기서는 2가 2번 연속해있으므로 result 에 카운팅해준다. (현재 result = 1)
2행을 살펴보면 [1,3,4] 이다. 여기서는 2번 이상 연속하는 수가 없으므로 카운팅하지 않는다. 3행을 살펴보면 [1,2,3] 이다. 여기서도 2번 이상 연속하는 수가 없으므로 카운팅하지 않는다.
그리고 1열을 살펴보면 [1,1,1] 로 여기서는 1이 3번 등장해서 2번 이상 연속해있으므로 result 에 카운팅한다. (현재 result = 2)
2열을 살펴보면 [2,3,2] 로 연속된 수가 없으므로 카운팅하지 않는다.
3열을 살펴보면 [2,4,3] 로 연속된 수가 없으므로 카운팅하지 않는다.
이렇게 모든 경우의 수를 탐색하면 된다 .
솔루션 도출 과정
코드로 위 과정을 표시하려면 어떻게 할까?
큰 문제를 작은 문제로 쪼개야한다.
여기서 작은 문제는 '하나의 배열에 대해 연속 수가 m 개 이상임을 확인하는 것' 이다.
따라서 배열 arr과 연속 조건 수 m 을 인풋으로 받았을 때 그것이 행복한 수열인지 boolean 을 리턴하는 함수가 작은 함수가 될 수 있다.
배열을 체크할 때는 인덱스 0부터 n-1 번째 까지가 아닌, n-1-(갈수있는 인덱스)+1 = m 이 되어야한다. 따라서 (갈 수 있는 인덱스) = n-m 이 될 수 있다. 그럼 범위는 for i in range(0, n-m+1) 로 할 수 있을 것이다.
내가 짠 코드
n, m = tuple(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]
# 배열을 체크
def check_in_arr(arr, m):
for i in range(0, len(arr) - m + 1):
is_happy = True
first_num = arr[i]
for k in range(i, i + m):
if first_num != arr[k]:
is_happy = False
break
if is_happy:
return True
return False
result = 0
for i in range(n):
if check_in_arr(arr[i], m):
result += 1
for j in range(n):
col = [arr[i][j] for i in range(n)]
if check_in_arr(col, m):
result += 1
print(result)3. 금 채굴하기(연습문제)
솔루션 도출 과정
내가 짠 코드
격자 안에서 밀고 당기기
격자 안에서 밀고 당기는 작업은 숫자를 1칸씩 미는 작업을 말한다.
단 이 경우 배열을 오른쪽으로 한 칸씩 시프트 한다고 하면 맨 오른쪽 녀석을 그냥 버려버리면 데이터 손실이 있을 수 있으므로 이를 temp 임시 저장소에 저장해준뒤 시프트하고 나서 가장 왼쪽의 비어있는 공간에 넣어주는 과정이 필요하다.
1. 컨베이어 벨트
아래 문제는 1초마다 배열이 시프트 되게 된다. t 초 후를 구하기 위해 우선 컨베이어 벨트에 넣었을 때 1초 후 상태를 구하는 함수를 만들어야하고, 이를 반복문에 넣어야 할 것 같다.
https://www.codetree.ai/missions/2/problems/conveyor-belt?&utm_source=clipboard&utm_medium=text
시간 제한: 1000ms
메모리 제한: 80MB
2. 삼각형 컨베이어 벨트
솔루션 도출 과정
내가 짠 코드
3. 1차원 바람(연습문제)
솔루션 도출 과정
내가 짠 코드
격자 안에서 터지고 떨어지는 경우
1. 1차원 젠가
https://www.codetree.ai/missions/2/problems/jenga-1d?&utm_source=clipboard&utm_medium=text
솔루션 도출 과정
- 빈 배열을 만들어서 빈 배열에 해당 슬라이싱 부분(젠가로 뺀 부분)을 제외하고 차곡차곡 쌓아준다!
- 함수로 나눠서 제작하면 함수 제작할 때는 해당 함수의 기능만 생각하며 구현할 수 있어서 좋다. (큰 문제를 작은 문제들로 자를 수 있다!)
내가 짠 코드
n = int(input())
genga = [int(input()) for _ in range(n)]
s1,e1 = tuple(map(int, input().split()))
s2,e2 = tuple(map(int, input().split()))
s1,e1 = s1-1, e1-1
s2,e2 = s2-1, e2-1
def do_genga(genga,s,e):
new_genga = []
for i in range(len(genga)):
if i in range(s,e+1):
continue
new_genga.append(genga[i])
return new_genga
new_genga = do_genga(genga,s1,e1)
new_genga = do_genga(new_genga,s2,e2)
print(len(new_genga))
for elem in new_genga:
print(elem)2. 십자 모양 폭발
솔루션 도출 과정
내가 짠 코드
3. 1차원 폭발 게임(연습문제)
솔루션 도출 과정
내가 짠 코드
