[WIL] 220207~220212_항해 5주차

큰 파도를 헤쳐나온 것일까,
더 큰 파도로 들어간 것일까

알고리즘을 마치고 주특기 주차가 시작되었다.

Algorithm(2/7 ~ 2/10)

진짜 마지막 알고리즘 주차. 이제 추가 공부는 스스로다. 남은 항해 기간에도 알고리즘 공부를 절대 놓아서는 안 된다고 생각하는데, 어떻게 될런지 -
마지막 주차라서 마음이 많이 뜨는 부분도 있었는데. 그래도 나름 열심히 문제를 붙드는 시간들도 있었던 것 같다.
그래도 확실히 이전보다 뭔가 싱숭생숭한 것들이 있었다. 아무래도 주특기를 앞두고 알고리즘을 공부하는 부분들 때문이었던 것 같다. 마지막 DP는 정말 어려웠는데 -
잘 마친 시간들에 대해 마지막을 회고하고 ! 딱 털고 ! 주특기 집중하자.
그리고 주특기 3주 마치면, 하루 1-2문제. 꼭 도전하자 !

알고리즘 TIL

• 월요일
• 화요일
• 수요일
• 목요일

이진 탐색

이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다.
이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다.

• 이진 탐색 동작 방식

1. 배열의 중간 값을 가져옵니다.
2. 중간 값과 검색 값을 비교합니다.
   1. 중간 값이 검색 값과 같다면 종료합니다. (mid = key)
   2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key)
   3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)
3. 값을 찾거나 간격이 비어있을 때까지 반복합니다.

• 구현 예시

int binarySearch (int arr[], int low, int high, int key) {
  
  if (low > high) // 종료 조건2 검색 실패.
    return -1;  

  int mid = low + (high-low)/2;

  if (arr[mid] == key) // 종료 조건1 검색 성공.
    return mid;
  else if (arr[mid] > key)
    return binarySearch(arr, low, mid-1, key);
  else
    return binarySearch(arr, mid+1, high, key);
}

출처 : https://yoongrammer.tistory.com/75

• 이진탐색 문제 풀이 시 어려웠던 점
  단순 구현은 오히려 잘 받아들여지고 금방 익힐 수 있었다. 그런데 문제로 접근할 때 항상 중간 값을 지정하는 것이 헷갈리기도 했고 무엇보다 '타겟'을 잡는 것이 어려웠다. 이진탐색은 속도가 기하급수적으로 줄어들기 때문에 10억 정도의 수를 제시하는 문제는 모두 풀어야 한다. 그런데 이진 탐색 문제의 중간 값은 쉽게 start, end 나 low, high를 주지 않고 임의의 값으로 중간 값을 지정하여 타겟을 향해 맞춰가야 하는 문제가 일반적이라고 느꼈다. 아무래도 이 부분을 다시 공부할 때에도 주의 깊게 보고 완전히 이해하여 문제를 풀 수 있도록 연습해야겠다.

최단 경로(다익스트라, 플로이드)

다익스트라(Dijkstra) 알고리즘은 최단 경로 문제 중에 Single-source path 찾는 알고리즘입니다.

• 음수 가중치를 가진 간선이 없어야 합니다.
• 탐욕 알고리즘(greedy algorithm)을 사용합니다.
• 미방문 정점들을 저장하기 위해 우선순위 큐를 사용합니다.

• 다익스트라 알고리즘 동작 방식 (의사 코드 구현)
  다익스트라 알고리즘은 우선순위 Queue를 사용하는 BFS (Breadth-First Search) 알고리즘과 비슷합니다.
  S = 방문한 정점들의 집합
  Q = 방문하지 않은 정점들을 저장하고 있는 우선순위 큐

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G,s)
2  S ← ∅
3  Q ← V [G]
4  while Q != ∅
5    do u ← Extract-Min(Q)
6    S ← S ∪ {u}
7    for each vertex v ∈ Adj[u]
8      do Relax(u, v, w)

