https://www.acmicpc.net/problem/14502

• 문제 티어 : G4
• 풀이 여부 : Solved
• 소요 시간 : 31:42

정답 코드

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy
input = sys.stdin.readline

# 바이러스 전파 bfs
def bfs(arr):
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 2:  # 바이러스인 경우
                dq = deque([(x, y)])
                while dq:
                    cx, cy = dq.popleft()
                    for i in range(4):
                        nx, ny = cx + dx[i], cy + dy[i]
                        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                            arr[nx][ny] = 2  # 바이러스 전파
                            dq.append((nx, ny))

    return sum(row.count(0) for row in arr)  # 안전 영역 계산

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

zero_idx = []
for i in range(N):
  for j in range(M):
    if arr[i][j] == 0:
      zero_idx.append((i, j))

safe_max = 0
for walls in combinations(zero_idx, 3): # 3개의 벽 세우기
    modified_arr = deepcopy(arr)
    for x, y in walls:
        modified_arr[x][y] = 1  # 벽 세우기
    safe_max = max(safe_max, bfs(modified_arr))  # 안전 영역의 최댓값 갱신

print(safe_max)

접근 방식

문제에 대한 사고 흐름은 다음과 같았다.

1. 0의 좌표 중 3군데를 무작위로 고르기
2. 3군데의 값을 1로 만들어, 3개의 벽을 추가로 설치
3. BFS를 통해 2(바이러스)의 값을 가진 인덱스를 큐에 넣어, 바이러스 전파
4. 바이러스 전파 이후, 안전 영역의 값 리턴
5. 안전영역의 최댓값 갱신

zero_idx = []
for i in range(N):
  for j in range(M):
    if arr[i][j] == 0:
      zero_idx.append((i, j))

다음과 같이 0의 좌표를 저장한다. (리스트 컴프리헨션을 사용하는게 코드가 더 깔끔했겠지만!)

safe_max = 0
for walls in combinations(zero_idx, 3): # 3개의 벽 세우기
    modified_arr = deepcopy(arr)
    for x, y in walls:
        modified_arr[x][y] = 1  # 벽 세우기
    safe_max = max(safe_max, bfs(modified_arr))  # 안전 영역의 최댓값 갱신

다음 itertools의 combinations을 사용해 zero_idx로부터 3개의 벽을 세워줬다. 3개의 벽을 세우는 모든 방법에 대해 최대 안전 영역을 구해야하므로, deepcopy를 사용해 원본 배열을 복사해 사용했다. combinations로 뽑아낸 3개의 인덱스 값을 1로 채워준 뒤, bfs 함수의 arr 인자로 전달한다.

# 바이러스 전파 bfs
def bfs(arr):
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 2:  # 바이러스인 경우
                dq = deque([(x, y)])
                while dq:
                    cx, cy = dq.popleft()
                    for i in range(4):
                        nx, ny = cx + dx[i], cy + dy[i]
                        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                            arr[nx][ny] = 2  # 바이러스 전파
                            dq.append((nx, ny))

    return sum(row.count(0) for row in arr)  # 안전 영역 계산

• 벽을 만드는 경우 → 무작위로 3개의 벽을 세우는 경우의 수를 만들기에 브루트포스 사용
• 바이러스를 전파시키는 경우 → 상하좌우로 이동하기에 BFS 사용

배열을 순회하며 2의 값을 가지는 인덱스의 x, y 좌표를 큐에 넣어준다. 이 때 통상적인 BFS와의 다른 점은, 방문했던 좌표에 다시 방문하면 안되는 제약이 없으므로 visited배열 없이 사용한다.

바이러스의 전파가 완료되면 arr의 값을 2로 갱신해준 뒤, 큐에 있는 모든 좌표를 다 순회해 루프를 빠져나오면, 0의 값을 리턴해준다.

배운점 또는 느낀점

BFS와 브루트포스를 기반으로 생각할 거리가 많았던 문제지만, 접근하기는 수월한 편이었던 것 같다!

visited가 BFS에 무조건 필요한 것은 아니라는 점!

https://www.acmicpc.net/problem/1351

• 문제 티어 : G5
• 풀이 여부 : Solved
• 소요 시간 : 20:33

정답 코드

시간복잡도 : O(logN)

import sys
input = sys.stdin.readline

N, P, Q = map(int, input().rstrip().split())
memo = {0:1}

