𝐓𝐨𝐝𝐚𝐲 𝐈 𝐋𝐞𝐚𝐫𝐧 2022.03.30.수

Today I Learn (20220330)

---

오늘 오전에는 교수님께서 저번에 주신 BFS문제를 풀이하는데 보냈다. 여러개의 소화기 중 하나를 찾고 불을 찾아 최단 거리를 구해 그 소화기 중 또 최단거리를 구하는 문제였는데... 내 코드는 소화기만 찾고 끝나는 코드로 되어버렸다. 그래서 다른 분에게 피드백 받았다.

구현 순서는

1. 불, 소화기 위치를 찾고
2. for 문을 통해 시작점부터 소화기까지, 소화기부터 불까지 bfs 함수를 실행하게 만들었고, 여기서 리턴되는 값을 list에 넣고 그 중 최소값을 반환하게 만들었다.

그런데 다른 테케에서 불을 지나가면 안되는 조건을 무시한체 코드가 돌아갔다.

그래서 bfs함수의 매개변수에 isfindFire이라는 변수를 넣어 소화기를 찾으러 갈때는 불을 못지나가게 만들었고, 소화기에서 불까지는 다시 불을 찾게 만들어 줬다.

그래서 최종적인 코드는 아래와 같다.

#모의 소방훈련을 실시하는 날입니다.
from collections import deque
n = int(input())
arr = [list(input()) for _ in range(n)]
sy,sx=map(int,input().split())

#불 위치, 소화기 위치 찾기
fire=[]
ext=[]
for k in range(n):
    for l in range(n):
        if arr[k][l] == '$':
            fire.append((k,l))
        if arr[k][l] == 'A':
            ext.append((k,l))


def bfs(sy,sx,ey,ex,isfindFire): #마지막 인자는 불을 지나가버리는 것을 막기 위해 넣어줌!
    q = deque()
    q.append((sy,sx,ey,ex,0))
    visit=[[0]*n for _ in range(n)]

    while q:

        sy,sx,ey,ex,move = q.popleft()

        directy=[-1,1,0,0]
        directx=[0,0,-1,1]

        if sy == ey and sx==ex:
            return move

        for i in range(4):
            dy=sy+directy[i]
            dx=sx+directx[i]

            if 0<=dy<n and 0<=dx<n:
                if visit[dy][dx]==0 and arr[dy][dx]!='#':
                    if isfindFire: #불을 찾을 때
                        visit[dy][dx]=1
                        q.append((dy,dx,ey,ex,move+1))
                    else: #소화기 찾을 때
                        if arr[dy][dx]!='$':
                            visit[dy][dx] = 1
                            q.append((dy, dx, ey, ex, move + 1))


result=[]
for i in range(len(ext)):
    a = bfs(sy,sx,ext[i][0],ext[i][1],False) #시작점 부터 소화기까지
    b = bfs(ext[i][0],ext[i][1],fire[0][0],fire[0][1],True) #소화기부터 불까지
    result.append(a+b)

print(min(result))

+)오늘은 knapsack과 heap에 대해 배웠다. 아직도 DP가 익숙하지 않고 구현 자체를 어떻게 해야할지 모르겠다. 학습이 부족하다는 느낌이 매일매일 강렬하게 든다. 이번주 멘토링에서 다시 DP를 복습하게 될 거 같은데 남들보다 더 많이 노력해야겠다.....ㅠㅠ 일단 오늘은 교수님의 코드를 트레이스 하며 다시 혼자 적어보는 연습을 3번 이상은 해봐야겠다.

knapsack

---

• Fractinoal Knapsack
• 0/1 (=>DP문제)

