전체 글

오늘 한것 다익스트라 알고리즘 우선순위 큐 구현버전 학습 힙 자료구조 학습 오늘 배운것 힙 자료구조는 완전이진트리로 구현되어있으며, 루트의 값이 항상 자식보다 크거나 작은 일관된 규칙을 유지한다. 따라서 탐색, 저장 시 이진트리의 특징인 logN의 시간복잡도를 가지게 된다. 다익스트라 알고리즘에서는 가장 짧은 간선을 가진 노드를 계속해서 탐색해 나간다. 즉 최단거리 노드를 계속해서 탐색을 해야한다. 만약 탐색해야하는 자료구조가 리스트라면 별 수 없이 완전탐색을 해야하므로 시간복잡도는 O(N)이 된다. 그러나 힙을 탐색하는 경우 탐색에 O(logN)만 필요하게되므로 성능을 향상시킬 수 있다.

요즘 코딩테스트 준비로 다이나믹 프로그래밍과 씨름중이다. 다이나믹 프로그래밍의 개념을 실무에서 쓸 일은 없었던지라 이런 방식으로 코드를 작성해본 경험이 없어서 애를 먹고있다. 물론 캐싱 기법은 실무에서도 쓸일이 많지만, 점화식이 필요한정도는 글쎄... 어떤 컨셉인지는 이해를 했으나 주어진 문제에서 규칙을 찾아내는것이 너무 어렵다. 반복적으로 여러 문제들과 부딪혀 봐야 감이 올 것 같다. 머리속의 생각을 코드로 옮기는 연습을 많이 해야겠다.

오늘 한것 다이나믹 프로그래밍 문제풀이 복습 오늘 배운것 점화식 세우기 연습

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