def find_A(n):
  if n in memo:
    return memo[n]
  else:
    memo[n] = find_A(n//P) + find_A(n//Q)
    return memo[n]

print(find_A(N))

접근 방식

탑다운으로 필요한 부분만을 메모이제이션으로 계산해서 사용하기

접근 시행착오(+ 코드)

시간 복잡도 : O(N)

# 메모리초과
import sys, math
input = sys.stdin.readline

N, P, Q = map(int, input().rstrip().split())
memo = {0: 1}
memo[1] = memo[0] + memo[0]

for i in range(2, N+1):
  if i not in memo:
    memo[i] = memo[math.floor(i//P)] + memo[math.floor(i//Q)]
print(memo[N])

배운점 또는 느낀점

바텀업보다 탑다운이 효율적인 해결 방안이 될 수 있음을 깨달은 문제다!

https://www.acmicpc.net/problem/2302

• 문제 티어 : S1
• 풀이 여부 : Failed
• 소요 시간 : 49:42

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

vips = list(int(input()) for _ in range(M))

dp = [[0]*2 for _ in range(N+1)]

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

for vip in vips:
    dp[vip][1] = -1

for i in range(2, N+1):
    if dp[i][1] == -1:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = -1
        else:
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = -1
    else:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = dp[i-1][0]
        else:
            dp[i][0] = dp[i-1][0]
            dp[i][1] = 0

if dp[N][1] == -1:
    print(dp[N][0])
else:
    print(dp[N][0] + dp[N][1])

접근 방식

https://velog.io/@mimmimmu/BOJ-2302번-극장-좌석-파이썬 다른 풀이들과 gpt를 동원해도 87%에서 인덱스 에러가 발생했었다. 위 블로그를 참고해 코드를 다시 작성했는데, 풀이 방법에서의 차이점은 블로그 필자분은 dp를 2차원 배열로 생성해서 풀이하셨다.

• 기본 경우
  • 안 바꾸는 경우: dp[i-1][0] + dp[i-1][1]
  • 바꾸는 경우: dp[i-1][0] (이전에 이미 바꾸면 X)
• vip 좌석이 앞에 있는 경우
  • 안 바꾸는 경우: dp[i-1][0]
  • 바꾸는 경우: 0

위와 같은 경우로 나눠서 풀이하셨다. 아직 완벽히 이해를 못했다… ^^ 내일 다시 풀어봐야지!

접근 시행착오(+ 코드)

런타임에러의 연속이었고… 어떤 예외상황에서 인덱스에러가 난 것인지 못찾겠다 😂

vip 배열의 각 원소를 기반으로 구간을 잘라, n개의 수로 만들 수 있는 경우의 수만큼을 누적해 곱해주는 방식으로 풀이했다.

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
vips = [0] + [int(input()) for _ in range(M)] + [N+1]

dp = [1] * (N+1)
dp[2] = 2

for i in range(3, N+1):
  dp[i] = dp[i-2] + dp[i-1] 

ans = 1
for i in range(1, M+2): # vips의 원소를 기준으로 구간을 잘라 dp에서 해당 값을 누적해 곱합
  ans *= dp[vips[i] - vips[i-1] - 1]
print(ans)

배운점 또는 느낀점

대체 어디서 인덱스에러가 났을까!!!!!🥵😂

https://www.acmicpc.net/problem/16987

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 38:41

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
eggs = [list(map(int, input().rstrip().split())) for _ in range(N)]

def backtrack(curr, broken):
  if curr == N: # 모든 계란으로 계란치기를 한 경우(N번째 계란까지 온 경우 -> curr:2 -> curr+1로 보내므로)
    global max_broken
    max_broken = max(max_broken, broken)
    return max_broken

  if eggs[curr][0] <= 0 or broken == N-1: # 현재 계란이 깨지거나(eggs[curr][0] : 내구도 < 0), 더이상 깨질 수 있는 계란이 없는 경우
    backtrack(curr+1, broken) # 정답 도출 조건(curr == N)을 위한 재귀

  else:
    for i in range(N): # 현재 들고있는 계란 기준 본인 제외, 왼/오 칠 수 있으므로
      if i != curr and eggs[i][0] > 0: # 깨지지 않은 다른 계란이 있는 경우
        eggs[i][0] -= eggs[curr][1] # curr 계란으로 상대 계란(i) 침
        eggs[curr][0] -= eggs[i][1] # 상대 계란(i)로 curr 계란 침

        # curr과 i번째 계란이 깨졌는지 확인 후 broken으로 넘김
        backtrack(curr+1, broken + (eggs[curr][0] <= 0) + (eggs[i][0] <= 0)) # 다음 계란으로 재귀 호출

        # 내구도 복원 -> 다른 경로 탐색에 영향을 주지 않기 위해
        eggs[i][0] += eggs[curr][1] # backtrack에 넘겼으므로 내구도 복원
        eggs[curr][0] += eggs[i][1] # backtrack에 넘겼으므로 내구도 복원

    # 모든 계란이 깨짐 OR 현재 계란(curr)만 남은 경우 
    if not any(eggs[i][0] > 0 for i in range(N) if i != curr): # 칠 수 있는 다른 계란이 없는 경우
      backtrack(curr+1, broken) # 다음 계란으로 넘어감

max_broken = 0
backtrack(0, 0)
print(max_broken)

접근 방식

처음에는 슬라이딩 윈도우 또는 투포인터를 사용해서 구현해야 하는 문제인가 했지만, 문제 상에서 현재 들고있는 계란 기준 왼/오 방향 상관없이 가장 많은 계란을 깰 수 있는 방법을 찾아야 하는 것이기에 완전탐색 중 백트래킹을 사용해서 가능한 경우의 수들만을 살펴보는 알고리즘을 사용해 풀이했다.

유의해야 할 점은, N번의 순회를 할 때, 다음 조건을 backtrack 함수의 인자로 넣어 재귀호출을 한 다음, 복원해줘야 하는 점이다.

배운점 및 느낀점

이 문제는 5번은 더 풀어봐야겠다….^^

https://www.acmicpc.net/problem/22862

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 25:23

정답 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

left, right = 0, 0
cnt_odd = 0 # 홀수 개수 기록
max_len = 0
for right in range(N):
  if arr[right] % 2 != 0: # 홀수일 경우 삭제
    cnt_odd += 1 # 홀수 갯수 +1

  while cnt_odd > K:
    if arr[left] % 2 != 0: # 허용된 홀수 개수 초과시 left 이동
      cnt_odd -= 1 # left를 오른쪽으로 한 칸 이동할 것이므로 홀수 갯수 -1
    left += 1 # left 이동

  max_len = max(max_len, (right-left+1) - cnt_odd) # left ~ right 범위에서 홀수 개수 빼줌

print(max_len)

접근 방식

left, right를 각각 arr의 시작 인덱스(0)로 설정한 후, 조건에 따라 투포인터로 배열을 순회하며 left, right를 갱신한다.

O(N)만큼 right를 순회하면서, arr[right]의 값이 홀수인 경우 cnt_odd(홀수 개수 카운터)를 갱신한다(+1). 이 때 left의 위치를 변경하는 조건은 cnt_odd(홀수 개수 카운터)가 K를 초과한 경우다.(left를 옮겨 구간 내 홀수 개수를 줄여줘야 하므로) cnt_odd의 값이 K보다 작아질 때까지, left의 값이 홀수이면 cnt_odd를 줄여주고, left의 인덱스를 오른쪽으로 한 칸 옮겨주며 left ~ right의 간격을 조정한다.

N번의 right 루프를 돌 때마다, max_len의 값을 left ~ right의 범위 중 cnt_odd(홀수 개수 카운터)만큼을 빼준 값으로 갱신해준다.

→ max_len = max(max_len, (right-left+1) - cnt_odd)

배운점 또는 느낀점

이번주에도 투포인터 열심히 풀어야겠다 ^ㅁ^ left, right의 갱신 조건을 찾는게 참 어려운 것 같다.

투포인터&이분탐색의 날을 가져야겠다 😂

https://www.acmicpc.net/problem/2156

• 문제 티어 : S1
• 풀이 여부 : Failed → Solved
• 소요 시간 : 17:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = [0] + [int(input()) for _ in range(N)] # 1부터 시작하기 위해 [0] 추가
dp = [0 for _ in range(N+1)]

dp[1] = arr[1]
if N > 1:
  dp[2] = arr[1] + arr[2]

for i in range(3, N+1):
  dp[i] = max(
    dp[i-1], # 현재 잔을 마시지 않는 경우
    dp[i-2] + arr[i], # 현재 잔을 마시고, 이전 잔은 마시지 않는 경우
    dp[i-3] + arr[i-1] + arr[i] # 현재 잔과 바로 이전 잔을 마시고, 그 이전 잔을 마시지 않는 경우
  )

print(dp[N])

접근 방식

• basecase
  • dp[0] = 0 → 포도주가 없는 경우
  • dp[1] = arr[1] → 첫번째 포도주만 있는 경우
  • dp[2] = arr[1] + arr[2] → 첫번째 두번째 포도주만 있는 경우

→ 위 세 경우가 “연속된 세 잔을 모두 마실 수 없다”의 조건을 언제든 충족하는 경우이므로 basecase로 설정

3~N까지 dp를 갱신하면서,

1) 현재 잔을 마시지 않는 경우: dp[i-1] (arr[i]를 더하지 않고 dp[i-1]이전 상태를 그대로 가져감)

2) 현재 잔을 마시고, 이전 잔은 마시지 않는 경우: dp[i-2] + arr[i]

3) 현재 잔과 바로 이전 잔을 마시고, 그 이전 잔은 마시지 않는 경우: dp[i-3] + arr[i-1] + arr[i]

