[코테] 백준 class 3 완료 & 정리

🗓️ 2023.07.28 ~ (7/30~8/3 여행으로 인한 공백) ~ 2023.08.09

++까지 하고 싶었는데 시간상 마음이 급해져서(벌써 8월 ㅁㅊㅠㅠ) 일단 에센셜까지만 풀었다.

class 3에서는 다이나믹 프로그래밍, 그래프 탐색(DFS/BFS), 집합과 맵, 우선순위 큐, 분할 정복, 좌표 압축 문제들이 있었고, 이중에서도 DP와 DFS/BFS가 중점이 되는 거 같았다.

문제만 보고 적합한 알고리즘을 떠올리기가 생각보다 어려워서 많이 막혔고 (특히 DP랑 BFS) 코드는 크게 꼬는거 없이 DP와 DFS/BFS의 정석 코드 자체만으로도 풀리는 문제들이었다. (안꼬아도 어려운데 꼬이면 얼마나 어려울까.....)

그리고 알고리즘 유형 불문 시간초과가 엄청나게 많이 떴고.. 접근 방식이 아예 틀린것도 있었지만 정말 아주 조금의 차이 때문에 시간초과가 나오기도 했다.

풀면서 정리해두고 싶었던 것들을 모아서 올린다.

---

📝 짧은 메모들

📌 비트마스크, 누적합, 활동선택(그리디), 좌표압축

📌 동적계획법(DP) 푸는 법
-[1003] 피보나치 함수
-[1463] 1로 만들기
-[9095] 1, 2, 3 더하기

• N을 구하기 위해 이전 값들을 활용해야 한다.
• N을 구하려면 0, 1, 2, ..., N-1까지 차례대로 모든 값을 다 구해야한다.
• 점화식을 세워야한다.
• N번째 '최솟값' = 이전에 계산해둔 0번째부터 N-1번째까지 중 일부 '최솟값'들의 합
• N만 딱 두고 뭘 어떻게 구해야될지 모르겠을때 이전값을 활용해서 구하는 것도 생각해보기

📌 런타임에러(RecursionError) 발생 시
-[11724] 연결 요소의 개수
-[1012] 유기농 배추
파이썬이 정한 최대 재귀 깊이보다 내가 작성한 재귀의 깊이가 더 깊어질 때 런타임에러(RecursionError)가 발생하는데, BOJ의 채점 서버에서 이 값은 1,000이다. 따라서 1,000보다 깊이 재귀를 실행하면 런타임에러가 난다. 이를 해결하는 방법은 2가지다.
1. 재귀를 사용하지 않고 풀기
ex. DFS 재귀 풀이 -> DFS 스택 풀이 or BFS 풀이
2. 최대재귀깊이 변경하기

import sys
sys.setrecursionlimit(10000)

경우에 따라 두 방법을 적절히 사용하되, 2번의 경우에는 채점서버가 감당할 수 있는 정도까지만 늘려야 한다.

📌 인덱스 가져오는 시간 줄이기
-[18870] 좌표 압축
index() 라이브러리로 위치를 찾을 때 시간복잡도가 O(N)이 걸리기 때문에 얘 때문에 시간초과가 날 수 있다. 이럴때 딕셔너리로 인덱스를 O(1)의 시간복잡도로 가져올 수 있게 하는 방법이 있다.

📌 DFS/BFS 시간초과날때
-[1697] 숨바꼭질
기본적으로 그래프 탐색에서 시간초과가 날때는 방문여부가 제대로 체크되고 있는지 확인한다. 제대로 체크하고 있는데도 시간초과가 난다면 방문여부를 어떻게 체크하고 있는지를 봐야 한다.
방문여부 확인을 위해 visited를 사용할때 Boolean 인덱싱으로 사용하는게 아니라 방문한 노드를 append로 붙일 경우에 시간이 오래 걸리게 된다. 따라서 웬만하면 visited = [False] * 노드개수로 방문여부를 확인하도록 하자.
cf) '목적지까지 가는 가장 빠른 시간(최단경로)'과 같이 표현이 바뀌어도 최단경로 탐색이라는 것을 알아내기

---

[9095] 1, 2, 3 더하기

DP 일거라고 생각은 했는데 점화식을 아무리 생각해도 모르겠어서 힌트를 찾아봤다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

n을 구하는 경우
= n-1까지 구하고 맨 뒤에 1을 더하는 경우
+ n-2까지 구하고 맨 뒤에 2를 더하는 경우
+ n-3까지 구하고 맨 뒤에 3을 더하는 경우

쉬운 문제였는데.. 못풀었다 ㅠㅠ

import sys
input = sys.stdin.readline

