Algorithm-효율적인 해킹

Nov 09, 2020 in Algorithm, Graph, BFS

문제유형 :
- 그래프 탐색
- BFS
설명
- DFS, BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산
- 가장 노드의 개수가 크게 되는 시작 정점을 출력

풀이

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

Algorithm-유기농 배추

Nov 09, 2020 in Algorithm, Graph, DFS

백준 1012 : 문제링크

문제유형 :
- 그래프 탐색
- DFS
설명
- 연결 요소의 개수를 세는 문제
- 모든 정점에 대하여 BFS를 수행하고, 한 번 방문한 정점은 다시 확인하지 않음
- BFS를 수행한 총 횟수를 계산

풀이

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

Algorithm-바이러스

Nov 09, 2020 in Algorithm, Graph, DFS

백준 2606 : 문제링크

문제유형 :
- 그래프 탐색
- DFS
설명
- 시작 정점에서부터 도달할 수 있는 노드의 수를 계산

풀이

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

Algorithm-숨박꼭질

Nov 09, 2020 in Algorithm, Graph, BFS

백준 1697 : 문제링크

문제유형 :
- 그래프 탐색
- BFS
설명
- 특정 위치까지 이동하는 최단 시간을 계산
- 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결

풀이

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

Algorithm-DFS와 BFS

Nov 09, 2020 in Algorithm, Graph

백준 1260 : 문제링크

문제유형 :
- 그래프 탐색
- BFS DFS
설명
- 정점 번호가 작은것부터 방문
- 모든 노드와 모든 간선을 차례대로 조회하여 O(N + M)의 시간 복잡도

풀이

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

Algorithm-가장 높은 탑 쌓기

Nov 06, 2020 in Algorithm, Dynamic Programming

백준 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

풀이

    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

Algorithm-기타리스트

Nov 06, 2020 in Algorithm, Dynamic Programming

백준 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]
- 이후에 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

Algorithm-LCS

Nov 06, 2020 in Algorithm, Dynamic Programming

백준 9251 : 문제링크

문제유형 :
- 동적 프로그래밍
설명
- 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
- 수열 각각을 X, Y라고 함
- D[i][j] = X[0..i]와 Y[0..j]의 공통 부분 수열의 최대 길이
- 두 문자열의 길이를 조금씩 늘려가며 확인, 공통 부분 수열의 최대 길이를 계산
- 점화식

풀이

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

Algorithm-가장 긴 증가하는 부분 수열

Nov 05, 2020 in Algorithm, Dynamic Programming

백준 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 일 때

풀이

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

Algorithm-평범한 배낭

Nov 05, 2020 in Algorithm, Dynamic Programming

백준 12865 : 문제링크

문제유형 :
- 탐색
- 동적 프로그래밍
설명
- 물품의 수 N, 배낭에 담을 수 있는 무게 K
- 동적 프로그래밍을 이용하여 시간 복잡도(NK)
- 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기
- D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치
- 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결
- 점화식
- N = 4, K = 7 일 때

풀이

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