[TIL][Krafton Jungle] 3주차 - (7) : DP + 그리디 문제풀이 마무리

3주차 마지막 날이 다가왔다.

 

남은 문제를 오늘 전부 풀겠다.

(도전빼고.)

---

BaekJun - #11053 : 가장 긴 증가하는 부분 수열 (DP)

출처 : https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

이 문제를 처음 접했을 때, DP적 접근이 아니라 문제를 해결하는 방식을 생각하다가

뒤에서부터 result에 append하고

만약에 다음에 append할 수의 값이 이전 append한 값보다 작으면 그냥 정상적으로 append하고

반대로 큰 값이면 작은 값을 pop하고 append하도록 코드를 짰다.

 

잘못 짠 그 코드가 아래와 같았다.

import sys


n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().strip().split()))

result = []
answer_num = 0
while arr:
    last_num = arr.pop()
    while True:
        if not result:
            result.append(last_num)
            break
        else:
            before_append = result[-1]
            if before_append > last_num:
                result.append(last_num)
                break
            else:
                result.pop()
    answer_num = max(answer_num,len(result))

print(answer_num)

근데 이코드는 문제의 수열의 중간 툭 튀어나온 큰 수를 뛰어 넘는 상황을 고려하지 못했다.

 

예를 들면 (10 ,20 ,70, 30 ,40) 의 수열이라면,

70을 무시하지 않고 70을 넣기 위해 30과 40을 전부 pop하고 있다.

 

그래서 다시 생각을 해보니 LCS와 비슷한 상황이고 문제해결을 비슷하게 할 수 있을 것 같다고 생각이 들었다.

 

LCS에서는 이전 LCS가 만들어진 상황에서 +1 하는 방식으로 크기를 넓혀 갔다면,

이 문제에선 왼쪽의 수부터 하나씩,

자기보다 왼쪽에 배치된 값들 중 현재 수보다 작은 수의 최장 길이 수열 값의 최고 값+1 로 저장해 주면 된다.

 

말이 어려운데 예를 들면,

 

10 20 50 30 40

이 수열이 있다면 10부터 체크하면서 자기보다 왼쪽의 작은 수 중 가장 긴 수열을 체크하고 +1한다.

 

 

10 20 50 30 40

 1

 

10은 왼쪽 수가 없으므로 그냥 1을 기입

 

 

10 20 50 30 40

 1   2

 

20은 왼쪽 자기보다 작은 10의 수가 최장 길이가 1이므로 본인까지의 최장 수열의 길이는 1+1 = 2가 된다.

 

 

10 20 50 30 40

 1   2    3

 

그리고 50도 왼쪽 수 중 자기보다 작은 수인 20이 최장 길이 2를 가지고 있으므로 2+1 = 3

 

 

10 20 50 30 40

 1   2    3   3

 

그리고 30에서는 50은 자기보다 크니까 제외한 왼쪽의 수중 20이 최장 길이 2를 가지고 있으므로 2+1 = 3

 

이런 방식이다.

40은 30이 가지고 있는 최장길이 3에서 +1한 4를 가지고 있을 것이고,

 

결국 최대 수열 길이는 4가 될 것이다.

 

 

 

이 로직을 아래 코드로 작성해 보았다.

import sys


n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().strip().split()))

dp = [0 for _ in range(n)]
result = 0
for i in range(n):
    max_dp = 0
    for j in range(i):
        if arr[j] >= arr[i]:
            continue
        else:
            max_dp = max(max_dp,dp[j])
    dp[i] = max_dp+1
    result = max(result,dp[i])

print(result)

 

dp 리스트가 수열의 길이를 저장하는 리스트이고, i와 j로 이중 for문을 돌면서 체크한다.

따라서 O(n^2)의 시간 복잡도를 가진다.

 

---

BaekJun - #2098 : 외판원 순회(DP)

출처 : https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

 

이전에 DFS로 문제를 푼 적이 있는데 그때는 N<=10 인 상황이었다.

 

