class 4

[백준 1043] 거짓말 - 그래프, 집합, 유니온 파인드(union find), bfs

설명

• 집합, 그래프(bfs), 유니온 파인드 여러 방식으로 풀 수 있는 문제
• 여기선 집합을 이용해 풀었다

코드

def solution(n, m, true):
    # true는 진실을 알고있는 초기 사람들의 집합(set)

    # 파티들을 저장할 배열
    partys = []

    # 파티들을 partys에 저장
    for _ in range(m):
        party = list(map(int, input().split()))[1:]
        partys.append(party)

    # partys의 각 party와 true에 공통된 사람이 있으면 합친다
    # party[0] ~ party[n-1] 까지 n번 반복하면서 각 파티에서 진실을 아는 사람을 전부 합침
    for _ in range(n):
        for party in partys:
            s_party = set(party)
            if true & s_party:
                true = true | s_party

    cnt = 0
    # 각 파티에 속한 사람 모두가 true 안에 없으면 cnt 값을 1 증가
    for party in partys:
        flag = True
        for p in party:
            if p in true:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)


n, m = map(int, input().split())
true = list(map(int, input().split()))
if len(true) != 0:
    true = true[1:]

solution(n, m, set(true))

---

[백준 16953] A → B - 그래프, 그리디, BFS

설명

• A를 B로 바꾸는데 연산은 무조건 2를 곱하거나 1을 오른쪽에 추가하는 연산 뿐이다.
• B를 A로 바꾼다고 하면, B에서 맨 오른쪽의 1을 제거하거나 2로 나누면 된다.
• 2로 나누는 연산보다는 1을 제거하는게 우선이다(그리디 방식)
• 만약 B의 마지막 숫자가 1이 아니거나, B가 짝수가 아니면 -1을 출력한다
• B가 A보다 작아지면 만들 수 없으므로, -1을 출력한다

코드

a, b = map(int, input().split())

answer = 0
while b >= 1:
    answer += 1
    if b == a:
        break
    if b % 10 == 1:
        b = b // 10
    elif b % 2 == 0:
        b = b // 2
    else:
        break

if a == b:
    print(answer)
else:
    print(-1)

---

[백준 11053] 가장 긴 증가하는 부분 수열 - DP, LIS(Longest Increasing Subsequence)

설명

• 처음에 그리디로 O(n) 만에 끝내려다가 실패한 문제... ([1, 4, 2, 3 5] 에 대한 결과 도출 불가능)
• LIS 알고리즘으로 풀 수 있는 DP 형태의 문제라고 한다
• O(n^2)과 O(n log n) 방식이 있다고 하는데, 이 문제에서는 O(n^2) 방식으로 풀었다(배열 길이가 1,000이라서)

풀이

• 배열(ex [10, 20, 10, 30, 20, 50])을 입력 받고, 같은 길이의 dp 배열을 1로 초기화하여 선언한다(ex [1, 1, 1, 1, 1, 1,])
• 1로 초기값을 설정하는 이유는, 현재 각 위치에서 최소 자기 자신이 부분 수열로 들어가기 때문
• 이중 for문을 돌면서 dp 배열을 갱신한다
  • 갱신할 위치인 j를 i (0 ~ j-1) 과 비교한다
  • 만약 arr[j]가 arr[i]보다 크면, 부분수열이 될 수 있으므로 현재 dp[j] 값과 dp[i]+1 값중 더 큰 값으로 갱신한다
  • +1을 한 값과 비교하는 이유는 arr[j] 까지의 부분 수열 개수에서 +1을 한 길이가 비교되어야 하기 때문
  • 만약 현재 dp[j]의 값이 dp[i]+1보다 크면 갱신하지 않고 진행한다

코드

input()
arr = list(map(int, input().split()))
dp = [1 for _ in range(len(arr))]


for j in range(len(arr)):
    for i in range(j):
        if arr[j] > arr[i]:
            dp[j] = max(dp[j], dp[i]+1)
print(max(dp))

---

[백준 1916] 최소비용 구하기 - 그래프, 다익스트라

코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(n, arr, start):
    distances = [1e9 for _ in range(n)]
    hq = [(0, start)]
    distances[start] = 0
    while hq:
        distance, now = hq[0][0], hq[0][1]
        heapq.heappop(hq)
        if distance > distances[now]:
            continue
        if now in arr:
            for node, dis in arr[now]:
                cost = dis + distances[now]
                if distances[node] > cost:
                    distances[node] = cost
                    heapq.heappush(hq, (cost, node))
    return distances
        
n = int(input())
m = int(input())
arr = dict()

for _ in range(m):
    start, end, cost = map(int, input().split())
    if start-1 in arr:
        arr[start-1].append((end-1, cost))
    else:
        arr[start-1]=list()
        arr[start-1].append((end-1, cost))
start, end = map(int, input().split())
print(dijkstra(n, arr, start-1)[end-1])

---