낭중지추

백준 문제 바로가기

실버2

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

길이 기록용 리스트를 1로 만들어서 각 요소의 길이를 기록

i와 j를 사용해서 현재값i과 이 전 값들(j들)의 요소 크기를 비교하고 현재값이 크다면 이전 값 요소의 길이 + 1과 현재값을 비교해서 큰 값을  현재값의 길이로 저장.

이 전 값들의 데이터를 재사용하여 dp로 풀 수 있다.

import sys
input = sys.stdin.readline

N = int(input())

lst = list(map(int, input().split()))

# lst 수열과 같은 수열을 만들어
lenlst = [1] * len(lst)

#i번째랑 이 전 값을 비교해서 크면 lenlst에 길이로 큰 값을 저장, 작으면 ㅃㅇ
#max()로 비교해서 넣는 이유는 현재 자신의 길이값 vs 나보다 작은 요소의 길이 뒤에 붙으면 큰 값 중 큰 것에 붙는 것

for i in range(len(lst)):
  j = 0
  for j in range(i):
    
    if lst[j] < lst[i] :
      lenlst[i] = max( lenlst[i], lenlst[j]+1 )

print(max(lenlst))

처음에 접근할 때에 어떻게 비교를 해야할지 판단이 안 섰다.

i를 늘려가면서 j를 0으로 초기화하고 i전까지 j하나씩 비교를 해가면 된다.

그리고 길이 리스트를 만들어서 1로 초기화해서 길이를 저장해두고, 

j<i일 때에 해당 j의 길이 뒤에 붙을 수 있기 때문에 i의 길이값을 j길이값+1 과 i길이값을 비교해서 큰 쪽에 붙는다.

*길이 수열 만들기, 탐색을 이중포문으로 현재값과 이전값 비교

*왜 이전값을 기준으로 탐색할까? 왜 다음 j는 i범위 전에서만 확인할까?

 i=0을 계산할 때 j=2(미래)를 참조하면

→ lenlst[2]는 아직 제대로 계산이 안 된 초기값 1

→ 나중에 lenlst[2]가 업데이트돼도 lenlst[0]은 이미 틀린 값으로 고정

i 이전에 있는 것들이 다 확정된 후에 계산되어야 하는데, range(len(lst))는 아직 확정 안 된 미래 값을 미리 참조해버리는 것이기 때문

풀이

Top-down 풀이

dp 딕셔너리 구조를 사용한다.

N을 나타내는 방법의 수를 구하려면 (N-1) + (N-2) + (N-3)을 구해야한다.

초기식은 3까지 구해놓는다.

import sys
input = sys.stdin.readline

#갯수 입력
N = int(input())

#Top-dowm
memo = {}

def dfs(K) :
  #base case
  if K == 1 : return 1
  if K == 2 : return 2
  if K == 3 : return 4

  #memo
  if K in memo:
    return memo[K]

  #memoization
  if K not in memo:
    memo[K] = dfs(K-1) + dfs(K-2) + dfs(K-3)
    return memo[K]
  
for _ in range(N):
  K = int(input())
  print(dfs(K))

bottom-up 풀이

dp[] 배열 자료구조를 사용한다. 탑다운은 필요한 것만 계산하되 느리지만, 바텀업은 전부를 계산하되 빠르다. 이 문제는 최대가 10이므로 이 방법이 더 적절할 수 있다.

빈 배열을 크기에 맞게 먼저 선언한다

dp[3]까지 초기식에 값을 넣어준다.

점화식 - 범위의 수를 미리 다 계산한다.

이후에 바로 찾아서 리턴한다.

#갯수 입력
N = int(input())

#배열
dp = [0] * 11

#초기식
dp[1] = 1
dp[2] = 2
dp[3] = 4

#점화식 - 미리 다 계산
for i in range(4, 11) :
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(N) :
  k = int(input())
  print(dp[k])

백준 문제 바로가기

실버1

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

문제

풀이

최단거리 구하는거니까 BFS로 풀어야겠다고 생각함.

계단문제처럼 DP쓰면 안되나? 했는데 사이클이 있어서 뱅뱅 돌 수 있으니 BFS.

그리고 방문했던 곳을 다시 방문하면 무한루프 돌 수 있으니 방문 리스트 만들어서 표시해둬야 함.