이번엔 N<=16이라 비트 마스킹 + DP를 꼭 사용해야만 한다는 팀원의 조언을 듣고 공부를 한 뒤 코드를 작성해봤다.

 

그전에,

외판원 순회는 해밀턴 순환 문제 중 하나인데,

해밀턴 순환이란 모든 정점을 한번만 지나가는 경로를 찾는 문제를 말한다.

 

해밀턴 순환은 NP 문제 중 하나라고 한다.

그전에 NP 문제가 무엇인지에 관한 자세한 설명이 있어서 적어 놓겠다.

 

📌 P-NP 문제가 무엇인지 잠깐! 알아보자!

 

‘P’는 컴퓨터가 쉽게 해결할 수 있는 문제를 말한다.
‘NP’는 직소 퍼즐이나 스도쿠처럼 한번 해결하면 검산하기 쉬운 문제를 뜻한다. 많은 NP 문제들은 사회가 직면한 가장 고질적이고 긴급한 문제에 해당한다.

P 대 NP로 제기되는 100만달러짜리 질문이란 다음과 같다. P 집합과 NP 집합은 동일한 하나의 집합일까? 다시 말해, 어려워 보이는 문제들을 일정 시간 안에 알고리즘을 통해 해결할 수 있을까? 만약 엄청나게 빠르고 탁월한 알고리즘만 있다면 말이다. 실제로 그렇다면 수많은 어려운 문제들이 갑자기 해결된다. 그리고 이 알고리즘 해법들은 의학과 공학, 경제학, 생물학, 생태학, 신경과학, 사회과학, 산업, 예술, 심지어 정치 및 그 밖의 분야에 유토피아적인 사회 혁신을 가져올 수 있다.

때로 이 분류에 변화가 생기기도 한다. 전에는 어려웠던 문제가 연구자들이 더 효율적인 해법을 발견함으로써 쉬운 문제가 되는 것이다. 예를 들어, 어떤 숫자가 소수(prime)인지 여부를 시험하는 것은 1970년대 중반부터 NP 집합에 속하는 것으로 알려져 왔다. 그러나 2002년 인도 공과대학교 칸푸르(Indian Institute of Technology Kanpur)의 세 컴퓨터 과학자가 증명과 알고리즘을 고안함으로써, 이 문제가 P 집합임이 마침내 확인되었다.

만일 모든 까다로운 문제가 이러한 알고리즘적 기법을 통해 P 문제로 전환될 수 있다면, 그 결과는 인류와 지구에 엄청난 영향을 끼칠 것이다.

우선 NP 문제에 기반한 대부분의 암호화 시스템이 무력화될 것이다. 기밀 통신에는 완전히 다른 접근법이 필요해지게 된다. 지난 50년 간 생물학계의 가장 큰 도전이었던 단백질 접힘 문제도 풀기 수월해져, 질병 치료 목적으로 약을 설계하거나 산업 폐기물 분해용 효소를 개발할 수 있게 될 것이다. 또한 여러 목적지를 들르기 위한 최단 거리를 계획하거나, 지인끼리 동석하게 결혼식 하객석을 배치하는 것과 같은 일상적인 문제에도 최적의 해결책을 찾을 수 있게 된다.

 

 

아무튼 이 문제를 한번 풀어봤다.

잘못 접근하여 죽쑨 예

 

처음 문제를 접근했을 때,

DP라는 것은 알고 있었으니까 반복되는 탐색의 경우를 생각하고 지워나가는 접근을 수행했다.

그 수행을 나는 Bottom - up 방식으로 작성했다.

 

이 코드가 그 코드이다.

import sys

n = int(sys.stdin.readline())
graph = [[0 for _ in range(n+1)]]
for _ in range(n):
    graph.append([0]+list(map(int,sys.stdin.readline().split())))
dp = {}
result = n * 1000000

