백준 1325 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • DFS, BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산
    • 가장 노드의 개수가 크게 되는 시작 정점을 출력
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    from collections import deque

    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]

    for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)

    def bfs(v):
    q = deque([v])
    visited = [False] * (n + 1)
    visited[v] = True
    count = 1
    while q:
    v = q.popleft()
    for e in adj[v]:
    if not visited[e]:
    q.append(e)
    visited[e] = True
    count += 1
    return count

    result = []
    max_value = -1

    for i in range(1, n + 1):
    c = bfs(i)
    if c > max_value:
    result = [i]
    max_value = c
    elif c == max_value:
    result.append(i)
    max_value = c

    for e in result:
    print(e, end = " ")

Comment and share


백준 1012 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • DFS

  • 설명

    • 연결 요소의 개수를 세는 문제
    • 모든 정점에 대하여 BFS를 수행하고, 한 번 방문한 정점은 다시 확인하지 않음
    • BFS를 수행한 총 횟수를 계산
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    import sys
    sys.setrecursionlimit(100000)

    def dfs(x, y):
    visited[x][y] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dx, dy in directions:
    nx, ny = x + dx, y + dy
    if nx < 0 or nx >= n or ny < 0 or ny > m:
    continue
    if array[nx][ny] and not visited[nx][ny]:
    dfs(nx, ny)

    for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
    y, x = map(int, input().split())
    array[x][y] = 1
    result = 0
    for i in range(n):
    for j in range(m):
    if array[i][j] and not visited[i][j]:
    dfs(i, j)
    result += 1
    print(result)

Comment and share


백준 2606 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • DFS

  • 설명

    • 시작 정점에서부터 도달할 수 있는 노드의 수를 계산
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    n = int(input())
    m = int(input())
    adj = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    count = 0

    for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(X)

    def dfs(now_pos):
    global count
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
    if not visited[next_pos]:
    dfs(next_pos)

    dfs(1)
    print(count - 1)

Comment and share


백준 1697 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • 특정 위치까지 이동하는 최단 시간을 계산
    • 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    from collections import deque

    MAX = 100001
    n, k = map(int, input().split())
    array = [0] * MAX

    def bfs():
    q = deque([n])
    while q:
    now_pos = q.popleft()
    if now_pos == k:
    return array[now_post]
    for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
    if 0 <= next_pos < MAX and not array[next_pos]:
    array[next_pos] = array[now_pos] + 1
    q.append(next_pos)

    print(bfs())

Comment and share


백준 1260 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS DFS

  • 설명

    • 정점 번호가 작은것부터 방문
    • 모든 노드와 모든 간선을 차례대로 조회하여 O(N + M)의 시간 복잡도
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    from collections import deque

    def dfs(v):
    print(v, end = ' ')
    visited[v] = True
    for e in adj[v]:
    if not(visted[e])
    dfs(e)

    def bfs(v):
    q = deque([v])
    while q:
    v = q.popleft()
    if not(visited[v]):
    visited[v] = True
    print(v, end = ' ')
    for e in adj[v]:
    if not visited[v]:
    q.append(e)

    n, m, v = map(int, input().split())
    adj = [[] for _ in range(n + 1)]

    for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

    for e in adj:
    e.sort()

    visited = [False] * (n + 1)
    dfs(v)
    print()
    visited = [False] * (n + 1)
    bfs(v)

Comment and share

백준 9251 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍
  • 설명

    • 곡의 개수가 N, 볼륨의 최댓값은 M이므로 동적프로그래밍을 이용하여 시간 복잡도 O(NM)

    • 핵심 아이디어: 모든 볼륨에 대하여 연주 가능 여부 계산

    • D[i][j+1] => i번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부

    • 노래를 순서대로 확인, 매 번 모든 크기의 볼륨을 검사

    • D[i][j - V[i]] = True if D[i-1][j] = True

    • D[i][j + V[i]] = True if D[i-1][j] = True

      스크린샷 2020-11-06 오후 9 02 20

  • 풀이

        n, s, m = map(int, input().split())
        array = list(map(int, input().split()))
    
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][s] = 1
    
        for i in range(1, n + 1):
            for j in range(m + 1):
                if dp[i - 1][j] == 0:
                    continue
                if j - array[i - 1] >= 0:
                    dp[i][j - array[i - 1]] = 1
                if j + array[i - 1] <= m:
                    dp[i][j + array[i - 1]] = 1
    
        result = -1
        for i in range(m, -1, -1):
            if dp[n][i] == 1:
                result = i
                break
    
        print(result)

Comment and share

백준 2655 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍
  • 설명

    • 벽돌의 수가 N개일 때, 시간복잡도 O(N^2)

    • 벽돌의 번호를 출력해야함 -> 계산된 테이블 역추적 가능해야함

    • 먼저 벽돌을 무게 기준으로 정렬

    • D[i] = 인덱스 i인 벽돌을 가장 아래에 두었을 때의 높이

    • 모든 0 <= j < i에 대해, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]

      스크린샷 2020-11-06 오후 9 33 07

    • 이후에 Max Value에서 테이블 역추적

  • 풀이

        n = int(input())
        array = []
    
        array.append((0, 0, 0, 0))
        for i in range(1, n + 1):
            area, height, weight = map(int, input().split())
            array.append((i, area, height, weight))
    
        array.sort(key=lambda data: data[3])
    
        dp = [0] * (n + 1)
    
        for i in range(1, n + 1):
            for j in range(0, i):
                if array[i][1] > array[j][1]:
                    dp[i] = max(dp[i], dp[j] + array[i][2])
    
        max_value = max(dp)
        index = n
        result = []
    
        while index != 0:
            if max_value == dp[index]:
                result.append(array[index][0])
                max_value -= array[index][2]
            index -= 1
    
        result.reverse()
        print(len(result))
        [print(i) for i in result]

Comment and share

백준 9251 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍
  • 설명

    • 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
    • 수열 각각을 X, Y라고 함
    • D[i][j] = X[0..i]와 Y[0..j]의 공통 부분 수열의 최대 길이
    • 두 문자열의 길이를 조금씩 늘려가며 확인, 공통 부분 수열의 최대 길이를 계산
    • 점화식
      스크린샷 2020-11-06 오후 6 30 38
  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    x = input()
    y = input()

    dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

    for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):
    if x[i - 1] == y[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
    else:
    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

Comment and share

백준 11053 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 수열의 크기가 N일 때, 기본적으로 동적 프로그래밍 알고리즘으로 O(N^2)으로 해결

    • D[i]는 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

    • 모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

    • N = 6 일 때

      스크린샷 2020-11-05 오후 9 30 40

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    n = int(input())
    array = list(map, input().split())
    dp = [1] * n

    for i in range(1, n):
    for j in range(0, i):
    if array[j] < array[i]:
    dp[i] = max(dp[i], dp[j] + 1)

    print(max(dp))

Comment and share

백준 12865 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 물품의 수 N, 배낭에 담을 수 있는 무게 K

    • 동적 프로그래밍을 이용하여 시간 복잡도(NK)

    • 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기

    • D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치

    • 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결

    • 점화식
      스크린샷 2020-11-05 오후 9 09 54

    • N = 4, K = 7 일 때
      스크린샷 2020-11-05 오후 9 11 23

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    n, k = map(int, input().split())
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
    weight, value = map(int, input().split())
    for j in range(1, k + 1):
    if j < weight:
    dp[i][j] = dp[i - 1][j]
    else:
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

    print(dp[n][k])

Comment and share

Yechan Kim

author.bio


author.job