코드

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

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

visited = [False] * 100001

def bfs (N,K) :
  q = deque()
  visited[N] = True
  q.append((N, 0))

  while q: 
    x, time  = q.popleft()

    if x == K : 
      return time

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

print(bfs(N,K))

- visited 배열의 크기를 범위에 맞게 만들어야 하는 구나 (여기선 0부터니까 0포함 100001), False로 초기화

- 방향을 반영해서 하나씩 꺼낼 때에 for nx in (n-1, n+1, n*1) 이런식으로 계산식을 만들어서 계산 한 뒤 하나씩 꺼내는 방법이 있군...

- 방문 표시는 큐에 넣을 때에 (방문 -> 인큐) 해야 함.

백준 문제 바로가기

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이

#최단거리 - bfs
#시작위치부터 dist 1, 1로만 지나다녀야 하고 상하좌우 움직일 수 있음
#1,1부터 시작해서 (N(세로 y),M(가로 x))에서 break
# 좌표와 거리를 함께 저장하여 넘겨, 좌표 이동할때 거리 + 1

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

N, M = map(int, input().split())

#grid
grid = []

for _ in range(N) :
  grid.append(list(map(int, input().strip()))) #공백없는 입력은 strip

dir = [(1,0), (0,1), (0, -1), (-1, 0)]

def bfs(a, b, dist) :
  q = deque()
  q.append((a,b,dist))
  grid[a][b] = 0

  while q:
    a, b, dist = q.popleft()

    # 도달
    if a == N-1 and b == M-1:
      return dist

    for x, y in dir :
      nx = a + x
      ny = b + y

      if nx >= 0 and nx < N and ny >= 0 and ny < M and grid[nx][ny] == 1:
        q.append((nx, ny, dist + 1))
        grid[nx][ny] = 0

  return dist

result = bfs(0,0,1)
print(result)

헷갈리는 것:

입력받을 때 공백이 있는 경우는 split()으로 받고, 없는 경우는 strip()으로 받기

백준 문제 바로가기

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

풀이

문제를 풀기 전 어떤식으로 해결하면 좋을지 설계를 했다.

처음에 이렇게 생각하고 문제를 풀었는데 굳이 단지 변수를 만들지 않아도 된다는 것을 알게되었음

result 리스트에 집 카운트를 넣고 길이를 구하면 되는거였다!

그리고 중요한 건 0으로 방문 처리를 해주는 것과 범위 내에서만 인큐, dfs를 하는 것, 처음 들어올 때 카운트를 1로 해줬으니 반복할 때에 방문처리와 함께 카운트를 올려주는 것.

BFS

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

N = int(input())

result = []
graph = []
dir = [ (-1,0), (1,0), (0,1), (0,-1)]

#그래프 입력받기
for _ in range(N):
    graph.append(list(map(int, input().strip())))

def bfs (graph, a, b ): 

  q = deque()
  q.append((a, b))
  graph[a][b] = 0
  count = 1 #들어오면서 첫번째 집 a,b 를 방문했기 때문에 count값을 1로 시작한다.

  while q: 
    x, y = q.popleft()

    for ax, ay in dir :
      nx = ax + x
      ny = ay + y

      if 0 <= nx < N and 0<= ny <N and graph[nx][ny] == 1 :
        q.append((nx, ny))
        graph[nx][ny] = 0
        count += 1 #좌표 옮기고 새로운 좌표에서 카운트

  return count

for i in range(N):
  for j in range(N) :
    if graph[i][j] == 1 :
      result.append(bfs(graph, i, j))

result.sort()

print(len(result))
for home in result:
  print(home)

DFS

#dfs
import sys
input = sys.stdin.readline

N = int(input())
graph = []
result = []

for _ in range(N) :
  graph.append(list(map(int, input().strip())))

dir = [(-1,0), (1,0), (0,-1), (0,1)]

def dfs (a, b):
  graph[a][b] = 0
  count = 1

  for x, y in dir :
    nx = x + a
    ny = y + b

    if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1 :
      count += dfs(nx, ny)

  return count

for i in range(N) :
  for j in range(N) :
    if graph[i][j] == 1 :
      result.append(dfs(i,j))

result.sort()
print(len(result))
for k in result :
  print(k)

