태야

<내 코드>

N, M = map(int, input().split())
A = [list(map(int, list(input()))) for _ in range(N)]
B = [list(map(int, list(input()))) for _ in range(N)]

cnt = 0

def check():
    for i in range(N):
        for j in range(M):
            if A[i][j] != B[i][j]:
                return False
    return True


def solve(x, y):
    for i in range(x, x+3):
        for j in range(y, y+3):
            A[i][j] = 1 - A[i][j]  # 뒤집기

# 3*3 행렬의 왼쪽 상단 지점을 기준으로 삼는다.
for i in range(0, N-2):  # 0 ~ N-3
    for j in range(0, M-2):  # 0 ~ M-3
        if A[i][j] != B[i][j]:
            cnt += 1
            solve(i, j)

if check():
    print(cnt)
else:
    print(-1)

1. 3x3매트릭스의 특성을 고려하면 x의 범위는 [0, N-2]이고 y의 범위는 [0, M-2]이다.

2. [i][j]를 하나씩 늘려가며, 뒤지기 연산을 호출한다.

3. 마지막에는 A행렬과 B행렬이 같은지를 확인하고 같다면 solve() 호출 횟수를, 다르다면 -1을 반환한다.

(0,0) (N-1,0), (0, M-1), (N-1,M-1)의 값을 결정할 수 있는 부분 행렬은 딱 1개밖에 존재하지 않는다.

왼쪽 위 부터 오른쪽으로 하나씩 비교해가면서 다음 줄로 넘어가며 비교한다. 즉 3 x 3 행렬의 왼쪽 상단 점을 기준으로 A와 B가 같은지 비교하며 뒤집어 나간다. 한 번 지나간 기준점은 더 이상 바뀔 일이 없게 되며 이후 비교에 영향을 주지 않는다.

1. 탐욕 알고리즘 이란?

• Greedy algorithm 또는 탐욕 알고리즘이라고 불림
• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

2. 그리디 알고리즘으로 정답을 찾는 조건

1.  탐욕스러운 선택 조건(greedy choice proeprty)

2.  최적 부분 구조 조건(optimal substructure)

- 매번 탐욕스러운 선택을 해야 하며, 각각의 부분의 최적이 영원히 최적이 여야 한다.왜냐하면 그럴 경우 앞으로도 최적인 게 자명하기 때문이다.

즉, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

3. 탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용

• 반드시 최적의 해를 구할 수 있는 것은 아니기 때문

• 최적의 해에 가까운 값을 구하는 방법 중의 하나임

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

그리디 알고리즘에 따르면 매번 큰 값을 선택하면 4 - 9 - 12가 된다. 이것은 실제 최대 값이 아니라는 것을 알 수 있다. 실제로는 4 - 1 - 99를 따라가야 최대를 구할 수 있기 때문이다. 이처럼 그리디는 항상 그 상황에서는 최적이지만 종합적으로는 최적의 값을 도출하지 않는 경우가 발생한다.

<내 코드>

N = int(input())
nums = list(map(int, input().split()))
nums.sort()

sum_num = 0

for i in range(N):
    if sum_num + 1 >= nums[i]:
        sum_num += nums[i]
    else:
        break
print(sum_num + 1)

1. 입력 값 오름차순 정렬

2. 다음에 등장하는 숫자가 (누적합 + 1) 이하라면 누적합 + 1까지의 숫자들은 기존의 숫자들의 조합으로 모두 표현 가능하다.

3. 하지만, 다음에 등장하는 숫자가 (누적합 + 2) 이상이라면 기존의 숫자들의 조합으로 (누적합 + 1) 표현이 불가능하므로 (누적합 + 1)을 출력해준다. 

생각지도 못한 문제 해결 방법이었다..그리디 문제를 조금 더 다양하게 풀어봐야겠다.

<내 코드>

from collections import deque


def bfs(x1, y1, x_end, y_end):

    queue.append([x1, y1])
    done[x1][y1] = 1

    while queue:

        x, y = queue.popleft()

        if (x, y) == (x_end, y_end):
            return (done[x][y] - 1)

        for i in range(8):
            nx = x + move[i][0]
            ny = y + move[i][1]

            if(0 <= nx < n) and (0 <= ny < n) and done[nx][ny] == 0:

                queue.append([nx, ny])
                done[nx][ny] = done[x][y] + 1


case = int(input())

move = [[1, 2], [2, 1], [-1, 2], [-2, 1],
        [1, -2], [2, -1], [-1, -2], [-2, -1]]

for _ in range(case):
    n = int(input())
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())

    done = [[0]*n for _ in range(n)]
    queue = deque()

    # 예외처리
    if start_x == end_x and start_y == end_y:
        print(0)
        continue

    ans = bfs(start_x, start_y, end_x, end_y)
    print(ans)

처음에는 min()을 이용해 모든 경우에 대해 최소를 찾으려고 잘 못 생각했다. 역시나 구현이 제대로 안됐다. 

n x n 크기 배열을 만들어 각 지나온 좌표값에 이전 좌표의 값에 +1을 계속해 더해 원하는 지점에 도달했을 때 그때의 값을 출력하면 문제의 정답이 된다. 즉, 현재 지점에서 8방향으로 갈 수 있는 지점을 현재 지점의 값에 +1을 해나가면 되는 것이다.