ex) i = 3 → dp[0] + arr[2] + arr[3]

위 3개의 값 중 최댓값을 찾아 갱신

접근 시행착오(+ 코드)

처음에는 배열을 순회하면서 가장 많은 포도주를 마실 수 있는 방법을 그때 그때 선택하는 그리디로 접근하려고 했다. 하지만, 문제 조건 중 "연속된 세 잔을 모두 마실 수 없다”로 인해 초기에 몇 가지 잔을 선택하는 것이 나중에 더 많은 양을 마실 기회를 상실할 수 있다.

즉, 초기 선택이 후반부의 선택에 영향을 미치며, 이는 그리디 알고리즘으로는 전체 최적 해를 찾을 수 없음을 의미한다.

따라서 DP를 사용해 각 단계의 선택이 전체 해에 미치는 영향을 고려해서, 모든 가능한 선택을 고려하고, 그 중에서 최적의 해를 찾도록 했다.

배운점 또는 느낀점

당연히 그리디라고 생각하고 풀이했는데, DP였다.

각 단계의 최적해가 전체 문제의 최적해를 만들 수 없는 문제는 DP를 고려해서 풀어보자!

13144: List of Unique Numbers(슬라이딩 윈도우)

https://www.acmicpc.net/problem/13144

• 문제 티어 : G4
• 풀이 여부 : Failed
• 소요 시간 : 21:05

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))
unique_elements = set()
ans = 0

left = 0
for right in range(N):
  while arr[right] in unique_elements: # 현재 요소에 중복된 요소가 있는 경우
    unique_elements.remove(arr[left]) # left 요소를 삭제하고
    left += 1 # left 한 칸 오른쪽으로 옮김

  unique_elements.add(arr[right]) # 중복된 요소가 없다면 right 포인터가 가리키는 요소를 추가
  ans += right - left + 1

print(ans)

접근 방식

중복요소가 없어야 하므로 중복요소가 있는 경우 left를 이동해 윈도우를 한 칸 오른쪽으로 옮기고, arr 전체를 right가 순회하며 집합에 추가한다.

접근 시행착오(+ 코드)

백트래킹으로 접근했었지만.. 중복을 제거하지 못했고! 메모리가 아주 한정적이었고! 시간을 초과했고! ex) 1 2 3 4 5 → [1, 2, 3, 4, 5, 12, 23, 34, 45, 123, 234, 345, 1234, 2345, 12345] 위와 같이 정답이 수열 기준으로 한칸씩 밀려가며 나오는 것을 보고 슬라이딩 윈도우라고 생각을 했지만 슬라이딩윈도우를 적용해 구현을 못하겠어서 GPT의 힘을 빌렸다 😂

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))
ans = 0

def backtrack(idx, curr, length):
  global ans
  if length == len(curr):
    ans += 1
  else:
    for i in range(idx, len(arr)):
      if arr[i] not in curr:
        curr.append(arr[i])
        backtrack(idx+1, curr, length)
        curr.pop()

for i in range(1, N+1):
  backtrack(0, [], i)

print(ans)

배운점 또는 느낀점

슬라이딩윈도우 유형의 문제를 많이 풀어야겠다. 백트래킹이라 생각하고 풀었다가는 중복 처리에서 까다로워지고, 시간과 메모리를 너무 잡아먹기에 투포인터와 슬라이딩윈도우를 잘 활용하는 능력을 길러야겠다!

https://www.acmicpc.net/problem/1541

• 문제 티어 : S2
• 풀이 여부 : Failed → Solved
• 소요 시간 : 35:14

정답 코드

import sys
input = sys.stdin.readline

opr = input().rstrip()
parts = opr.split('-')
res = sum(map(int, parts[0].split('+')))
for part in parts[1:]:
  res -= sum(map(int, part.split('+')))

print(res)

접근 방식

이 문제를 풀이하는 핵심 아이디어는

1. - 을 기준으로 수식을 분리
2. - 이후의 모든 수를 괄호로 묶어 한번에 빼주기

로 볼 수 있다.

따라서 입력값을 - 부호를 기준으로 나눠서 parts 배열에 저장한다. ex) 55+10-50+40-20+70 → ['55+10', '50+40', '20+70']

그 다음 -부호가 하나도 없어 parts 배열의 길이가 1인 경우 res값을 한번만 갱신해주고, 1 이상인 경우 parts[0] 이후의 값을 빼주며 최솟값을 산출한다.

접근 시행착오(+ 코드)

괄호를 추가해 값을 최소로 만들기 위해서는, -연산자가 적용되는 범위를 최대로 가져가야 한다. 그리디로 접근해서 - 부호를 찾아 minus_idx 에 뺄셈부호의 인덱스를 저장해주고, 저장된 인덱스를 기반으로 문자를 추가하는 방식으로 접근했다.

최종적으로 문자열 연산식의 계산결과를 리턴하는 함수를 사용해 계산값을 도출하려고 했다.

하지만!! 괄호를 추가하는 과정에서 오류가 있었고, 예제입력3과 같이 0으로 시작하는 값의 연산에서 syntax error가 발생했다.

import sys
input = sys.stdin.readline

opr = list(input().rstrip())
minus_idx = []
for i in range(len(opr)): # worst : O(50)
  if opr[i] == '-':
    minus_idx.append(i) # - 위치 인덱스 기록 (값을 최소로 만들기 위해)

if minus_idx: # - 부호가 1개 이상 있는 경우
  opr.insert(minus_idx[0]+1, '(') # - 부호 뒤에 괄호 추가
  opr.append(')') # 연산식 마지막에 닫는 괄호 추가(여는괄호 추가를 고려한 위치)

  for i in range(len(minus_idx)-1):
    opr.insert(minus_idx[i]+1, '(')
    opr.insert(minus_idx[i+1]+2, ')')