**배낭 문제**(Knapsack Problem 냅색 프라블럼[[*](https://ko.wikipedia.org/wiki/위키백과:영어의_한글_표기)])는 [조합 최적화](https://ko.wikipedia.org/wiki/조합_최적화)의 유명한 문제이다.

간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 [소수])일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 **분할가능 배낭문제**(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 **0-1 배낭문제**(0-1 Knapsack Problem)라 부른다.

이 문제는 쪼갤 수 있는 경우에는 [그리디 알고리즘]으로 [다항 시간], 쪼갤 수 없는 경우에는 [동적계획법](Dynamic Programming)등으로 [의사 다항 시간]에 풀 수 있다. 단, 쪼갤 수 없는 경우는 [NP-완전]이기 때문에 알려진 다항 시간 [알고리즘]은 없고, [FPTAS]만 존재한다.

출처: wikipedia(https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C)

한 달 후면 국가의 부름을 받게 되는 라이언은 여행을 가려고 한다. 
세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 
가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
라이언이 여행에 필요하다고 생각하는 N개의 물건이 있다. 
각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 라이언아 V만큼 즐길 수 있다. 
아직 행군을 해본 적이 없는 라이언은 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.
라이언이 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.


입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 
두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 
해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이며 제한시간은 2초 이다.

출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

4 7
6 13
4 8
3 6
5 12

출력
14

n, k = map(int, input().split())
knapsack = [[0 for _ in range(k + 1)] for _ in range(n + 1)] # 배열

item = [[0, 0]]
for i in range(1,n+1): # 아이템 입력
    item.append(list(map(int, input().split())))

for i in range(1, n + 1): # 아이템 개수만큼 반복
    for j in range(1, k + 1):  # 최대무게까지 반복

        weight = item[i][0]
        value = item[i][1]

        if j < weight:  # 무게가 아이템 무게보다 작으면
            knapsack[i][j] = knapsack[i - 1][j]  # 위의 값 그대로 가져오기
        else:
            knapsack[i][j] = max(value + knapsack[i-1][j - weight], knapsack[i - 1][j])
            # 현재 아이템가치 + 그전 단계에서 구한 남은무게의 최대가치  (현재 아이템 + 윗줄(남은 kg만큼)
            #  vs  그전단계에서 구한 현재 아이템의 최대가치 ( 윗줄 )

print(knapsack[n][k])

Heap

---

heap은 완벽한 이진 트리의 형태이며, nlogn의 속도를 갖고 있다.

이 이진트리를 일차원 리스트로 표현 가능한데 이때, index는 왼쪽 자식은 부모의 인덱스x2, 오른쪽 자식은 부모의 인덱스x2+1의 값을 갖는다.

max heap

Max Heap의 과정

부모는 항상 자식보다 커야한다. 따라서 부모가 작으면 자식과 swap해줘야함.

-삽입

insert과정에서는 젤 위만 큰 수이고, 아래는 정렬되어있지 않다. 단지, 자식이 부모보다 작다는 것일뿐.

-출력

따라서 출력 과정을 통해 이를 정렬하여 heap정렬이 가능해진다.

arr=[4,7,8,1,5,3,6,9]  # Maxheap
heap=[0]*20
hindex=1  # 힙 이라는 1차배열의 인덱스 역활

def insert(value):
    global heap,hindex
    heap[hindex]=value
    now=hindex
    hindex+=1

    while 1:
        parents=now//2 # 부모 인덱스 확인
        if parents==0: break  # 처음에 인덱스가 1이면 그냥 끄기
        if heap[parents]>heap[now]: break # 부모가 더 크면 스왑 안함
        heap[parents],heap[now]=heap[now],heap[parents] # 부모가 지금 들어온 애보다 작으면 스왑
        now=parents  # 부모를 그다음 now로 놓고 위로 올라가면서 그다음 부모랑 비교!!



def top():
    global heap
    return heap[1] # 1번 인덱스의값 (루트노드 리턴)

def pop():
    global heap,hindex
    heap[1]=heap[hindex-1] # 맨 뒤에 있는 아이를 루트로 일단 옮기기
    heap[hindex]=0
    hindex-=1

    now=1
    while 1:
        son=now*2 # 왼쪽자식
        rson=son+1 # 오른쪽 자식

        # 오른쪽에 자식이 있고 그리고 왼쪽 오른쪽 자식비교했는데
        # 오른쪽이 더 크다면 자식을 오른쪽찜 하겠음
        if heap[rson]!=0 and heap[son]<heap[rson]: son=rson
        if heap[now]>=heap[son]: break # 부모가 내가 찜한 자식보다 크면 브레이크
        heap[now],heap[son]=heap[son],heap[now] # 그게 아니면 스왑
        now=son # 트리의 밑으로 내려가면서 while 돌며 그 밑의 자식과 비교

for i in range(len(arr)):
    insert(arr[i])   # 트리의 형태로 저장 (1차배열)

for i in range(len(arr)):
    print(top(),end=' ') # 루트노드 출력
    pop() # 맨뒤에 있는아이를 1번 인덱스로 올리고 자식들이랑 비교

min heap

max heap과 반대로 젤 작은 값이 루트에 오게 된다.

Min heap과정

#Min heap
arr = [4,7,8,1,5,3,6,9]
INF=9889798698643  
heap = [INF]*20 #Min heap이기 때문에 큰 값을 넣어준다!
hindex=1

def insert(value):
    global heap, hindex
    heap[hindex]=value
    now=hindex
    hindex+=1

    while 1:
        parents=now//2 #부모 인덱스 확인
        if parents==0: break
        if heap[parents]<heap[now]:break
        heap[parents],heap[now] = heap[now],heap[parents] #부모가 더 크면 스왑하기
        now = parents

def top():
    global heap
    return heap[1] #루트 노드 리턴

def pop():
    global heap, hindex
    heap[1]=heap[hindex-1]
    heap[hindex]=INF #max heap에서는 0으로 초기화 했지만, min heap은 INF로 !!!!
    hindex-=1

    now=1
    while 1:
        son = now*2 #왼쪽자식
        rson = son+1 #오른쪽 자식

        if heap[rson] !=0 and heap[son]>heap[rson]: #오른쪽 자식이 작다면 오른쪽 찜
            son = rson
        if heap[now]<=heap[son]:break #부모가 내가 찜한 자식보다 작으면 멈추기
        heap[now],heap[son]=heap[son],heap[now]
        now=son



for i in range(len(arr)):
    insert(arr[i])

for i in range(len(arr)):
    print(top(),end=' ') #root node 출력하기
    pop() #heap sort

---

#교수님코드
arr=[4,7,8,1,5,3,6,9]  #Minheap
heap=[0]*50
hindex=1  # 힙 이라는 1차배열의 인덱스 역활

def insert(value):
    global heap,hindex
    heap[hindex]=value
    now=hindex
    hindex+=1

    while 1:
        parents=now//2
        if parents==0: break
        if heap[parents]<=heap[now]: break
        heap[parents],heap[now]=heap[now],heap[parents]
        now=parents 



def top():
    global heap
    return heap[1] # 1번 인덱스의값 (루트노드 리턴)

def pop():
    global heap,hindex
    heap[1]=heap[hindex-1] # 맨 뒤에 있는 아이를 루트로 일단 옮기기
    heap[hindex]=0
    hindex-=1

    now=1
    while 1:
        son=now*2 # 왼쪽자식
        rson=son+1 # 오른쪽 자식

        if rson<=hindex and heap[son]>heap[rson]: son=rson
        if son>hindex or heap[now]<heap[son]: break
        heap[now],heap[son]=heap[son],heap[now]
        now=son

for i in range(len(arr)):
    insert(arr[i])   # 트리의 형태로 저장 (1차배열)

for i in range(len(arr)):
    print(top(),end=' ') # 루트노드 출력
    pop() # 맨뒤에 있는아이를 1번 인덱스로 올리고 자식들이랑 비교

추가적인 TIL....

후..... 교수님이 부등호만 잘 바꾸면 된다고해서 부등호만 바꿨는데..... 인덱스 오류가 났다...

이유는 heap을 생성할 때 0으로 초기화해서 만들었는데.... 이게 문제였다!

왼쪽, 오른쪽 비교할 때 작은거로 스왑하는데 그 오른쪽 값이 0이니까 당연히 계속 .....계속.... now=son부분이 계속 가버렸다....

그래서 INF = 879886451 이런걸 만들어 이거로 처음에 heap을 들때 초기화 했고, pop()에서 hindex부분도 INF로 초기화함으로써 해결되었다.

이것도 다른분께 도움을 받아 해결했다....^,ㅠ 아직 디버깅 해도 문제를 고치는 것에 한계가 느껴진다...