학교에서 진행하는 여름방학 코딩테스트 대비 캠프 with CodeTree 의 강의와 문제풀이를 정리한 내용입니다.

완전탐색이란?

완전탐색이란, 문제를 해결할 수 있는 가장 naive한 방법이다. 이는 모든 가능한 경우를 다 따져보는 것으로, 코드를 작성하기가 쉽다는 장점이 있지만 모든 가능한 경우를 전부 계산해봐야 하므로 올바른 정답을 찾기까지 걸리는 시간(프로그래 수행시간)이 비교적 오래 걸린다는 단점이 있다.
따라서 완전탐색은 시간복잡도를 계산해보고, 시간초과가 나지 않을 것 같다면 항상 적용해야 하는 방법이라고 할 수 있다.

격자 안에서 완전탐색

✏️ 연습문제 : 최고의 33위치

N * N 크기의 격자 정보가 주어집니다. 이때 해당 위치에 동전이 있다면 1, 없다면 0이 주어집니다. N * N 격자를 벗어나지 않도록 3 * 3 크기의 격자를 적절하게 잘 잡아서 해당 범위 안에 들어있는 동전의 개수를 최대로 하는 프로그램을 작성해보세요.

이 문제의 경우 어느 지점을 잡아야 최대의 돈을 얻을 수 있을지 바로 판단하기가 어렵다.
따라서 가능한 모든 지점에 3x3 크기의 사각형을 놓아보며, 얻을 수 있는 돈을 세고, 그 중 최댓값을 구하면 된다.

1. 모든 가능한 3x3 격자의 좌측 상단 모서리를 잡아본다.
   단, 이때 격자를 벗어나는 경우는 제외한다.
2. 좌측 상단 모서리가 잡혔다면, 3x3 칸 내 동전의 수를 세어 최댓값을 갱신한다.

💻 CODE

n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

# (row_s, col_s) ~ (row_e, col_e) 사이의 금의 개수를 계산하는 함수
def get_num_of_gold(row_s, col_s, row_e, col_e):
    num_of_gold = 0

    for row in range(row_s, row_e + 1):
        for col in range(col_s, col_e + 1):
            num_of_gold += grid[row][col]

    return num_of_gold

max_gold = 0

# 완전탐색
for row in range(n):
    for col in range(n):
        # 3 * 3 격자가 n * n 격자를 벗어나는 경우는 계산 X
        if row + 2 >= n or col + 2 >= n:
            continue
        
        num_of_gold = get_num_of_gold(row, col, row + 2, col + 2)
            
        # 최댓값 갱신
        max_gold = max(max_gold, num_of_gold)

print(max_gold)

---

시뮬레이션이란?

시뮬레이션이란 문제에서 제시한 알고리즘을 한 단계식 차례대로 수행하여 해결하는 방법을 말한다. 이런 문제의 경우 문제를 해결하는데 있어 아이디어를 떠올리기는 쉽지만 떠올린 아이디어를 실제로 코드로 옮기는 과정이 어렵다.

격자 안에서 밀고 당기기

밀고 당기는 작업이란, 주어진 숫자들을 특정 방향으로 1칸씩 미는 작업을 뜻한다. 2차원 격자에서는 선택된 행에 대해, 적혀있는 숫자들을 왼쪽 혹은 오른쪽으로 한 칸씩 밀어주는 작업이 될 수 있고, 혹은 선택된 열에 대해 적혀있는 숫자들을 위 혹은 아래 방향으로 한 칸씩 밀어주는 작업이 될 수도 있다.

1. 가장 끝에 있는 원소가 유실되는 것을 방지하기 위해서 가장 끝의 원소를 temp라는 변수를 저장한다.
2. 가장 끝 칸(n-1)부터 앞으로 오며 순서대로 채운다.
   앞에서부터 당기는걸 반복한다면, 정보가 중간에 유실될 수 있다.
3. 모든 원소를 채웠다면, 가장 앞 칸에 temp에 저장되어 있던 값을 넣어준다.

✏️ 연습문제 : 컨베이어 벨트

시계 방향으로 한 칸씩 회전하는 컨베이어 벨트가 있습니다. 컨베이어 벨트 위아래로 n개씩 총 2 * n 개의 숫자가 두 줄로 적혀 있고, 1초에 한 칸씩 움직입니다.t초의 시간이 흐른 뒤 컨베이어 벨트에 놓여있는 숫자들의 상태를 출력하는 프로그램을 작성해보세요.