# print(minus_idx)
# print(opr)
eval_opr = eval(''.join(opr))
print(eval_opr)

배운점 또는 느낀점

이상하게 그리디가 너무 안풀린다!!! 그리디 문제 특성을 잘 생각해서 핵심 구현방법을 잘 파악하자!!!

https://www.acmicpc.net/problem/2457

• 문제 티어 : G3
• 풀이 여부 : Failed
• 소요 시간 : 26:51

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
  start_m, start_d, end_m, end_d = map(int, input().rstrip().split())
  arr.append([start_m, start_d, end_m, end_d]) 

arr.sort(key= lambda x: (x[0], x[1], -x[2], -x[3])) # 시작일자와 종료일자를 기준으로(시작달 : 빠른 순, 종료 달 : 느린 순)
start_date, end_date = (3, 1), (11, 30)
latest_date, next_start = (0, 0), (0, 0) # 종료 날짜, 다음 꽃을 심을 날짜

cnt, i = 0, 0

while start_date <= end_date and i < N:
  valid = False
  # 3/1일부터 꽃을 피울 수 있는 조건 찾기
  while i < N and (arr[i][0], arr[i][1]) <= start_date:
    if (arr[i][2], arr[i][3]) > latest_date: # 종료날짜가 가장 늦은 것 찾아서 갱신
      latest_date = (arr[i][2], arr[i][3])
      next_start = (arr[i][0], arr[i][1])
      valid = True
    i += 1 # 다음 꽃 개화시기 순회
  if valid:
    start_date = latest_date # start_date를 갱신해 end_date까지 순회
    cnt += 1
  else:
    break

if start_date <= end_date:
  print(0) # 모든 기간을 커버할 수 없는 경우 : 누적해서 갱신한 시작 일자가 종료 일자보다 적음
else:
  print(cnt)

접근 방식

그리디를 사용해서 푸는 문제임은 알았지만! 구현 과정에서 삐끗해서 한참 고민했던 문제다.

문제의 두 조건을 보면,

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 조건을 만족하는 범위 내에서 최소한의 꽃의 개수를 구해야 하므로 그리디로 접근하는 것이 맞다고 생각했다.

입력값을 받은 다음, 시작일자는 빠른 순으로, 종료일자는 느린 순으로 정렬을 해준다. → O(NlogN) 그 다음 4개의 튜플(또는 배열)형태의 변수를 만들어준다.

• 3/1 : start_date, 11/30 : end_date → 문제 조건의 3/1 시작일자와 11/30 종료일자
• 0/0 : latest_date, 0/0 : next_start → 선택한 시작일자가 종료되는 값, 다음 시작일자

문제를 풀기 위해 start_date를 갱신해가면서 end_date보다 커질 때까지 반복해줬다. 더불어 조건을 만족하는 꽃을 선택했으면, 다음 꽃을 순회하기 위해 i변수로 arr을 순회한다. (i < N)

  while i < N and (arr[i][0], arr[i][1]) <= start_date:
    if (arr[i][2], arr[i][3]) > latest_date: # 종료날짜가 가장 늦은 것 찾아서 갱신
      latest_date = (arr[i][2], arr[i][3])
      next_start = (arr[i][0], arr[i][1])
      valid = True
    i += 1 # 다음 꽃 개화시기 순회

위 코드와 같이 start_date와 latest_date, next_start를 갱신해주면서 start_date ≤ end_date 조건에 위배될 때까지 반복을 계속한다.

배운점 또는 느낀점

우와 이 문제 어려웠다… ^..^ 체크해두고 이 문제는 꼭 다시 풀어봐야겠다!

https://www.acmicpc.net/problem/11054

• 문제 티어 : G4
• 풀이 여부 : Failed → Solved
• 소요 시간 : 21:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

increase_dp = [1 for _ in range(N)]
decrease_dp = [1 for _ in range(N)]

# 최대 증가 부분 수열 길이 찾기
for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and increase_dp[i] < increase_dp[j]+1:
      increase_dp[i] = increase_dp[j] + 1

# 최대 감소 부분 수열 길이 찾기
for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if arr[i] > arr[j] and decrease_dp[i] < decrease_dp[j] + 1:
      decrease_dp[i] = decrease_dp[j] + 1

# 각 지점 기준 최대로 증가하는 부분 수열, 최대로 감소하는 부분 수열의 길이 중 최댓값 산출
ans = max(increase_dp[i] + decrease_dp[i] - 1 for i in range(N))
print(ans)

접근 방식

풀이 방법을 확인하고, 바이토닉 증가 부분 수열에서는 2번의 반복문을 돌려야 함을 알았다.

1. 최대 증가 부분 수열의 길이를 찾기 위한 반복
2. 최대 감소 부분 수열의 길이를 찾기 위한 반복

위와 같이 2번의 (worst : N^2) 반복을 통해 증가/감소 부분수열을 구해준다.

내가 작성했던 코드와 다른 점이 있다면, increase_dp와 decrease_dp를 산출한 뒤, 각 지점 모두 후보가 될 수 있으므로 ans = max(increase_dp[i] + decrease_dp[i] - 1 for i in range(N)) 로 모든 인덱스를 살펴본다.

접근 시행착오(+ 코드)

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

increase_dp = [1 for _ in range(N)]
decrease_dp = [1 for _ in range(N)]

for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and increase_dp[i] < increase_dp[j]+1:
      increase_dp[i] = increase_dp[j] + 1

turn = increase_dp.index(max(increase_dp))

for i in range(turn, N):
  for j in range(i):
    if arr[i] < arr[j] and decrease_dp[i] < decrease_dp[j] + 1:
      decrease_dp[i] = decrease_dp[j] + 1

ans = max(increase_dp) + max(decrease_dp) - 1
print(ans)

처음 접근한 방식은 LIS를 사용해서 최대로 증가하는 위치를 찾고, 그 위치를 기반으로 증가 수열 → 감소 수열로의 전환 후 최대로 감소하는 값을 찾아서 ans를 갱신해줬다. 테스트케이스와 추가로 만든 테스트케이스에 잘 동작했지만 틀렸다.

틀린 이유는 각 위치에서의 최대 증가 부분 수열과 최대 감소 부분수열을 독립적으로 고려해주지 않았기 때문이라고 한다.

바이토닉 부분 수열은 어떤 지점에서도 증가부분과 감소부분이 만나는 지점이 될 수 있고, 각 지점마다 최대 증가 부분 수열과 최대 감소 부분 수열의 합을 고려해줘야 한다는 점을 알았다.

배운점 또는 느낀점