1. 문제

https://leetcode.com/problems/network-delay-time/description/

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

하나의 네트워크에 n개의 노드가 있고, 간선 정보 times가 주어진다.

times[i] = (u, v, w)

• u → v 로 가는 데 걸리는 시간은 w
• 시작 노드 k에서 신호를 보냈을 때
• 모든 노드가 신호를 받는 최소 시간을 구하는 문제
• 도달 불가능한 노드가 있다면 -1 반환

2. 풀이

이 문제는 다음 조건을 만족한다:

• 방향 그래프
• 가중치 존재
• 단일 시작점
• 최단 거리 문제

따라서 다익스트라(Dijkstra) 알고리즘을 사용하면 된다.

우리가 구해야 하는 것은 시작점 k에서 각 노드까지의 최단 거리 그 중 가장 큰 값

코드 설계:

1. 그래프 생성
2. 다익스트라 수행
3. 모든 노드 방문 여부 확인
4. 최단 거리 중 최대값 반환

구현 코드:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times, n, k):

        # 1. 그래프 생성
        graph = defaultdict(list)
        for time in times:
            graph[time[0]].append((time[2], time[1]))
        
        # 2. 다익스트라 알고리즘
        costs = {}
        pq = []
        heapq.heappush(pq, (0, k))

        while pq: 
            cur_cost, cur_node = heapq.heappop(pq)

            # 이미 방문한 노드는 건너뜀
            if cur_node not in costs:
                costs[cur_node] = cur_cost

                for next_cost, next_node in graph[cur_node]:
                    next_cost = cur_cost + next_cost
                    heapq.heappush(pq, (next_cost, next_node))

        # 3. 방문 못한 노드 확인
        if len(costs) != n:
            return -1

        # 4. 최소값 중 최대값 리턴
        return max(costs.values())

1. 문제

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

m × n 격자(grid)가 있다.

로봇은 왼쪽 위 (0,0) 에서 시작해서

오른쪽 아래 (m-1, n-1) 까지 이동해야 한다.

단,

• 오른쪽 →
• 아래 ↓

이동 가능하다.

목적지까지 갈 수 있는 서로 다른 경로의 개수를 구하라.

2. 풀이

이 문제를 처음 보면 자연스럽게 이렇게 생각하게 된다.

현재 위치에서

• 위에서 왔거나
• 왼쪽에서 왔거나

즉 어떤 칸 (r, c)에 도착하는 경우의 수는(r-1, c)에서 오는 경우 + (r, c-1)에서 오는 경우

이걸 그대로 재귀로 표현하면 DFS가 된다.

dfs(r, c)

= dfs(r-1, c) + dfs(r, c-1)

시작점은 경로가 1. 

dfs(0,0) = 1

순수dfs로 풀면 시간초과가 나기때문에 메모이제이션으로 풀어야한다.

먼저, 이중리스트로 구현해보았다.

memo 배열 설계

memo = [[-1] * n for _ in range(m)]

memo[r][c] =
    -1 → 아직 계산 안됨
    값 → 해당 위치까지 오는 경로 수

# 이중리스트 구현

class Solution:
    def uniquePaths(self, m, n):

        # 메모 테이블 생성
        memo = [[-1] * n for _ in range(m)]

        def dfs(r, c):

            unique_paths = 0

            # base case (출발점)
            if r == 0 and c == 0:
                memo[r][c] = 1

            # 아직 계산 안된 경우만 계산
            if memo[r][c] == -1:

                # 위에서 내려오는 경우
                if r - 1 >= 0:
                    unique_paths += dfs(r - 1, c)

                # 왼쪽에서 오는 경우
                if c - 1 >= 0:
                    unique_paths += dfs(r, c - 1)

                memo[r][c] = unique_paths

            return memo[r][c]

        return dfs(m - 1, n - 1)

# 해시맵(딕셔너리) 구현

class Solution:
    def uniquePaths(self, m, n):

        memo = {}

        def dfs(r, c):

            # base case
            if r == 0 and c == 0:
                return 1

            # 이미 계산됨
            if (r, c) in memo:
                return memo[(r, c)]

            paths = 0

            if r > 0:
                paths += dfs(r - 1, c)

            if c > 0:
                paths += dfs(r, c - 1)

            memo[(r, c)] = paths
            return paths

        return dfs(m - 1, n - 1)