def dfs(this,visit,cost):
    global result
    global n 
    visit = visit | (1<<(this-1))
    if (this,visit) in dp:
        if dp[(this,visit)] < cost:
            return
        
    dp[(this,visit)] = cost

    if visit == (1<<n)-1:
        if graph[this][1] != 0:
            result = min(result,cost + graph[this][1])
        return
    
    for i in range(1,n+1):
        if not visit & (1<<(i-1)) and graph[this][i] != 0:
            dfs(i,visit,cost + graph[this][i])

dfs(1,0,0)
print(result)

 

dp 딕셔너리를 생성한 뒤에,

현재 방문하고 있는 지역과 방문해온 정점을 비트 마스킹으로 저장한 값을 튜플로 묶은 것을 key로 매칭하고

그 value에다가 현재까지의 가중치 값을 저장하도록했다.

 

그니까 방문을 순회하면서 도중 값을 계속 딕셔너리에 `(현재 노드,방문해온 정보) = 지금까지 방문한 가중치` 로 저장하고 있는 것이다.

 

그리고 중복된 상황에서 만약 지금까지 저장한 가중치가 이전 기록에서의 가중치보다 클 경우 해당 경로를 가지 않도록 했다.

 

 

그런식으로 DP방식의 최적화를 수행하려고 노력했지만, 앞에서 봤듯이 계속 시간초과가 발생해서 다른 포스팅을 참고해봤다.

 

근데 모든 사람들이 top-down 방식을 사용하고 있었고, 왜 내가 한 bottom -up 방식보다 시간이 빨라서 문제가 풀리는 지 그 차이가 무엇인지 디버깅 해 보았다.

 

 

그 차이는 꽤 컸다.

 

내가 수행하고 있는 방식은

이후의 어디로 갈 것인지에 대한 것은 열어놓은채로 현재가 최선이 아니라면 그 길로 가지 않도록 했지만,

만약 최선이라면 그 길로 쭉 가서 값을 쭉 갱신한다.

 

하지만 top-down 방식은 뒤에서부터 최적의 값을 저장하면서 내려오기 때문에,

다음번에 또 올라갈때, 같은 동선이라면 최적이던 아니던 끝의 동선까지 갈 필요가 없다.

 

그러니까 모든 동선의 경우의 수가 가지를 뻗는 느낌으로 나눠지는데,

가지의 갈래길에 해당 가지의 최적의 값을 저장해놓으니까

다른 가지에서의 똑같은 상황에서 해당 가지의 끝까지 갈 필요가 없이 최적을 사용하면 된다는 말이다.

 

하지만 바텀 up 상황은 가지의 루트의 자식부터 시작해서 최적을 갱신하기 때문에

최적의 값을 갱신해야 하는 상황이 발생하면

그 깊이를 전부 끝까지 수행해야만 해당 경로의 결과값을 가져올 수 있다.

 

from collections import defaultdict
import sys

n = int(sys.stdin.readline())
graph = [[0 for _ in range(n+1)]]
for _ in range(n):
    graph.append([0]+list(map(int,sys.stdin.readline().split())))
dp = defaultdict(lambda: float('inf'))

def dfs(this,visit):
    global n
    if visit == (1<<n) - 1:
        if graph[this][1] == 0:
            return float('inf')
        else:
            return graph[this][1]
    
    if (this,visit) in dp:
        return dp[(this,visit)]
    
    for i in range(1,n+1):
        if not visit & 1<<(i-1) and not graph[this][i] == 0:
            weight = dfs(i,visit|1<<(i-1))+graph[this][i]
            dp[(this,visit)] = min(dp[(this,visit)],weight)
    return dp[(this,visit)]


print(dfs(1,1))

 

이 코드는 상당히 복잡하므로 따로 종이에 인자들을 기억하는 방식으로 디버깅하면서, 어떻게 구동되는지 파악하는 게 좋다.

 

dfs 안의 두번째 if문을 통해 만약 지금까지 동선이 모두 곂쳤다면, 더 깊이 들어갈 필요없이 해당 최적의 값을 사용했다.

 

내용 출처 : https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C

[알고리즘] 외판원 순회 문제

 

---

 

BaekJun - #1700 : 멀티탭 스케줄링 (그리디)

출처 : https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