LIS는 생소해서 그런지 잘 활용이 안되어서 아무래도 코드를 외워야 할 것 같다!!! 관련 문제 많이 풀이하면서 필요할 때 바로 떠올려서 사용할 수 있도록 해야겠다 💪

https://www.acmicpc.net/problem/2295

• 문제 티어 : G4
• 풀이 여부 : Failed
• 소요 시간 : 32:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
U = [int(input()) for _ in range(N)]
U.sort()

ans = 0
flag = True
while flag:
  check_num = U.pop() # 큰 수부터 추출

  for i in range(len(U)):
    left, right = i, len(U) - 1

    while left <= right:
      sum = U[i] + U[left] + U[right]
      if sum < check_num:
        left += 1
      elif sum > check_num:
        right -= 1
      else:
        ans = check_num
        flag = False
        break

print(ans)

접근 방식

k번째 수가 최대가 되도록 하려면, k번째는 정렬된 U 중 가장 큰 수가 될수록 좋다. 따라서 입력을 받은 뒤 U를 정렬한다. 정렬 후, 가장 큰 수부터 추출해 check_num으로 지정하며 남은 U배열을 순회한다.

for문 내부에서 left, right를 sum과 check_num의 대소관계 비교를 통해 갱신하며 가장 큰 수가 배열 내부의 세 수의 합으로 구성될 수 있을 때, 반복을 종료한다.

접근 시행착오(+ 코드)

처음에는 DP로 접근해, 배열의 누적합을 계산해놓은 뒤 구간에서의 값을 빼고자 했다.

하지만 문제 설명을 보면 {2, 3, 5, 10, 15}의 집합에서 15를 만드는 세 수의 합을 구할 때, 2+3+10으로 연속된 수가 아니어도 구할 수 있다는 예외케이스를 찾을 수 있다.

따라서 DP로 누적합을 계산하는 것이 아니라, 이분탐색을 적용해 문제를 푸는 방식으로 다시 시도했다.

배운점 또는 느낀점

이분탐색…!! 복병이다 이번주는 그리디, 이분탐색, 해시로 돌려야겠다!

https://www.acmicpc.net/problem/18870

• 문제 티어 : S2
• 풀이 여부 : Solved
• 소요 시간 : 23:38

정답 코드

# O(NlogN)
import sys
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))
set_arr = sorted(list(set(arr))) # 좌표 정렬, 고유 값에 대한 인덱스 매핑
dict_arr = {set_arr[i]: i for i in range(len(set_arr))} # 각 값의 인덱스에 O(1)로 접근

compressed = [dict_arr[x] for x in arr]

print(*compressed)

접근 방식

dict_arr = {set_arr[i]: i for i in range(len(set_arr))} 로 해시테이블을 생성해 인덱스와 중복을 제거한 값으로 key, value 설정 → {-10: 0, -9: 1, 2: 2, 4: 3}

compressed = [dict_arr[x] for x in arr] 코드를 통해 해시테이블에서 key에 해당하는 value를 찾는 방법!

접근 시행착오(+ 코드)

문제를 이해한 바로는, ex) 2 4 -10 4 -9 의 입력이 주어졌을 때, 이를 정렬하면 -10 -9 2 4 4 이고

좌표를 압축해 가장 작은 수부터 0을 시작값으로 부여한다면 0 1 2 3 3 이 된다.

이를 바탕으로 원래 입력값의 순서에 따라 압축된 좌표 값을 넣어주면 된다고 생각했다.

결론적으로 아래와 같이 풀이해 시간초과가 났다. 해시테이블을 사용해야 할 것 같은 느낌!?

# O(N^2)
import sys
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().rstrip().split()))
set_arr = sorted(set(arr)) # O(NlogN)

for i in range(len(arr)): # O(N)
  arr[i] = set_arr.index(arr[i]) # 내부 선형 탐색 : O(N)

print(*arr)

배운점 또는 느낀점

해시테이블 문제 오랜만에 푸는 것 같다!

이번주에 해시테이블 문제를 많이 접해서 시간 줄이는 연습을 해야겠다!

https://www.acmicpc.net/problem/1644

• 문제 티어 : G3
• 풀이 여부 : Failed
• 소요 시간 : 38:52

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
# 에라토스테네스의 체를 사용한 소수 찾기
is_prime = [True] * (N+1)
is_prime[0], is_prime[1] = False, False # 0과 1은 소수 X
for i in range(2, int(N ** 0.5) + 1):
  if is_prime[i]: # 소수인 경우
    for j in range(i*i, N+1, i):
      is_prime[j] = False
primes = [i for i in range(2, N+1) if is_prime[i]]

left, right = 0, 0
ans = 0
total = 0

while right < len(primes):
  if total < N:
    total += primes[right]
    right += 1
  elif total > N:
    total -= primes[left]
    left += 1
  else: # total == N
    ans += 1
    total -= primes[left]
    left += 1

if is_prime[N]: # N이 소수인 경우
  ans += 1

print(ans)

접근 방식

1. 에라토스테네스의 체로 소수 판별 -> $O(NloglogN)$
2. 투포인터로 left, right 갱신 -> worst : O(N)

접근 시행착오(+ 코드)

import sys
input = sys.stdin.readline

N = int(input())
arr = [2, 3]
for i in range(4, N):
  if i % 2 != 0 and i % 3 != 0:
    arr.append(i)

left, right = 0, 0

ans = 0
if N % 2 != 0 and N % 3 != 0 and N % 5 != 0 and N % 7 != 0:
  ans = 1

while right < N and left <= right:
  total = sum(arr[left:right+1])
  if total == N:
    ans += 1
    left += 1
  if total < N:
    right += 1
  if total > N:
    left += 1

print(ans)

소수의 특징을 한자릿수의 소수로 나눠떨어지지 않는 수로 잡아서 투포인터 연산을 해줬다.

연속 구간의 합이 N과 일치해야 하는지 판단해야하므로 left와 right를 모두 0으로 잡아 조건에 따라 갱신해줬는데 틀렸다 🫠

배운점 또는 느낀점

머리가 띵했던 문제다 🤯 에라토스테네스의 체를 사용하는 문제라구요…?

너무 새로워서 풀이 찾아보면서 재밌었다. 시간복잡도를 이렇게나 단축시킬 수 있다니!

투포인터로 접근하는 방식은 맞았지만! N 이하의 모든 소수를 구하는 방법(에라토스테네스의 체)과, 투포인터의 갱신과정에서 약간의 오류가 있었다.

에라토스테네스의 체로 소수를 찾으면 $O(NloglogN)$ 이라니 내가 작성했던 코드 대비 시간효율이 비약적으로 높아졌다... 외워야겠다!!