Bottom - up 방식으로도 구현해볼 수 있다.

아래, 오른쪽으로밖에 이동 못하기 때문에 가생이? 것들의 paths는 1일것으로 이것을 베이스케이스로 사용.

#이중리스트

class Solution:
    def uniquePaths(self, m, n):

        # DP 테이블 생성
        dp = [[0] * n for _ in range(m)]

        # 첫 행 = 1 (오른쪽만 이동 가능)
        for c in range(n):
            dp[0][c] = 1

        # 첫 열 = 1 (아래만 이동 가능)
        for r in range(m):
            dp[r][0] = 1

        # 점화식 채우기
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]

        return dp[m-1][n-1]

#해시맵(딕셔너리)

class Solution:
    def uniquePaths(self, m, n):

        dp = {}

        # 첫 행
        for c in range(n):
            dp[(0, c)] = 1

        # 첫 열
        for r in range(m):
            dp[(r, 0)] = 1

        # 점화식
        for r in range(1, m):
            for c in range(1, n):
                dp[(r, c)] = dp[(r-1, c)] + dp[(r, c-1)]

        return dp[(m-1, n-1)]

1. 문제

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]

Output: 15

Explanation: You will start at index 1.

- Pay 15 and climb two steps to reach the top.

The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Explanation: You will start at index 0.

- Pay 1 and climb two steps to reach index 2.

- Pay 1 and climb two steps to reach index 4.

- Pay 1 and climb two steps to reach index 6.

- Pay 1 and climb one step to reach index 7.

- Pay 1 and climb two steps to reach index 9.

- Pay 1 and climb one step to reach the top.

The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

2. 풀이

1) DFS(순수 재귀)

dfs(i) = i번째 위치(0..n)에 도달하는 최소 비용

top은 n이므로 최종 답은 dfs(n).

점화식:

• i에 도달하려면
  • i-1에서 한 칸 올라오거나(그때 cost[i-1] 지불)
  • i-2에서 두 칸 올라온다(그때 cost[i-2] 지불)

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)

        def dfs(i):
            if i <= 1:     # 시작점(0 또는 1) → 비용 0
                return 0

            return min(
                dfs(i - 1) + cost[i - 1],
                dfs(i - 2) + cost[i - 2]
            )

        return dfs(n)

• 시간복잡도: O(2^n) (중복 호출 많음)
• 공간복잡도: O(n) (재귀 스택)

2) DP Top-down (Memoization)으로 개선하기

핵심

순수 재귀는 dfs(i)를 여러 번 다시 계산한다.

그래서 dfs(i) 값을 한 번만 계산해서 memo에 저장하고 재사용한다.

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        memo = {}

        def dfs(i):
            # 1) base case는 항상 최상단
            if i <= 1:
                return 0

            # 2) 이미 계산된 값이면 바로 반환
            if i in memo:
                return memo[i]

            # 3) 계산 후 memo에 저장
            memo[i] = min(
                dfs(i - 1) + cost[i - 1],
                dfs(i - 2) + cost[i - 2]
            )
            return memo[i]

        return dfs(n)

 중복 계산이 사라져서 빠르다.

• 시간복잡도: O(n) (각 i를 한 번씩만 계산)
• 공간복잡도: O(n) (memo + 재귀 스택)

3) DP Bottom-up (반복문)으로 바꾸기

핵심

Top-down은 “위에서 아래로(재귀)”

Bottom-up은 “아래에서 위로(반복문)”로 dp 테이블을 채운다.

여기서 가장 많이 헷갈렸던 포인트:

cost 길이가 n이면 top은 n이므로 dp[n]을 구해야 한다.

그래서 dp 배열은 n개가 아니라 n+1개가 필요하다.

dp[i] = i번째 위치(0..n)에 도달하는 최소 비용

초기값:

• dp[0] = 0, dp[1] = 0

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        dp = [0] * (n + 1)   # 0..n까지 필요 (top이 n)

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

        for i in range(2, n + 1):
            dp[i] = min(
                dp[i - 1] + cost[i - 1],
                dp[i - 2] + cost[i - 2]
            )

        return dp[n]

• 시간복잡도: O(n)
• 공간복잡도: O(n)