2025.04.09

TIL(TODAY I LEARN)

---

• WEEK04 :
  동적 프로그래밍, 그리디 알고리즘
  CSAPP 3장. 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)

• 남은 알고리즘 문제들을 풀고 있다. 너무 어렵다.

---

2253 - 점프 - 골드4

문제 링크 - https://www.acmicpc.net/problem/2253

내 코드

 # BFS 방식 -> 최초 도달 시 이미 최단거리임.
 
 import sys
 from collections import deque, defaultdict
 input = sys.stdin.readline
 n,m = map(int,input().split())
 
 small = set(int(input().strip()) for _ in range(m))
 
 INF = float('inf')
 visited = defaultdict(lambda : False)
 
 def bfs():
     q = deque()
     q.append((1,0))
     visited[(1,0)] = True
     cnt = 0
     
     while q:
         for _ in range(len(q)):
             now_stone,now_jump = q.popleft()
             if now_stone == n:
                 return cnt
             for j in [now_jump-1,now_jump,now_jump+1]:
                 next_stone = j + now_stone
                 if j >= 1 and next_stone <= n and next_stone not in small and visited[next_stone,j] == False:
                     visited[(next_stone,j)] = True
                     q.append((next_stone,j))
         
         cnt += 1
     return -1
 
 print(bfs())

문제 분류

• 다이나믹 프로그래밍

---

• 너무 어렵다 DP!
  TSP 문제를 풀고 있는데 DFS + 백트래킹만 이용하고 dp를 못하겠다. 포기
  내일 오전에 시험치고 심기일전해서 도전해봐야겠다.
  오늘도 내일도 화이팅