TIL

오늘 한것 이것이 코딩테스트다 with 파이썬 챕터9 - 최단 경로 학습 운영체제 12강 - 세마포 학습 오늘 배운것 최단 경로(Shortest Path) 알고리즘은 말 그대로 최단 경로를 구하는 알고리즘이다. 그래프 상의 노드간 간선을 통해 계산한다. 다익스트라, 벨만포드, 플로이드워셜 알고리즘 등이 이에 해당한다. 세마포는 임계구역(Critical Section)에서 발생하는 동기화문제를 해결하기 위해 사용되는 동기화 도구중 하나이다.

오늘 한것 이것이 코딩테스트다 with 파이썬 챕터8 - 다이나믹 프로그래밍 학습 오늘 배운것 다이나믹 프로그래밍(Dynamic Programming)은 작은 문제의 풀이를 통해 큰 문제를 해결하는 방법이다. 분할정복(Divide and Conquer)과의 공통점은 문제를 작게 나눈다는 점이고, 차이점은 작은 문제의 재활용 여부이다. DP의 풀이방법에는 재귀로 풀이하는 탑다운(Top-down)방식과 반복문으로 풀이하는 (Bottom-up) 방식이 있다. 대부분의 경우 성능은 바텀업 방식이 유리하다. 탑다운방식은 재귀호출로 인해 스택에 한계가 있는 경우 오류가 발생하기 때문이다. 대신 탑다운방식은 코드를 간결하게 만들 수 있다는 장점이 있다.

오늘 한것 이것이 코딩테스트다 with 파이썬 챕터6 - 정렬(계수) 학습 이것이 코딩테스트다 with 파이썬 챕터7 - 이진탐색 학습 오늘 배운것 순차탐색은 모든 데이터를 순회하면서 찾는 방법이다. 정렬되지 않은 데이터를 탐색하는 경우에 사용하며 시간복잡도는 O(N)이다. 이진탐색은 정렬된 데이터를 찾는 방법이다. 중간값 또는 부모노드를 기준으로해서 양쪽으로 비교를 하기 때문에, 비교할 때마다 탐색 범위가 절반으로 줄어드는 장점이 있다. 따라서 시간복잡도는 O(logN)이 된다.

오늘 한것 이것이 코딩테스트다 with 파이썬 챕터5 - 그래프(DFS,BFS) 학습 이것이 코딩테스트다 with 파이썬 챕터6 - 정렬(선택, 삽입, 퀵) 학습 오늘 배운것 정렬된 상태에서는 삽입정렬의 성능이 좋다. 퀵 정렬은 이미 정렬된 데이터를 대상으로 하는 경우 성능이 좋지 않다. 그래서 라이브러리에 최적화된 정렬알고리즘은 시간복잡도 NLogN을 보장하기위해 적절한 피벗값을 선택하는 알고리즘이 추가되어 있다.