스파르타코딩클럽/항해99

항해 5주차 WIL

YONS 2022. 2. 13. 15:38

필수 포함 키워드 : 이진탐색, 최단경로(다익스트라, 플로이드)

 

  • 이진탐색이란?
    • 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법
  • 이진탐색의 효율성
    • 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.
    • import math math.log2(100000000) # 26.575424759098897
    • 이진탐색을 위해서는 정렬되어 있어야 한다.

 

  • 최단경로
    • 그래프로 표현. 각 지점은 노드, 도로는 간선.
    • 다익스트라, 플로이드-워셜을 배울 예정.
  • 다익스트라 알고리즘
  • 1. 출발지를 s로 정하고, 다음과 같이 표시한다. (s, t, x, y, z 순) 거리 = [0, inf, inf, inf, inf] 방문 = [True, False, False, False, False] 2. 갈 수 있는 노드들의 최소거리를 측정한다. s->t: 10 s->y: 5 (s, t, x, y, z 순) 거리 = [0, 10, inf, 5, inf] 방문 = [True, False, False, False, False] 3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다. y->t: 3 y->x: 9 y->z: 2 (s, t, x, y, z 순) 거리 = [0, 8, 14, 5, 7] 방문 = [True, False, False, True, False] 4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다. z->x: 6 (s, t, x, y, z 순) 거리 = [0, 8, 13, 5, 7] 방문 = [True, False, False, True, True] 5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다. t->x: 1 t->y: 2 (s, t, x, y, z 순) 거리 = [0, 8, 9, 5, 7] 방문 = [True, True, False, True, True] 6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다. x->z: 4 (s, t, x, y, z 순) 거리 = [0, 8, 9, 5, 7] 방문 = [True, True, True, True, True] 7. 방문 안한 노드가 없으므로 끝낸다. (s, t, x, y, z 순) 거리 = [0, 8, 9, 5, 7] 방문 = [True, True, True, True, True]

 

  • 플로이드-워셜
    • 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리.
    • 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리.자기자신으로 가는 비용은 0
    • 직접 연결되어있지 않은 경로는 무한대.
    • $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

 

 

 

 

 

나는 리액트에 대해 아무것도 모르다가 이제 처음 접하는데 과제들은 나를 기다리고 있고 그 와중에 이미 지나간 알고리즘까지 복습하려니 참으로 괴로웠다. 그래서 그냥 복습하지는 않고 수업자료에서 복사+붙여넣기만 했다. 나는 다가올 공부를 위해 지나간 공부에는 연연하지 않겠어

 

차라리 알고리즘 주차가 토요일에 끝나고 일요일에 마음편하게 복습하며 마무리한 다음 월요일에 깔끔하게 새출발을 했더라면 어땠을까 싶기도 하다.

 

오늘은 갑자기 뭘해도 자꾸만 에러가 뜨는 기현상을 겪었다. 한참을 코드 뜯어보며 뭐가 꼬였는지 살펴봤는데 답이 전혀 보이질 않았다. 그러다 결국 개발자도구 콘솔창에 뜬 에러를 복사해서 구글에 붙여넣기 했더니... https://studioplug.tistory.com/383 에서 해답을 찾았다.

꼬일 땐 괴로워하지 말고 맘편하게 콘솔창을 믿자;;; 항상 기계가 인간보다 정확하다.

 

설 연휴 때 앞니에 충치가 있는 느낌을 받았는데 항해 끝날때까지 미루려고 했더니 오늘은 정말 큰일날 것 같은 느낌이 들었다; 그냥 가만 있는데도 욱신거리고 시린 느낌이 든다... 신경치료까진 안하겠지ㅠ 화성탐사 이런거 하지 말고 두번째 영구치 맹출을 연구해달라고ㅠㅠ