⭐실력진단 결과

격자 안에서 모든 가능한 경우를 탐색하여 원하는 결과를 얻는 방법을 배우게 됩니다.

---

기본개념

---

🟢최고의 33위치

✏️격자 안에서의 완전탐색

• 완전탐색 : 문제를 해결할 수 있는 가장 무식한(?) 방법
• 시간복잡도를 계산해보고 시간초과가 나지 않을 것 같다면 항상 적용

완전탐색 예시

1. 비밀번호 맞추기
   4자리라면 0000부터 9999까지 일일이 다 맞춰본다.
2. N개의 숫자 중 M개의 숫자를 골라 합이 최대가 되도록 하기
   가능한 모든 조합을 직접 만들어 합을 구해 그 중 최댓값을 구한다.

완전탐색 구현 방법

1. for문 기반 구현
2. 재귀함수 기반 Backtracking(Brute Force) 기법

✔️격자에서의 완전탐색은 칸 단위로 원하는 지점을 모두 확인하는 방식으로 진행

📌문제

📌나의 코드

# 격자 크기
n = int(input())

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

def get_num_of_coin(row_s, row_e, col_s, col_e):
    num_of_coin = 0

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

    return num_of_coin

MAX_coin = 0

for row in range(n):
    for col in range(n):
        # 격자를 벗어나는지 확인
        if row + 2 >= n or col + 2 >= n:
            continue
        
        # 동전 개수 확인
        num_of_coin = get_num_of_coin(row, row + 2, col, col + 2)

        # 동전 최대 개수 
        MAX_coin = max(MAX_coin, num_of_coin)

print(MAX_coin)

🔓풀이

1. 모든 칸을 확인하면서 3 * 3 크기의 격자이므로 행과 열 둘 다 격자를 벗어나는지 확인해야 한다.
2. 3 * 3 격자 행의 시작부터 끝까지, 열의 시작부터 끝까지 각 칸의 값을 더해 동전의 개수를 구한다.
3. 동전의 최대 개수를 비교해 값을 출력한다.

---

연습문제

---

🟢행복한 수열의 개수

📌문제

📌나의 코드

n, m = map(int, input().split())

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

ans = 0

# 행에서 행복한 수열의 수
for row in range(n):
    # 동일 원소에 자기 자신도 포함
    cnt = 1
    prev_col = 0
    for col in range(n):
        # 이전 열의 값이 현재 값과 같다면
        if prev_col == grid[row][col]:
            cnt += 1
        else:
            cnt = 1

        # 이전 열의 값 갱신
        prev_col = grid[row][col]    

		# 연속 횟수가 m보다 크면 ans 증가 후 다음 행으로
        if cnt >= m:
            ans += 1
            break

# 열에서 행복한 수열의 수
for col in range(n):
    # 동일 원소에 자기 자신도 포함
    cnt = 1
    prev_row = 0
    for row in range(n):
        # 이전 행의 값이 현재 값과 같다면
        if prev_row == grid[row][col]:
            cnt += 1
        else:
            cnt = 1
        
        # 이전 행의 값 갱신
        prev_row = grid[row][col]

		# 연속 횟수가 m보다 크면 ans 증가 후 다음 열로
        if cnt >= m:
            ans += 1
            break

print(ans)