큰 파도를 헤쳐나온 것일까,
더 큰 파도로 들어간 것일까
알고리즘을 마치고 주특기 주차가 시작되었다.
진짜 마지막 알고리즘 주차. 이제 추가 공부는 스스로다. 남은 항해 기간에도 알고리즘 공부를 절대 놓아서는 안 된다고 생각하는데, 어떻게 될런지 -
마지막 주차라서 마음이 많이 뜨는 부분도 있었는데. 그래도 나름 열심히 문제를 붙드는 시간들도 있었던 것 같다.
그래도 확실히 이전보다 뭔가 싱숭생숭한 것들이 있었다. 아무래도 주특기를 앞두고 알고리즘을 공부하는 부분들 때문이었던 것 같다. 마지막 DP는 정말 어려웠는데 -
잘 마친 시간들에 대해 마지막을 회고하고 ! 딱 털고 ! 주특기 집중하자.
그리고 주특기 3주 마치면, 하루 1-2문제. 꼭 도전하자 !
알고리즘 TIL
이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다.
이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다.
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
다익스트라(Dijkstra) 알고리즘은 최단 경로 문제 중에 Single-source path 찾는 알고리즘입니다.
- 음수 가중치를 가진 간선이 없어야 합니다.
- 탐욕 알고리즘(greedy algorithm)을 사용합니다.
- 미방문 정점들을 저장하기 위해 우선순위 큐를 사용합니다.
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)
출처 : https://yoongrammer.tistory.com/88?category=987044
플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로 문제 중에 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘입니다.
- Dynamic Programming을 사용합니다.
- 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다.
- 그래프에 음수 사이클 여부를 확인할 수 있습니다.
// 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
주특기 TIL
드디어 주특기.
스프링은 생각보다 어렵지 않은 '느낌'이 들고.
과제는 생각보다 오래 걸릴 것 같은 '느낌'이 든다.
강의에 의존하지 말라고 하셨지만, 아직까진 강의라는 기초가 있어야만 할 것 같다는 불안인지- 나만의 공부 방법인지-
하지만 분명, 시간이 없어서라기보다 찾고 찾으면서 해결방안들을 찾아나가게 될 것 같다.
길은 있다. 지름길이나 쉽게 가려는 것보다. 제대로 하려고 하자.
나에게 필요한 것이 그거이니까 -
그렇다고 오래 걸리는 곤조를 원하는 것은 아니다. 나아가야 할 바가 분명히 있으니까 - !
다음주 과제 및 2주차로 넘어가는 시간 속에서. 실전 전에 주특기에 걸맞는 나의 타임라인을 잘 설정하자.
너무 늦게 자고 이도저도 제대로 하지 못하지 말고 -
오직 기도와 말씀으로 아자 !