Krafton_jungle 5기 24일차 TIL - 알고리즘

11723 집합

import sys
input = sys.stdin.readline


def add(S, x):
    x = int(x)
    S |= (1 << x) # 1을 X만클 shift 연산 한 뒤 or연산 실행
    return S


def remove(S, x):
    x = int(x)
    S &= ~(1 << x) # 1을 X만클 shift 연산 한 뒤 NAND연산 실행
    return S


def check(S, x):
    x = int(x)
    if S & (1 << x): #
        return True
    return False


def toggle(S, x):
    x = int(x)
    S ^= 1 << x
    return S


def all():
    S = (1 << 21) - 1
    return S


def empty():
    return 0



n = int(input())
S = 0

for i in range(n):
    commend = list(input().split())
    if commend[0] == "add":
        S = add(S, commend[1])

    elif commend[0] == "remove":
        S = remove(S, commend[1])

    elif commend[0] == "check":
        if check(S, commend[1]):
            print(1)
            continue
        print(0)

    elif commend[0] == "toggle":
        S = toggle(S, commend[1])

    elif commend[0] == "all":
        S = all()

    elif commend[0] == "empty":
        S = empty()

외판원 순회에서 비트 마스킹 기법을 사용해야 한다고 해서 익숙해질 겸 풀어본 문제.

확실히 이렇게 집합을 활용하면 정말 편하게 방문 처리를 할 수 있다는 사실을 알게되었다.

 

 

2098 외판원 순회

import sys
import math
input = sys.stdin.readline

n = int(input())

inf = math.inf

container = []

for i in range(n):
    row = list(map(int, input().split()))
    container.append(row)

dp = [[-1] * (1 << n) for _ in range(n)]


def dfs(start, visited):
    # 탈출조건
    if visited == (1 << n)-1:
        if container[start][0]:
            return container[start][0]
        else:
            return inf

    if dp[start][visited] != -1:
        return dp[start][visited]

    min_val = inf
    # DP 조건
    for next in range(1, n):
        # 이미 방문 했거나 연결되어있지 않으면
        if container[start][next] == 0 or visited & (1 << next):
            continue
        cost = dfs(next, visited | (1 << next)) + container[start][next]
        min_val = min(min_val, cost)

    dp[start][visited] = min_val
    return min_val


print(dfs(0, 1))

기존에 풀었던 외판원 순회 2와 DP, 비트마스킹을 추가해서 풀이했다.

 

 

1931 회의실 배정

#실패코드!
import sys
import heapq
input = sys.stdin.readline

n = int(input())
max_distance = 0
room = []

for i in range(n):
    start, end = map(int, input().split())
    distance = end - start
    max_distance = max(max_distance, end)
    heapq.heappush(room, (distance, start, end))

visited = [0] * (max_distance + 1)

res = 0
while room:
    distance, start, end = heapq.heappop(room)
    if start == end:
        if visited[start] == 1:
            continue
        else:
            visited[start] = 1
            res += 1
            continue
    for i in range(start, end):
        if visited[i] == 1:
            break
    else:
        for i in range(start, end):
            visited[i] = 1
        res += 1

print(res)

 

내 생각엔 거리를 기준으로 우선순위 큐에 담아 나열하는 방식으로 접근했다.

하지만 이 코드의 치명적인 오류가 있는데 시작점과 끝점이 같은 경우엔 무조건 count가 오른다는 부분.

애초에 접근 방식이 잘못됐다고 생각하고 코드를 한번 다 밀었다.

 

#성공코드

import sys
input = sys.stdin.readline

n = int(input())
room = [list(map(int, input().split())) for _ in range(n)]
room.sort(key=lambda x : (x[1], x[0]))
current = 0
cnt = 0
for i, j in room:
    if i < current:
        continue
    current = j
    cnt += 1
print(cnt)

생각해보니 끝점을 기준으로 정렬하고, 해당 시작점이 방금 전 끝점보다 작지 않으면 카운트를 해주는 방식으로 해결한다는 결론에 도달했다.

 

 

1946 신입사원

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    member = list()
    res = 0
    for _ in range(n):
        member.append(list(map(int, input().split())))
    member.sort(key=lambda x: x[0])
    x = member[0][1]
    for i in member:
        if i[1] > x:
            continue
        else:
            x = i[1]
            res += 1
    print(res)

이 문제도 사실상 회의실 배정 2인 셈이다.

 

 

 

DP는 풀이하는데 점화식을 찾는 재미라도 있었다면, 그리디는 정말 풀면풀수록 스트레스만 받는 유형인것 같다.