https://www.acmicpc.net/problem/1759

• 문제 티어 : G5
• 풀이 여부 : Solved
• 소요 시간 : 17:49

정답 코드

import sys
input = sys.stdin.readline

L, C = map(int, input().rstrip().split())
candidates = sorted(list(map(str, input().rstrip().split())))

ans = []

def backtrack(start, curr):
  if len(curr) == L:
    aeiou_cnt = sum(1 for c in curr if c in 'aeiou')
    if aeiou_cnt >= 1 and len(curr) - aeiou_cnt >= 2:
      ans.append(curr[:])
      return

  for i in range(start, C):
    curr.append(candidates[i])
    backtrack(i+1, curr)
    curr.pop()

backtrack(0, [])
for a in ans:
  print(*a, sep='')

접근 방식

저번 로또 백트래킹 문제와 거의 동일하다!

검색 시간을 O(1)로 가져가려고 처음에는 모음의 갯수를 계산할 때,

딕셔너리로 모음을 관리했는데! 굳이 그러지 않아도 충분했다…

시간복잡도의 경우,

1. C개 중 L개를 선택하는 조합의 시간복잡도 : $O(C! / (L! * (C-L)!))$
2. 각 조합을 검사하는 시간복잡도 : 조합의 길이만큼 → $O(L)$

따라서 전체 시간복잡도는 $O((C! / (L! * (C - L)!)) * L)$ 이다.

그리고 아주 파이써닉한 코드!

aeiou_cnt = 0
for c in curr:
    if c in 'aeiou':
        aeiou_cnt += 1

위 코드를

aeiou_cnt = sum(1 for c in curr if c in 'aeiou')

이렇게 축약할 수 있다!

배운점 또는 느낀점

은근 조합의 중복을 방지하기 위한 시작점 갱신을 계속 빼먹는 경우가 많다.

중복을 방지하고자 할 때에는 backtrack 함수에 start 값과 curr배열을 함께 넘겨주는 것 잊지 말자!

https://www.acmicpc.net/problem/1932

• 문제 티어 : S1
• 풀이 여부 : Solved
• 소요 시간 : 43:57

정답 코드

# O(N^2)
import sys
input = sys.stdin.readline

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

dp = [[0]*N for _ in range(N)] # 층 별 최대 값
dp[0][0] = arr[0][0]

for i in range(1, N):
  for j in range(i+1):
    # 대각선 왼쪽에서 내려온 경우
    if j > 0:
      left = dp[i-1][j-1] + arr[i][j]
    else:
      left = 0
    # 대각선 오른쪽에서 내려온 경우
    if j < i:
      right = dp[i-1][j] + arr[i][j]
    else:
      right = 0
    dp[i][j] = max(left, right)

print(dp)
print(max(dp[N-1]))

접근 방식

처음엔 그리디라고 생각했지만, 이전 단계까지의 합을 구하는 문제이기에 DP로 풀이방법을 돌렸다.

대각선 왼쪽과 오른쪽에서 내려오는 값중 더 큰 값을 골라 누적합을 구하면 되는 문제!

배운점 또는 느낀점

DP는 코드 구현보다 점화식을 찾는 데에 정말 압도적으로 시간이 많이 든다.

관계 잘 파악하기!

https://www.acmicpc.net/problem/17835

• 문제 티어 : G2
• 풀이 여부 : Failed
• 소요 시간 : 45:32

정답 코드 1 : 면접장 → 도시로 가는 풀이 (정답)

import sys, heapq
input = sys.stdin.readline

N, M, K = map(int, input().rstrip().split())
arr = [[] for _ in range(N+1)] # 1 ~ N개의 도시

for _ in range(M): # O(M)
  u, v, c = map(int, input().rstrip().split())
  arr[v].append((u, c)) # v -> u : c (시작점을 면접장으로 설정할 것이므로 u -> v 경로를 v -> u로 바꿔서 보기)

K_pos = list(map(int, input().rstrip().split())) # 면접장의 위치

def dijkstra(arr, starts):
  costs = [float('inf') for _ in range(N+1)]
  pq = []

  # 면접장 위치에서 시작하도록 다익스트라 초기화
  for start in starts:
    heapq.heappush(pq, (0, start)) # 누적비용, 노드
    costs[start] = 0

  while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    if costs[cur_node] < cur_cost:
      continue
    for next_node, cost in arr[cur_node]:
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]:
        costs[next_node] = next_cost
        heapq.heappush(pq, (next_cost, next_node))

  return costs

dist = dijkstra(arr, K_pos)

max_dist, max_city = 0, 0
for i in range(1, N+1): # 가장 먼 노드 탐색 O(N)
  if i not in K_pos and dist[i] > max_dist:
    max_dist = dist[i]
    max_city = i

print(max_city)
print(max_dist)

접근코드 2 : 도시 → 면접장으로 가는 풀이 (시간초과)

# O(N * (MlogM))
import sys, heapq
input = sys.stdin.readline

# N: 도시의 수, M: 도로의 수, K: 면접장의 수
N, M, K = map(int, input().split())
arr = [[] for _ in range(N + 1)]

# 도로 정보 입력 받기 (단방향)
for _ in range(M):
    u, v, c = map(int, input().split())
    arr[u].append((v, c))  # u에서 v로 가는 비용이 c

# 면접장 위치 입력 받기
K_pos = list(map(int, input().split()))

# 다익스트라 알고리즘
def dijkstra(start):
    costs = [float('inf')] * (N + 1)
    costs[start] = 0
    pq = [(0, start)]

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if costs[cur_node] < cur_cost:
            continue

        for next_node, cost in arr[cur_node]:
            distance = cur_cost + cost
            if distance < costs[next_node]:
                costs[next_node] = distance
                heapq.heappush(pq, (distance, next_node))

    return costs

# 각 도시에서 면접장까지의 최단 거리 중 최댓값 찾기
max_dist, max_city = 0, 0

for start_city in range(1, N + 1): # O(N)
    if start_city in K_pos:
        continue
    dist = dijkstra(start_city) # O(MlogM)
    # 면접장 중 가장 가까운 거리 찾기
    min_k = min([dist[loc] for loc in K_pos])
    if min_k > max_dist:
        max_dist = min_k
        max_city = start_city

print(max_city)
print(max_dist)

접근 방식

시간초과가 나지 않으려면 면접장에서 각 도시로의 최단거리를 기준으로 각 비용을 계산한 뒤,

그 중에서도 가장 먼 도시와 그 비용을 산출하는 역발상으로 접근해야 한다.

이를 위해서는,

