[WEEK03] DAY25

https://velog.io/@yerimii11/WEEK03-DAY25 2021년 11월 25일에 작성된 게시글 아카이브입니다.  (사유: 블로그이전)

[WEEK03] DAY25

---

다익스트라는 최단경로를 찾는 알고리즘
그리디 알고리즘은 문제를 푸는 방식 분할정복같이
그리디 중의 하나가 다익스트라

다이나믹 - 할 수 있는 선택을 모두 알아보고 그 중 좋은 것
그리디 - 그냥 바로 다음단계 중에서 제일 좋아보이는 것을 선택

---

18405 경쟁적 전염 (BFS)

코드

import sys
from collections import deque
input = sys.stdin.readline

# n개의 줄과 원소, k 이하의 바이러스 번호
n, k = map(int, input().split())
virus = []
graph = []
for x in range(n): # 2차원 리스트 받기
    graph.append(list(map(int, input().split())))
    for y in range(n):
        # graph에서 virus 정보 받아오기
        if graph[x][y] != 0:
            virus.append(((graph[x][y], x, y))) # 바이러스 번호, 좌표
                    # (x,y)자리에 있는 virus 번호 저장

seconds, x, y = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def BFS(seconds, x, y):
    # global time_count
    time_count = 0
    q = deque(virus) #q에 바이러스 정보 넣음
    while q:
        if time_count == seconds: 
            break

        for _ in range(len(q)):
            virusnum, x, y = q.popleft() # 한 줄 빼서 탐색
            for i in range(4): # 동서남북 탐색
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if graph[nx][ny] == 0: # 동서남북 중 이동할 좌표 값이 0이면
                        graph[nx][ny] = graph[x][y] # 현재 바이러스 번호를 이동할 좌표에 퍼뜨림
                        q.append((graph[nx][ny], nx, ny)) # 바뀐 바이러스 좌표 정보 업데이트
                                # 현재 바이러스 번호, xy 좌표
        time_count += 1 # 초 카운팅
        
    return graph[x-1][y-1] # 동서남북 탐색 끝 원점으로 돌아옴
    
                        
virus.sort()
BFS(seconds, x, y)
print(graph[x-1][y-1])

.
.

---

시험 문제였는데
나머지 2개는 손 못 댔음!
마저 풀었음

4256 트리

---

코드

import sys
input = sys.stdin.readline

def getPostorder(preorder,inorder): #리스트 둘 다 길이 같으니 둘 중 아무거나로 종결조건 줘도 됨
    if len(preorder) <= 1: # 노드 갯수가 0이더라도 빈리스트 출력됨 # if == 0 pass도 괜찮음
        return preorder # 재귀로 나누고 나눠서 숫자 한 글자씩 출력
    else:
        root = preorder[0]
        n = inorder.index(root) # 이 값을 가지는 list의 idx를 출력
        in_left, in_right = inorder[0:n], inorder[n+1:]
        pre_left, pre_right = preorder[1:len(in_left)+1], preorder[len(in_left)+1:]

        l_subtree = getPostorder(pre_left, in_left) # 루트 외 서브트리
        r_subtree = getPostorder(pre_right, in_right)
        return (l_subtree + r_subtree + [root]) # [root] == list(root) 동일문법

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        m = int(input())
        preorder = list(map(int, input().split()))
        inorder = list(map(int, input().split()))
        result = getPostorder(preorder, inorder)
        print(*result)

---

이전에 푼 5639 이진 탐색 트리 문제와 흡사하게 접근하면 풀 수 있는 문제였다 !

---

Git merge

• 머지 >> 내꺼
  메인에서 git merge yerim(합칠 브랜치)
  머지하고나서 git push origin main
• 타인꺼 머지
  타인 브랜치 들어가서 pull 받고
  메인가서 git merge 타인브랜치이름
  이 사이에 포크에서 얼 커밋
  그다음 git push 타인브랜치이름
• 포크에서 로컬체인지 - 스테이지드 밑에 더블클릭해서 내려놓고 오른쪽아래에 커밋
• 푸쉬안되면 포크 - 메인 가서 위에 푸시

---

피곤피곤
굿나잇