1. 그래프(G)에 있는 모든 정점을 초기화합니다.
   모든 정점은 d[v] = ∞ 로 초기화 되고 그중 시작 정점인 s는 0으로 초기화 합니다.
2. 집합 S를 초기화 합니다.
3. 우선순위 큐(Q)에 그래프에 있는 모든 정점을 저장합니다.
4. 큐가 빌때까지 다음 작업을 진행합니다.
   1. 우선순위 큐에서 가장 작은 d값을 가진 정점 u를 가져옵니다.
      (d : 시작 정점부터 현재 정점까지의 최단경로 측정치)
   2. 정점 u를 집합 S에 넣습니다.
   3. 정점 u와 인접한 정점들에 Relax 연산을 수행합니다.

출처 : https://yoongrammer.tistory.com/88?category=987044

플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로 문제 중에 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘입니다.

• Dynamic Programming을 사용합니다.
• 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다.
• 그래프에 음수 사이클 여부를 확인할 수 있습니다.

• 플로이드 와셜 알고리즘 동작 방식

1. 플로이드 와셜 알고리즘은 각각의 정점 쌍을 지나는 그래프의 모든 경로를 비교합니다.
2. 플로이드 와셜 알고리즘은 Dynamic Programming을 사용하여 정점 i에서 j로 직접 가는 경로와 중간에 어느 정점을 거쳐 가는 경로를 비교하여 최단경로를 찾습니다.
3. 이 방식으로 모든 정점 쌍에 대한 최단 거리를 구하게 됩니다.

• 구현 예시

// n = 정점의 수
// d = n*n 행렬
for i = 1 to n
  for j = 1 to n
    if i == j
      d0[i, j] = 0
    if (i, j) is an edge in E 
      d0[i, j] = wij
    else
      d0[i, j] =infinity

for k = 1 to n // 중간정점 집합
  for i = 1 to n
    for j = 1 to n
      dk[i, j] = min (dk-1[i, j], dk-1[i, k] + dk-1[k, j])

출처 : https://yoongrammer.tistory.com/90?category=987044

• 최단경로 문제 풀이 시 어려웠던 점
  처음에 다익스트라를 만났을 때는, 이게 뭘까? 라고 생각했다.
  전혀 이해가 안 가는 상황인 것 같았는데 팀원의 발표로 인해 머릿속에 여러 가지를 들이 붓듯이 했던 것 같다.
  그리고 그것이 내 것이 되었는가 확인할 시간도 없이 하루를 마치고 다음 날이 되었다.
  오히려 플로이드를 하면서 다익스트라까지 모아서 이해가 되었던 것 같다.
  문제를 풀 때, 다시 재미가 붙으면서 하나 하나 직접 풀어볼 수 있었다.
  주특기 때문에 마음이 막- 잡히던 시간은 아니었지만 알고리즘 마지막 주차에 가장 즐겁게 문제를 푼 것은 최단경로 였던 것 같아서 참 고맙고 재미있었다! :)

주특기 PBL 시작(2/11 ~ 2/12)

주특기 TIL

• 금요일
• 토요일

드디어 주특기.
스프링은 생각보다 어렵지 않은 '느낌'이 들고.
과제는 생각보다 오래 걸릴 것 같은 '느낌'이 든다.
강의에 의존하지 말라고 하셨지만, 아직까진 강의라는 기초가 있어야만 할 것 같다는 불안인지- 나만의 공부 방법인지-

하지만 분명, 시간이 없어서라기보다 찾고 찾으면서 해결방안들을 찾아나가게 될 것 같다.
길은 있다. 지름길이나 쉽게 가려는 것보다. 제대로 하려고 하자.
나에게 필요한 것이 그거이니까 -
그렇다고 오래 걸리는 곤조를 원하는 것은 아니다. 나아가야 할 바가 분명히 있으니까 - !

다음주 과제 및 2주차로 넘어가는 시간 속에서. 실전 전에 주특기에 걸맞는 나의 타임라인을 잘 설정하자.
너무 늦게 자고 이도저도 제대로 하지 못하지 말고 -

오직 기도와 말씀으로 아자 !