1. 입력으로 받는 u → v : c 의 시작노드 → 도착노드 : 비용 을 역으로 저장 (면접장 → 도시로 가기때문)
2. 다익스트라 코드 내부에서 면접장의 개수만큼 우선순위 큐에 push
3. 다익스트라에서 비용을 비교해가며 최소 비용으로 경로 생성
4. 면접장이 아닌 도시 중에 최댓값을 가지는 도시와 그 비용 계산

위와 같은 로직으로 정답을 찾아나갈 수 있다.

접근 시행착오(+ 코드)

처음 생각한 접근 방식으로는,

1. 1~N의 도시를 순회하며, K개의 면접장이 위치한 K_pos 중, 가장 가까운 면접장을 찾아준다.
2. 다익스트라 함수의 final(도착점)으로 설정해서 N번의 다익스트라 함수를 호출한다.

위 방식으로 문제를 풀이했다. (접근코드 2 참조)

하지만 해당 문제에서의 N의 범위는 100,000이며 도로의 수인 M의 범위는 500,000이다.

기본적인 다익스트라 알고리즘은 간선의 개수를 E라고 했을 때 O(ElogE)임을 고려해,

접근코드 2의 방식은 N번의 순회 후 간선의 개수가 M인 입력값으로 다익스트라 알고리즘을 호출하기에

O(N * MlogM)의 시간복잡도가 나옴을 확인할 수 있다.

즉, 시간 제한인 1초를 한참 넘겨서 시간초과가 날 수밖에 없다.

배운점 또는 느낀점

다익스트라 알고리즘의 역발상이 필요했던 문제다.

시간초과가 나서 접근코드 2는 졌지만 잘 싸운 코드로 … ^.^

문제를 보고 특정 알고리즘을 사용하면 되겠다는 생각이 들어도! 그 알고리즘을 적용하기 위한 입력값의 전처리에 얼만큼의 비용이 필요한지 고려하자.

https://www.acmicpc.net/problem/13913

• 문제 티어 : G4
• 풀이 여부 : Failed → Solved
• 소요 시간 : 26:28

정답 코드

시간복잡도 : O(V+E) ⇒ O(V + 3V) ⇒ O(4V)

• worst V : 200001
• worst E : 3 * 200001

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 200001
parents = [-1] * 100001 # 부모노드 기록(역추적으로 사용)

def bfs(x):
  dq = deque([x]) # 현재 위치
  visited[x] = True

  while dq:
    x = dq.popleft()
    if x == K:
      break

    for nx in (x-1, x+1, 2*x):
      if not visited[nx] and 0 <= nx <= 100000:
        dq.append(nx)
        visited[nx] = True
        parents[nx] = x # nx도착 이전 노드가 x임을 기록

def make_path(N, K, parents):
  path = []
  while K != N: # 시작 지점 N에 도달하기까지 역추적
    path.append(K)
    K = parents[K] # K의 부모 지점으로 이동
  path.append(N) # 최종으로 시작 지점 추가
  return list(reversed(path))

bfs(N)
path = make_path(N, K, parents)
print(len(path) - 1)
print(*path)

접근 방식

1. 부모 노드를 기록하며 역추적으로 경로를 파악하는 방법

아래 첨부한 잘못된 접근 방식에서, deque에 원소를 추가할 때 경로를 바로 넣어주는 것이 아니라,

deque에서 추출한 x의 다음 노드가 될 nx를 순회하면서,

parents[nx] = x

위와 같이 nx 노드로 도착하기 이전의 노드가 x였음을, 즉 부모노드를 배열에 기록해준다.

이 때 parents 배열은 N의 최댓값인 100000(메모리 초과 방지를 위해 100001로 초기화)로 크기를 지정해줬다.

1. visited의 범위 수정

내 로컬 환경에서 문제를 풀었을 때는 분명 정답이 나오는데, 백준 채점 결과 런타임 에러가 났다.

그 이유는 visited의 범위를 100001로 초기화해뒀기 떄문.

N이 이동할 수 있는 방법이 x-1, x+1이라면 100001로 visited의 범위를 초기화해도 무방하지만,

만약 N이 다음 노드로 2*x를 선택했을 때 최악의 경우 200000의 값을 가질 수 있다.

따라서 visited의 범위를 200001로 초기화해줬더니 맞았다.

1. parents를 통한 경로 역추적

def make_path(N, K, parents):
  path = []
  while K != N: # 시작 지점 N에 도달하기까지 역추적
    path.append(K)
    K = parents[K] # K의 부모 지점으로 이동
  path.append(N) # 최종으로 시작 지점 추가
  return list(reversed(path))

bfs 함수에서 parents 배열의 값을 넣어준 방식을 보자면, K부터 N까지의 경로가 역순으로 저장되어 있다.

그말인 즉슨 K를 시작으로 K = parents[K] 를 통해 K의 부모 지점으로 이동하면서 경로를 찾을 수 있다는 점이다.

문제 출력에서 요구한 시작값 N과 종료값 K를 path에 추가한 뒤, 역순으로 리턴하면 이동 경로가 나온다.

잘못된 접근 방식(+ 코드)

처음에는 BFS를 통해 deque 내부의 원소를 추가하면서

1. 시작 노드를 저장할 때
2. 덱에 다음 노드를 추가할 때

이렇게 두 번 path에 값을 갱신해줬다.

그 결과 소요 시간은 정답과 일치하게 나왔지만, path가 아주 이상하게 나왔다.

(다시 생각해보면 너무 당연한 결과다… BFS로 x-1, x+1, 2*x를 돌며 모두 path에 추가했으니까)

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 100001

def bfs(x):
  dq = deque([(x, 0)]) # 현재 위치, 이동 횟수
  path = []

  visited[x] = True
  path.append(x) # 경로 저장

  while dq:
    x, move = dq.popleft()
    if x == K:
      return move, path

    for i in (x-1, x+1, 2*x):
      if not visited[i]:
        dq.append((i, move+1))
        path.append(i)
        visited[i] = True

move, path = bfs(N)
print(move)
print(*path)

배운점 또는 느낀점

백준에 있는 숨바꼭질 문제 세트를 풀어보면서, 정말 조금씩 다른 문제에도 풀이 방법이 많이 차이남을 느꼈다.

기본 BFS를 잘 활용하는 방법을 배운 문제다!

https://www.acmicpc.net/problem/1600

• 문제 티어 : G3
• 풀이 여부 : Failed → Solved
• 소요 시간 : 38:25

정답 코드

from collections import deque

K = int(input())
W, H = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(H)]

