Data Structure

들어가며 나에게 맞는 알고리즘 공부 방법을 찾고나니 한결 마음이 가벼워졌다. 또, 오늘은 문제가 쉬웠는지 직접 문제 풀이에 성공해서 꽤나 뿌듯했다. 이 기쁜 마음을 안고, 오늘의 TIL은 힙의 개념과 문제풀이, 새로 알게 된 개념을 정리해보고자 한다. 힙 힙(heap)은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 어떤 정수형 배열이 있다고 가정해보자. [9, 8, 7, 6, 5, 4, 3, 2, 1] 이 배열에서 가장 작은 값을 꺼내오려면 요소 하나씩을 검색해서 찾아내야 한다. 그렇게 되면 시간복잡도는 O(n)이 된다. 해당 배열을 힙으로 구현한다면 O(log n)의 시간복잡도를 갖게 된다. 위에서 말했듯이 힙은 완전 이진 트리로 이루어져있기 ..

들어가며 갑자기 잘 쓰던 들어가며에 뭘 써야할 지 헷갈리기 시작했다. 원래 아무말이나 적었던거 같은데... 오늘도 열심히 잠을 잤으니 그 업보를 지금의 나에게 지우기로 하고 오늘의 TIL은 이진 탐색트리의 개념과 문제 풀이를 정리해보고자 한다! 이진 탐색 트리 이진 탐색 트리(BST, Binary Search Tree)란 이진 탐색(Binary search)과 연결리스트(Linked list)의 아이디어를 결합한 자료구조의 일종이다. 커리큘럼상 뒤에 배우게 될 이진탐색의 경우 소요되는 시간 복잡도는 O(log n)으로 빠르지만 삽입, 삭제가 불가능하다. 반면 연결리스트의 경우 삽입, 삭제에 필요한 시간 복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)가 소요된다. 이진 탐색 트리는 이진 탐색의 효..

들어가며 알고리즘 1주차가 끝나는 날이다. 항해99 알고리즘 주차에서는 한 주차가 끝날 때마다 테스트를 보게되고, 오늘 그 테스트를 보았다. 사실 1주차 내내 개념 정리에 주로 힘을 써왔기 때문에 구현에는 자신이 없어서 테스트를 잘 볼 수 있을까 걱정했는데 아니나 다를까 어렵더라… 어찌저찌해서 결국 해결은 했는데 문제를 풀어냈다!라는 기쁨보다는 여전히 한참 부족하다는 자괴감이 많이 들었다. 테스트 2시간이었는데 시간이 부족해서 추가시간까지 쓰고 나서야 겨우 해결을 하는 바람에 오늘 문제공부를 할 시간이 부족했다. …라고 오늘 문제풀이를 못하는 이유를 늘어놨는데 결론은 오늘의 TIL은 항해99의 커리큘럼에 따라 그래프와 DFS의 간단한 개념을 정리해보고자한다! 그래프 그래프는 정점(vertex)와 간선(e..