[Python] 프로그래머스 스티커 모으기(2), 백준 21610 마법사 상어와 비바라기, 프로그래머스 표 병합

1. 문제 - 프로그래머스 스티커 모으기(2)

https://school.programmers.co.kr/learn/courses/30/lessons/12971

 

💡알고리즘 - DP

- 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 
라는 문장에서 이전 항목을 활용하여 최적의 해를 만들어낸 다는 점에서 DP 알고리즘을 유추할 수 있다.

 

✅ 풀이

def solution(sticker):
    answer = 0
    n = len(sticker)
    
    if n <= 3:
        return max(sticker)
    
    dp = [[0] * n for _ in range(2)]  # dp의 해: 스티커에 적힌 숫자의 합의 최대값
    # dp[0]: 첫번째 스티커를 뗸 경우, dp[1]: 첫번째 스티커를 떼지 않은 경우
    dp[0][0] = sticker[0]
    dp[0][1] = sticker[0]           # 첫번째 스티커를 이미 뗐으므로, 인접한 그 다음 칸은 그 전의 해와 같다.
    
    dp[1][0] = 0 
    dp[1][1] = sticker[1]
    
    # 첫번째 스티커를 뜯으면서 시작한 경우
    for i in range(2, n-1):
        dp[0][i] = max(dp[0][i-1], dp[0][i-2] + sticker[i])  # 차례대로 스티커를 떼지 않는 경우, 스티커를 떼는 경우
    
    # 첫번째 스티커를 떼지 않은 경우
    for i in range(2, n):
        dp[1][i] = max(dp[1][i-1], dp[1][i-2] + sticker[i])
        
    return max(dp[0][-2], dp[1][-1])

 

- 2차원 배열을 만들어서 dp[0][i]은 첫 번째 스티커를 뗀 경우, dp[1][i]은 첫 번째 스티커를 떼지 않은 경우의 합이라고 정의했다.

2차원 배열을 만들지 않아도 dp1, dp2 이렇게 1차원 배열 2개를 만들어서 나눈 다음에 풀이할 수도 있다.
dp[0][i], dp[1][i]는 i 위치까지 도달했을 때까지 뗀 스티커 수의 총합이라고 정의한다.

- 첫 번째 스티커를 뗀 경우, 두번째 스티커를 뗄 수 없으니 dp[0][1]은 첫번째 스티커만 뗀 경우가 된다.

    dp[0][0] = sticker[0]
    dp[0][1] = sticker[0]

- 첫 번째 스티커를 떼지 않은 경우, 두번째 스티커를 뗄 수 있으니 dp[1][1]은 두번째 스티커 값이 된다.

    dp[1][0] = 0 
    dp[1][1] = sticker[1]

- 그이후에 첫 번째 스티커를 떼지 않은 경우와 뗀 경우를 나눠서 생각해보면 되는데 첫 번째 스티커를 떼면 문제 조건에 의해 맨 마지막 스티커를 뗄 수 없으므로 n-2까지 순회하고, 그렇지 않으면 n-1까지 순회한다.

2. 문제 - 백준 21610 마법사 상어와 비바라기 (삼성 SW 역량테스트 기출)

💡알고리즘 - 시뮬레이션 / 구현

 

✅ 풀이

- 문제에 있는 순서대로 꼼꼼하게 따라가며 구현하면 어렵지 않은 문제이다.

n, m = map(int, input().split())
A = []       # A[r][c]: 바구니에 저장되어 있는 물의 양
for _ in range(n):
  A.append(list(map(int, input().split())))
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]
# 맨 첫번째는 방향 offset 변수가 1부터 시작함에 따라 간편하게 접근하기 위한 더미 값
# 문제 순서대로 방향 배열
clouds = [[0] * n for _ in range(n)]

# 비바라기 시전하면, (n, 1), (n, 2), (n-1, 1), (n-1, 2)에 비구름이 생긴다.
clouds[n-1][0] = 1
clouds[n-1][1] = 1
clouds[n-2][0] = 1
clouds[n-2][1] = 1