N = int(input())
for _ in range(N):
  count = [1, 2, 4]
  n = int(input())
  for i in range(3, n):
    s = count[i-1] + count[i-2] + count[i-3]
    count.append(s)
  print(count[n-1])

---

[1012] 유기농 배추

그래프 탐색으로 모든 연결트리의 개수를 찾는 문제..인데 생각을 너무 과하게 했던지 귀찮은거 안하려고 피하느라 너무 덜했던지..

(i,j) 형태의 노드로 그래프 탐색을 하는게 익숙치 않아서 제대로 못 푼 거 같다. (=> 결론적으로 그래프를 만들진 않았다)

배추가 심어져있는 밭을 2차원배열로 쭉 나타내고, 순서대로 돌면서 찾은 배추가 심어져있는 지점을 루트노드 삼아 여기에 연결된 모든 배추들을 방문하는(뽑는?) 방식 (DFS)

그래프를 따로 구성하지 않고, 위에서 주어진 밭 정보를 visited 겸용으로 사용해서 DFS 탐색을 한다는게 그동안 푼 그래프 문제와는 다르게 눈에 띄는 점?

배운점은 문제에서 딱봐도 그래프 탐색 혹은 경로찾기, 이어져있는 점들 찾기같은 포인트가 보일때 귀찮다고 DFS/BFS를 안하려들지 말아라.. 다른 방법으로 하면 어찌됐든 중간에 막힌다 에휴

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(ground, i, j, M, N):
  ground[i][j] = 0
  adjacent = []
  
  if 0 <= i-1 < N and 0 <= j < M:
    adjacent.append((i-1,j))
  if 0 <= i+1 < N and 0 <= j < M:
    adjacent.append((i+1,j))
  if 0 <= i < N and 0 <= j-1 < M:
    adjacent.append((i,j-1))
  if 0 <= i < N and 0 <= j+1 < M:
    adjacent.append((i,j+1))
    
  for a, b in adjacent:
    if ground[a][b] == 1:
      dfs(ground, a, b, M, N)
  
def main():
  T = int(input())
  for _ in range(T):
    M, N, K = map(int, input().split())
    ground = [[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
      X, Y = map(int, input().split())
      ground[Y][X] = 1

    answer = 0
    for i, row in enumerate(ground):
      for j, r in enumerate(row):
        if r == 1:
          dfs(ground, i, j, M, N)
          answer += 1

    print(answer)

main()

---

[1074] Z

처음에 재귀로 풀었는데 답은 맞았는데 시간초과가 났다. 하나하나 재귀호출로 카운트할게 아니라 (r,c)가 포함된 사분면만 세면 되겠지 -까지는 생각을 했는데.. 코드로 옮기려니 도저히 머리가 안굴러가서 답을 찾아봤다.

해답 참고한 블로그 : 백준 1074번 - Z ( python )

• 첫번째 코드 (시간초과)

import sys
input = sys.stdin.readline

cnt = 0

def visit_z(board, i, j, N, r, c):
  global cnt
  if N == 1:
    board[i][j] = 1
    if r == i and c == j:
      print(cnt)
    cnt += 1
    board[i][j+1] = 1
    if r == i and c == j+1:
      print(cnt)
    cnt += 1
    board[i+1][j] = 1
    if r == i+1 and c == j:
      print(cnt)
    cnt += 1
    board[i+1][j+1] = 1
    if r == i+1 and c == j+1:
      print(cnt)
    cnt += 1
    return

  visit_z(board, i, j, N-1, r, c)
  visit_z(board, i, j+2**(N-1), N-1, r, c)
  visit_z(board, i+2**(N-1), j, N-1, r, c)
  visit_z(board, i+2**(N-1), j+2**(N-1), N-1, r, c)

def main():
  N, r, c = map(int, input().split())
  board = [[0 for _ in range(2**N)] for _ in range(2**N)]
  visit_z(board, 0, 0, N, r, c)

main()

• 고친 코드(정답)

import sys
input = sys.stdin.readline

N, r, c = map(int, input().split())
answer = 0

while N > 0:
  half = 2**(N-1)
  # 1사분면
  if r < half and c < half:
    answer += 0
  # 2사분면
  elif r < half and c >= half:
    answer += half * half
    c -= half
  # 3사분면
  elif r >= half and c < half:
    answer += half * half * 2
    r -= half
  # 4사분면
  elif r >= half and c >= half:
    answer += half * half * 3
    r -= half
    c -= half
  N -= 1

print(answer)

앞으로는 (특히 시간초과가 났을 때) 자세한 값이 필요하지 않으면서 뭉터기로 계산할 수 있는 부분은 뭉터기로 다뤄서 스킵하고, 하나하나 봐야하는 부분만 탐색하는 방식으로 풀어야겠다. 말은쉽지