def bfs():
  visited = [[[False] * (K + 1) for _ in range(W)] for _ in range(H)] # x, y 위치, k번 말처럼 이동한 경우 방문 여부
  dq = deque([(0, 0, 0, K)]) # (x좌표, y좌표, 동작수, 남은 말 이동 횟수)

  dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
  kx, ky = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]

  while dq:
    x, y, move, k_limit = dq.popleft()

    if x == H - 1 and y == W - 1:
      return move

    if k_limit > 0: # 말처럼 이동 처리
      for i in range(8):
        nx, ny = x + kx[i], y + ky[i]
        if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k_limit - 1] and arr[nx][ny] == 0:
          visited[nx][ny][k_limit - 1] = True
          dq.append((nx, ny, move + 1, k_limit - 1))

    for i in range(4): # 일반 이동 처리
      nx, ny = x + dx[i], y + dy[i]
      if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k_limit] and arr[nx][ny] == 0:
        visited[nx][ny][k_limit] = True
        dq.append((nx, ny, move + 1, k_limit))

  return -1

print(bfs())

접근 방식

말처럼 이동이 가능한 K번의 횟수를 초과할 경우, x, y 좌표의 값 업데이트를 kx, ky 에서 dx, dy로 바꿔주는 방식이다.

visited를 2차원 배열로 관리했었고, 말처럼 이동 가능한 횟수를 별도의 변수로 관리했었는데, 값 업데이트가 의도한대로 되지 않아서

visited 배열의 형태를 2차원 → 3차원 : x위치, y위치, k번 말처럼 이동한 경우 방문 여부 로 바꿔서 관리해줬다.

deque에 추가하는 자료 역시 (x좌표, y좌표, 동작수, 남은 말 이동 횟수) 로 바꿔줬더니 의도했던대로 동작한다!

배운점 또는 느낀점

W, H 범위 지정이 헷갈렸다. 그래서 index out of range가 여러번 떴었다 😅

범위 체크 잘 하기!

https://www.acmicpc.net/problem/13549

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 29:25

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())

def bfs(cur, dest):
  dq = deque([(cur, 0)]) # 노드, 초
  visited = [False] * 1000001
  visited[cur] = True

  while dq:
    x, sec = dq.popleft()
    if x == dest:
      return sec

    for nx in (x-1, x+1, 2*x):
      if 0 <= nx <= 100000 and not visited[nx]:
        visited[nx] = True
        if nx == 2*x:
          dq.appendleft((nx, sec))
        else:
          dq.append((nx, sec+1))
  return -1

print(bfs(N, K))

접근 방식

이 문제 역시 BFS로 풀이하면서 최소 비용을 위해 우선적으로 처리하면 유리한 조건이 있는 문제다.

    for nx in (x-1, x+1, 2*x):
      if 0 <= nx <= 100000 and not visited[nx]:
        visited[nx] = True
        if nx == 2*x:
          dq.appendleft((nx, sec))
        else:
          dq.append((nx, sec+1))

위와 같이 2*x로 0초가 소요되는 값을 우선적으로 덱에서 처리하기 위해 appendleft() 로 넣어줌으로써 최소 시간을 계산할 수 있다.

잘못된 접근 방식(+ 코드)

# 오답 코드
import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 1000001

def bfs(cur):
  dq = deque([(cur, 0)]) # 노드, 초
  path = ['-1', '1', '2']
  visited[cur] = True

  while dq:
    x, sec = dq.popleft()
    if x == K:
      return sec

    for i in range(3):
      if i == 0 or i == 1:
        nx = x + int(path[i])
      else:
        nx = x * int(path[i])

        if 0 <= nx < 100001 and not visited[nx]: 
          if i == 2:
            dq.append((nx, sec))
            visited[nx] = True
          else:
            dq.append((nx, sec+1))
            visited[nx] = True
  return -1

print(bfs(N))

최소 시간을 계산하기 위해서는 순간이동(0초 소요)이 우선적으로 실행되어야 하는데, 이에 대한 처리를 해주지 않았고 또 답이 올바르게 출력되지 않았다.

또한 갈 수 있는 방법 (x-1, x+1, 2*x)을 문자열로 다루어 코드 가독성이 좋지 않았다.

배운점 또는 느낀점

• BFS 유형의 문제에서 Queue를 사용한다고 무조건 FIFO만 사용한다는 생각 버리기!
• 조건에 따라 우선적으로 실행되어야 하는 좌표가 있을 수 있음을 꼭 고려하기!

https://www.acmicpc.net/problem/1261

• 문제 티어 : G4
• 풀이 여부 : Solved
• 소요 시간 : 24:16

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

M, N = map(int, input().rstrip().split()) # M : 가로, N : 세로
arr = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]

def bfs(x, y):
  dq = deque([(x, y)])
  visited[x][y] = 0 # 운영진의 현재 위치(0, 0)

  dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
  while dq:
    x, y = dq.popleft()
    for i in range(4):
      nx, ny = x + dx[i], y + dy[i]
      if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
        if arr[nx][ny] == 0: # 벽을 뚫지 않아도 되는 경우
          dq.appendleft((nx, ny))
          visited[nx][ny] = visited[x][y]
        else: # 벽을 뚫어야 하는 경우
          dq.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

  return visited[N-1][M-1]

print(bfs(0, 0))

접근 방식

BFS 기본 문제와 똑같은 풀이방법대로 작성했다.

다만 이 문제에서 주의해야 할 점은 “벽을 최소 몇 개 부수어야 하는지 구하는”부분이다.

범위 내의 좌표임과 동시에 방문하지 않은 좌표 + 벽을 뚫지 않고 갈 수 있는 좌표의 우선 고려 로 조건을 설정해야한다.

      if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
        if arr[nx][ny] == 0: # 벽을 뚫지 않아도 되는 경우
          dq.appendleft((nx, ny))
          visited[nx][ny] = visited[x][y]
        else: # 벽을 뚫어야 하는 경우
          dq.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

따라서 기존 BFS에서는 deque에 append() 를 해주는 것이 일반적이었지만,

이 문제의 경우 arr[nx][ny]의 값이 0인 경우를 우선적으로 고려해야한다.

그렇기에 arr[nx][ny]의 값이 0인 경우는 FIFO의 특징을 가진 Queue(파이썬에서 사용하는 Deque은 Queue를 두개 붙인 형태이기에 append, appendleft, pop, popleft가 모두 가능하다.)이지만,

우선적으로 처리하기 위해 appendleft() 로 (nx, ny)를 넣어줬다.

배운점 또는 느낀점

너비우선탐색에서 같은 너비의 좌표여도 우선적으로 처리해야 하는 조건을 다루는 방법을 배웠다!