# 이후에 구름에 이동을 m번 명령한다.
for _ in range(m):
  d, s = map(int, input().split())
  cloud_pos = []

  # 모든 구름이 d 방향으로 s칸 이동한다.
  for i in range(n):
    for j in range(n):
      if clouds[i][j] == 1:
        clouds[i][j] = 0

        # 1번 행-n번 행, 1번 열-n번 열이 연결되어있으므로 n 더한 후 n으로 나눈 나머지로 연결시켜준다.
        ni = (i + dx[d] * s + n) % n
        nj = (j + dy[d] * s + n) % n

        cloud_pos.append((ni, nj))
    
  # 구름이 있는 칸의 바구니에 저장된 물의 양이 증가한다.
  for x, y in cloud_pos:
    A[x][y] += 1

  # 물복사 버그 마법 시전
  for x, y in cloud_pos:
    count = 0    # 대각선 방향으로 1인 칸의 갯수
    for i in range(2, 9, 2):
      nx = x + dx[i]
      ny = y + dy[i]

      # 이때는 구름 이동과는 달리 경계를 넘어가는 칸은 세지 않는다.
      if 0<=nx<n and 0<=ny<n and A[nx][ny] != 0:
        count += 1
    A[x][y] += count   # 해당 갯수만큼 바구니의 양 증가

  for i in range(n):
    for j in range(n):
      if A[i][j] >= 2 and (i, j) not in cloud_pos:    # 물의 양이 2이상인 모든 칸에, 하지만 위에서 구름이 사라진 칸이 아닌 칸에
        clouds[i][j] = 1   # 구름이 생긴다.
        A[i][j] -= 2    # 물의 양이 2 줄어듬

answer = 0
for i in range(n):
  for j in range(n):
    answer += A[i][j]

print(answer)

 

3. 문제 - 프로그래머스 표 병합 (2023 카카오 기출)

💡알고리즘 - 구현 / 시뮬레이션

표의 셀끼리 병합 = 병합된 좌표끼리 서로 같은 좌표를 가르키게 하는 것을 어떻게 처리하는지에 대한 아이디어에서 막혔는데,

카카오 블로그(https://tech.kakao.com/posts/567)를 찾아보니 병합된 기준 좌표들을 저장할 merged 배열로 접근할 수 있었다.

 

✅ 풀이

def solution(commands):
    answer = []
    pyo = [["EMPTY"] * 51 for _ in range(51)]   # 50x50 고정, 비어있는 셀을 "EMPTY"로 표현한다.
    merged = [[(i, j) for j in range(51)] for i in range(51)]   # 병합된 좌표들을 저장하는 배열. 초기에는 자기 자신의 좌표로 초기화함
    
    for c in commands:
        command = c.split()
        if command[0] == "UPDATE":
            if len(command) == 4:    # 길이가 4인 경우 (r, c) 위치가 주어짐
                r, c, value = int(command[1]), int(command[2]), command[3]
                x, y = merged[r][c]   # 병합된 좌표값 얻어오기
                pyo[x][y] = value
            else:       # value1을 값으로 가지고 있는 모든 셀들의 값을 value2로 바꿔줌
                value1, value2 = command[1], command[2]
                for i in range(1, 51):
                    for j in range(1, 51):
                        if pyo[i][j] == value1:
                            pyo[i][j] = value2
                
        elif command[0] == "MERGE":
            r1, c1, r2, c2 = int(command[1]), int(command[2]), int(command[3]), int(command[4])
            x1, y1 = merged[r1][c1]    # 병합된 r1, c1 좌표 얻어오기
            x2, y2 = merged[r2][c2]    # 병합된 x2, y2 좌표 얻어오기
            if pyo[x1][y1] == "EMPTY":  # pyo[x1][y1] 가 빈값이라면 x2, y2 를 기준으로 해서 병합해야한다.
                value = pyo[x2][y2]
                
                for i in range(1, 51):
                    for j in range(1, 51):
                        if merged[i][j] == (x1, y1):   # x2, y2로 병합하기
                            merged[i][j] = (x2, y2)
                            pyo[i][j] = value
                pyo[x1][y1] = value
                            
            else:     # pyo[x1][y1] 값이 있다면, pyo[x2][y2] 값이 있는지와 무관하게 pyo[x1][y1]을 선택한다.
                value = pyo[x1][y1]
                for i in range(1, 51):
                    for j in range(1, 51):
                        if merged[i][j] == (x2, y2):
                            merged[i][j] = (x1, y1)
                            pyo[i][j] = value
                pyo[x2][y2] = value

        elif command[0] == "UNMERGE":
            r, c = int(command[1]), int(command[2])
            x, y = merged[r][c]
            value = pyo[x][y]
            for i in range(1, 51):
                for j in range(1, 51):
                    if merged[i][j] == (x, y):   # 병합된 모든 셀들을
                        merged[i][j] = (i, j)    # 기존으로 해제시킨다.
                        pyo[i][j] = "EMPTY"
            pyo[r][c] = value                   # 병합을 해제하기 전, 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 된다.
        else:    # PRINT -> answer 배열에 추가
            r, c = int(command[1]), int(command[2])
            x, y = merged[r][c]
            answer.append(pyo[x][y])
            
    return answer

 

새롭게 알게된 점

- DP 문제를 풀 때, DP의 해 = 문제의 답 이라고 가정하고 DP 배열을 정의해보자

- python 집합의 교집합: &, 합집합: |, 차집합: -