이번 문제는 멀티탭에 기기를 꼽기위해 뽑는 횟수의 최소값을 출력하는 문제이다.

 

그리디는 정말 느끼는게, DP와 달리 최적화를 한다기보단 기발한 방식으로 효율적으로 문제를 찾는 방법을 구현하는 유형 같다.

 

창의적 아이디어를 도입한 구현문제 같은느낌.?

 

아무튼 효율성을 고려하려고 애쓰다가 정신팔려서 문제를 오래 고민했다.

 

근데 멀티탭의 구멍의 최대한도와 기기들의 최대 수가 많지 않아서

효율을 많이 고려하지 않고 상식적으로 문제 해결방법을 찾으려 노력했다.

 

멀티탭이 꽉 찼을 때, 보통은 제일 오래 사용하지 않을 기기를 뽑는다.

 

그 알고리즘을 이 문제에 적용하는 것이다.

 

꼽혀있는 기기들을 리스트에 넣어두고

앞으로 사용할 기기들을 하나씩 순회하면서, 만약 꼽혀 있지 않은 기기를 사용하기 위해 꼽을때,

가장 늦게 사용되는 기기를 뽑기 위해 이후의 예정된 기기들을 탐색한다.

 

그 후 가장 미래에 (혹은 더이상 사용하지 않을 수도 있다) 사용할 기기를

꼽혀 있는 기기의 인덱스와 매칭시켜서 가장 오래 사용하지 않을 기기를 지금 사용할 기기와 바꿔준다.

 

그리고 플러그를 뽑은 횟수를 +1 하는 것으로 문제풀이를 마무리했다.

 

해당 문제를 풀이한 코드이다.

import sys

n,k = map(int,sys.stdin.readline().split())

items = list(map(int,sys.stdin.readline().split()))
i = 0
pluged_items = []
for item in items:
    i += 1
    if not item in pluged_items:
        pluged_items.append(item)
        if len(pluged_items) == n:
            break


other_task = items[i:]
count = 0

for m in range(len(other_task)):
    if other_task[m] in pluged_items:
        continue
    else:
        pluged_important_cost = [k for _ in range(n)]
        for i in range(len(pluged_items)):
            for item_index in range(m,len(other_task)):
                if other_task[item_index] == pluged_items[i]:
                    pluged_important_cost[i] = item_index
                    break

        pluged_items[pluged_important_cost.index(max(pluged_important_cost))] = other_task[m]
        count += 1

print(count)

 

해당 문제는 알고리즘 풀이를 잘하는 팀원의 도움을 많이 받아서,

다음번에 또 보면서 해당 문제를 어떻게 접근했었는지 기억해야 할 것 같다.

 

---

 

 

 

백준 문제를 풀며 알게된 Python 문법

---

KeyError를 방지하기 위한 초기값 자동 선언 방법

딕셔너리를 사용하다보면 Key가 없는 것을 참조하면서 Error가 발생할 때가 많다.

 

 

이때, from collections import defaultdict 를 통해서

딕셔너리 선언 시,

my_dict = defaultdict(lambda: 원하는 초기값)

으로 선언하면, 저장되지 않은 key가 참조될 경우 초기값으로 받아낼 수 있다.

 

---

 

유용한 리스트 활용법 총정리

 

1. 인덱싱 

for 문에서 range 슬라이싱을 하는 것과 동일하다.

 

':' 문자로 슬라이싱하며, 문자 왼쪽에 수를 두면 해당 인덱스를 포함하는 리스트값부터 포함되고,

오른쪽에 수를 두면 해당 인덱스 이전값까지 포함된다.

 

list = [1,2,3,4,5]

list[2:] = [3,4,5]

list[:3] = [1,2,3]

 

2. list 값 중 max값 추출하기

 

list = [1,2,3,4,5]

max(list) = 5

 

3. list 값으로 해당 값이 어떤 인덱스에 있는지 확인하기

 

list.index(1) = 0

 

괄호 안에 인덱스를 알고자 하는 값을 넣으면 된다.

 

 

---