태야

<내 코드>

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을 해나가면 되는 것이다.

<내 코드>

import sys
sys.setrecursionlimit(10000)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(x, y, h):

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if(0 <= nx < N) and (0 <= ny < N):
            if arr[nx][ny] > h and done[nx][ny] == 0:
                done[nx][ny] = 1
                dfs(nx, ny, h)


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for k in range(max(map(max, arr))):  # 주어진 배열에서 가장 큰값만큼 반복
    # 매번 초기화
    cnt = 0
    done = [[0]*N for _ in range(N)]

    # 입력 받은 arr배열 탐색
    for i in range(N):
        for j in range(N):
            if arr[i][j] > k and done[i][j] == 0:
                done[i][j] = 1
                cnt += 1
                dfs(i, j, k)

    ans = max(ans, cnt)


print(ans)

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

이 문제에서 중요한 것이 물의 높이 1부터 ~ 가장 높은 높이까지 반복하며, 안전 영역의 최댓값을 구하는 거다. 

max(map(max, arr)) 구문을 통해서 입력 배열에서 가장 큰 값(이 예에서는 9)을 구할 수 있다. 그리고 매 dfs 탐색이 끝나면 이전 안전 영역 개수(ans)와 현재 탐색의 안전 영역 개수(cnt) 중 큰 값을 비교해 담는다.

<내 코드>

- DFS

import sys
sys.setrecursionlimit(10000)


def dfs(x, y, type):

    done.append((x, y))

    # 4방향 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if(0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
            # 정상인
            if type == 0 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 0)
            # 적록색맹
            elif type == 1 and colors[nx][ny] == colors[x][y]:
                dfs(nx, ny, 1)


N = int(input())
colors = [list(input()) for _ in range(N)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 정상인인 경우
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 0)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            dfs(i, j, 1)
            cnt_2 += 1

print(cnt_1, cnt_2)

DFS로 풀 때 런타임 에러 방지하기 위해 sys.setrecursionlimit(10000) 설정해준다. 그리고 type 값에 따라 정상인과 색약의 상태를 구분해 탐색한다. 시간을 조금 더 줄여보는 방법을 생각해봐야겠다.

- BFS

from collections import deque


def bfs(x, y):
    queue.append((x, y))
    done.append((x, y))
    
    while queue:
        curr = queue.popleft()

        for i in range(4):
            nx = curr[0] + dx[i]
            ny = curr[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
                if colors[nx][ny] == colors[curr[0]][curr[1]]:
                    queue.append((nx, ny))
                    done.append((nx, ny))


N = int(input())
colors = [list(input()) for _ in range(N)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 정상인인 경우
queue = deque()
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

queue = deque()
done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_2 += 1

print(cnt_1, cnt_2)

<내 코드>

import sys
sys.setrecursionlimit(10000) 


def dfs(x, y, cnt):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    now = (x, y)

    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = now[0] + dx[i]
        ny = now[1] + dy[i]

        if(0 <= nx < R) and (0 <= ny < C):
            if(done[strings[nx][ny]] == 0):
                done[strings[nx][ny]] = 1
                # print(done)
                dfs(nx, ny, cnt+1)
                done[strings[nx][ny]] = 0  #백트래킹


R, C = map(int, input().split())
strings = [list(map(lambda x: ord(x)-65, input())) for _ in range(R)] # 아스키 코드로 바꿔줌
done = [0]*26   # 알파벳 26개만큼 배열설정
done[strings[0][0]] = 1

ans = 1

dfs(0, 0, ans)
print(ans)

계속해서 시간 초과가 나서 실패하고, 이 코드로 겨우 통과했다. 알고리즘은 계속해서 맞았지만 재귀를 활용하다 보니 시간 초과가 많이 났다. 백트래킹의 기본 동작원리를 이해할 수 있는 문제였다.

<내 코드>

T = int(input())
for _ in range(T):
    strings = list(input())

    if strings[0] == 'O':
        strings[0] = 1
    else:
        strings[0] = 0

    for i in range(1, len(strings)):
        if strings[i-1] != 'O' and strings[i] == 'O':
            strings[i] = strings[i-1] + 1
        else:
            strings[i] = 0
    print(sum(strings))