[코테] 격자 안에서 완전 탐색
완전 탐색
- 문제를 해결할 수 있는 가장 naive한 방법으로, 모든 가능한 경우를 다 따져본다.
- 코드를 작성하기는 쉽지만, 프로그램의 수행시간이 비교적 오래 걸린다.
- 시간복잡도를 계산해보고 시간 초과가 나지 않는다면 무조건 사용하는 것이 좋다.
- 완전 탐색 구현 방법
- For문 기반으로 구현
- 재귀함수 기반의 Backtracking(Brute Force) 기법을 이용하는 방법
격자 안에서의 완전탐색 (for문 이용)
문제
N * N 크기의 격자 정보가 주어집니다. 이때 해당 위치에 동전이 있다면 1, 없다면 0이 주어집니다. N * N 격자를 벗어나지 않도록 3 * 3 크기의 격자를 적절하게 잘 잡아서 해당 범위 안에 들어있는 동전의 개수를 최대로 하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 격자의 크기를 나타내는 N이 주어집니다.
두 번째 줄부터는 N개의 줄에 걸쳐 격자에 대한 정보가 주어집니다. 각 줄에는 각각의 행에 대한 정보가 주어지며, 이 정보는 0또는 1로 이루어진 N개의 숫자로 나타내어지며 공백을 사이에 두고 주어집니다.
- 3 ≤ N ≤ 20
출력 형식
N * N 격자를 벗어나지 않으면서, 3 * 3 크기 격자 내에 들어올 수 있는 최대 동전의 수를 출력해주세요.
입출력 예제
입력:
3
1 0 1
0 1 0
0 1 0
출력:
4
✔️ 문제 풀이
캠프 중에 주어지는 문풀 시간에 풀려고 했으나 ㅋㅋ.. 역시나 기초지식이 부족한 나는 시간 내에 풀지 못했다. 캠프가 끝나면 기초부터 다시 풀어야겠다 하 .. 나에겐 넘 어려운 문제들…
아무튼 이 문제는 주워진 격자 범위를 벗어나지 않고, 3*3 격자를 잡아 격자 내의 동전들의 개수를 구해야 한다. 코드트리에서는 동전들의 최대 개수를 찾을 때까지 최댓값을 갱신하는 형식으로 코드를 작성하였다.
1. 모든 가능한 3 * 3 격자의 좌측 상단 모서리를 잡는다. (범위 내인지 확인)
2. 좌측 상단 모서리를 기준으로 3 * 3 칸 내의 동전 개수를 센다.
3. 최댓값을 갱신한다.
반복문을 이용해 주어진 격자를 처음부터 돌면서 좌측 상단 모서리인 경우를 탐색한다. 만약 3 * 3 격자가 n * n 격자를 벗어나면 continue를 이용해 건너 뛰고, 벗어나지 않는다면 3* 3 격자 내의 동전 개수를 센다. 동전 개수의 최댓값을 출력하는 코드를 작성하기 전, 동전 개수를 세는 함수를 먼저 정의한다.
- 주어진 범위 내의 동전 개수를 세는 함수
def get_num_of_gold(row_s, col_s, row_e, col_e): cnt = 0 for row in range(row_s, row_e + 1): for col in range(col_s, col_e + 1): if arr[row][col] == 1: cnt += 1 return cnt - 최댓값을 출력하는 반복문 ~~~python max_gold = 0 for row in range(n): for col in range(n): if row + 2 >= n or col + 2 >= n: continue gold_cnt = get_num_of_gold(row, col, row + 2, col + 2) max_gold = max(max_gold, gold_cnt)
print(max_gold)
<br>
- 전체 코드
~~~python
n = int(input())
arr = [
list(map(int, input().split()))
for _ in range(n)
]
def get_num_of_gold(row_s, col_s, row_e, col_e):
cnt = 0
for row in range(row_s, row_e + 1):
for col in range(col_s, col_e + 1):
if arr[row][col] == 1:
cnt += 1
return cnt
max_gold = 0
for row in range(n):
for col in range(n):
if row + 2 >= n or col + 2 >= n:
continue
gold_cnt = get_num_of_gold(row, col, row + 2, col + 2)
max_gold = max(max_gold, gold_cnt)
print(max_gold)
격자 안에서의 밀고 당기기
문제
시계 방향으로 한 칸씩 회전하는 컨베이어 벨트가 있습니다. 컨베이어 벨트 위아래로 n개씩 총 2 * n 개의 숫자가 두 줄로 적혀 있고, 1초에 한 칸씩 움직입니다.
위의 그림에서 1초가 흐른 뒤에는 다음과 같이 그림이 바뀌게 됩니다.
t초의 시간이 흐른 뒤 컨베이어 벨트에 놓여있는 숫자들의 상태를 출력하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 n과 t가 공백을 사이에 두고 주어집니다.
두 번째 줄에는 위 변에 있는 초기 n개의 숫자들이 공백을 사이에 두고 주어집니다.
세 번째 줄에는 아래 변에 있는 초기 n개의 숫자들이 공백을 사이에 두고 주어집니다.
숫자는 각 변마다 숫자가 올바르게 보이는 방향에서 바라봤을 때 왼쪽에서 오른쪽 순으로 주어집니다.
- 1 ≤ n ≤ 200
- 1 ≤ t ≤ 1,000
- 1 ≤ 주어지는 숫자 ≤ 9
출력 형식
t초 후 컨베이어 벨트에 놓여있는 숫자들의 상태를 출력합니다.
첫 번째 줄에는 위 위 변에 있는 n개의 숫자들을 공백을 사이에 두고 출력합니다.
두 번째 줄에는 아래 변에 있는 n개의 숫자들을 공백을 사이에 두고 출력합니다.
숫자는 각 변마다 입력으로 주어지는 순서대로 출력합니다.
입출력 예제
입력:
3 1
1 2 3
6 5 1
출력:
1 1 2
3 6 5
✔️ 문제 풀이
이번 문제도 강사님이 설명해주신 방법으로 접근해서 풀어보려고 했는데 마찬가지로 풀지 못했다 … ㅠ 일단 코드트리에 있는 해설을 참고하여 다시 풀어보았다.
처음에는 주어진 숫자들을 하나의 배열에 다 담고자 했는데 이것보다는 해설에 나와있는 것처럼 각 행을 따로 담는 게 컨베이어 벨트 문제를 풀기에 더 적합한 것 같다.
u = list(map(int, input().split()))
d = list(map(int, input().split()))
컨베이어 벨트를 2차원 격자로 생각했을 때 선택된 행에 대해 오른쪽으로 한 칸씩 밀어줘야 한다. 이를 위해 먼저 각 행의 오른쪽 끝을 temp라는 변수에 담아야 한다. temp = a[n - 1]
그리고 for문을 사용해 오른쪽으로 한 칸씩 밀어주고, 아래 행의 값을 u[0]로 옮긴다.
for i in range(n - 1, 0, -1):
u[i] = u[i - 1]
u[0] = d[i - 1]
아래 행도 마찬가지로 시행해준다. 완성된 코드는 다음과 같다.
n, t = tuple(map(int, input().split()))
u = list(map(int, input().split()))
d = list(map(int, input().split()))
for _ in range(t):
temp = u[n-1]
for i in range(n-1, 0, -1):
u[i] = u[i - 1]
u[0] = d[n - 1]
for i in range(n-1, 0, -1):
d[i] = d[i - 1]
d[0] = temp
for elem in u:
print(elem, end = " ")
print()
for elem in d:
print(elem, end = " ")
print()
문제출처: 코드트리의 문제 및 풀이를 정리한 내용입니다.
https://www.codetree.ai/missions/2/problems/best-place-of-33?&utm_source=clipboard&utm_medium=text
https://www.codetree.ai/missions/2/problems/conveyor-belt?&utm_source=clipboard&utm_medium=text