1. 위에서 가장 오른쪽에 있는 숫자를 따로 temp값에 저장한다.

   

2. 위에 있는 숫자들을 완성한다. 오른쪽에서부터 채워넣어야 하며, 맨 왼쪽 숫자는 아래에서 가져온다.

   

3. 아래에 있는 숫자들을 완성한다. 마찬가지로 오른쪽에서부터 채워야 하며, 맨 왼쪽 숫자는 temp값을 가져온다.

   

💻 CODE

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=" ")

격자 안에서 터지고 떨어지는 경우

격자 안에서 터지고 떨어지는 작업이란, 특정 규칙에 의해 폭탄이 터지게 되고, 그 이후에 중력이 작용하여 위에 떠있는 폭탄들이 아래로 떨어지는 작업을 말한다.

$\rightarrow$ 시간복잡도 $O(n)$에 진행할 수 있다.

2차원 격자에서 떨어지는 경우

1. temp라는 새로운 배열을 생성한다.
2. 아래에서 위로 올라오면서, 비어있지 않을 때만 temp에 넣어준다.
3. temp값을 기존 배열에 다시 옮긴다.

1차원 격자에서 떨어지는 경우

1. temp라는 새로운 배열을 생성한다.
2. 왼쪽에서 오른쪽으로 가면서, 비어있지 않을 때만 temp에 넣어준다.
3. temp값을 기존 배열에 다시 옮긴다.

-> 1차원과 2차원에서의 전체적인 흐름은 서로 비슷하다.

격자 안에서 단일 객체를 이동

격자에서 인접한 4방향으로 이동하는 문제에서는 코드를 깔끔하게 작성하기 위해 dx, dy 테크닉을 이용하는 것이 좋다.

✏️ 연습문제 : 숫자가 더 큰 인접한 곳으로 이동

1이상 100이하의 숫자로 이루어진 n * n 크기의 격자판 정보가 주어집니다. 이때 특정 위치에서 시작하여, 상하좌우로 인접한 곳에 있는 숫자들 중 현재 위치에 있는 숫자보다 더 큰 위치로 끊임없이 이동합니다. 만약 그러한 위치가 여러개 있는 경우, 상하좌우 방향 순서대로 우선순위를 매겨 가능한 곳 중 우선순위가 더 높은 곳으로 이동합니다. 격자를 벗어나서는 안되며, 더 이상 움직일 수 없을 때까지 반복합니다. 위의 규칙에 따라 방문하게 되는 위치에 적힌 숫자를 순서대로 출력하는 프로그램을 작성해보세요.

• 움직일 수 있는 곳이 여러 곳일 경우, 먼저 움직여야 하는 방향이 정해져 있기 때문에 우선적으로 봐야하는 방향의 순서는 상하좌우이므로, dx, dy 값을 상하좌우 순서대로 적어주면 편하다.

1. (Next X, Next Y)가 격자를 벗어나는 경우 해당 방향에 인접한 숫자가 존재하지 않으므로, 그 다음 방향이 가능한지 확인한다.

2. (Next X, Next Y)가 격자를 벗어나지 않는 경우

   1. 이동하려는 곳에 적혀있는 값이 더 큰 경우 조건을 만족시키므로 이동한다.
   2. 이동하려는 곳에 적혀있는 값이 같거나 작은 경우 조건을 충족시키지 못했으므로 이동하지 않고, 그 다음 바향이 가능한지 확인한다.

💻 CODE

n, curr_x, curr_y = tuple(map(int, input().split()))
a = [[0] * (n + 1)]
for _ in range(n):
    a.append([0] + list(map(int, input().split())))

visited_nums = []

def in_range(x, y):
    return 1 <= x and x <= n and 1 <= y and y <= n

def can_go(x, y, curr_num):
    return in_range(x, y) and a[x][y] > curr_num

def simulate():
    global curr_x, curr_y
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

    for dx, dy in zip(dxs, dys):
        next_x, next_y = curr_x + dx, curr_y + dy

        if can_go(next_x, next_y, a[curr_x][curr_y]):
            curr_x, curr_y = next_x, next_y
            return True
 
    return False

visited_nums.append(a[curr_x][curr_y])
while True:
    greater_number_exist = simulate()
    if not greater_number_exist:
        break
    visited_nums.append(a[curr_x][curr_y])

for num in visited_nums:
    print(num, end=' ')