Dev On The Coffee Dev On The Coffee

# 트리 (Tree) 가계도와 같은 계층적인 구조를 표현할 때 사용하는 자료구조이다. - 루트 노드 (root node): 부모가 없는 최상위 노드 ex) A - 단말 노드 (leaf node): 자식이 없는 노드 ex) G, E, F - 크기 (size): 트리에 포함된 모든 노드의 개수 ex) 7개 - 깊이 (depth): 루트 노드부터 해당 노드까지의 거리 ex) A: 0 / B, C: 1 / D, E, F: 2 / G: 3 - 높이 (height): 깊이 중 최댓값 ex) 3 - 차수 (degree): 각 노드의 (자식 방향) 간선 개수 ex) A, B: 2 / C, D: 1 - 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개 # 트리의 순회 (Tree Traversal) 트리 자료구조에..

# 우선순위 큐 (Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트(List), 힙(Heap) 두가지 방식으로 구현 가능하다. 리스트의 경우 데이터를 단순히 리스트의 뒤에 삽입하고 우선순위를 기준으로 선형탐색한다. 따라서 삽입시간은 시간복잡도가 O(1)이지만, 삭제시간은 선형탐색으로 인해 O(N)이 소요된다. 반면, 힙은 삽입시간, 삭제시간 모두 O(logN)의 시간복잡도를 보장한다. 힙의 또다른 특징은 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다는 점이다. 이를 힙 정렬(Heap Sort)이라 하는데, 힙 정렬은 O(NlogN)의 시간 복..

# 스택(Stack) 스택 자료구조는 상자 쌓기와 비슷하다. 차곡 차곡 아래서부터 위로 상자를 쌓아 나가면, 상자를 뺄 때는 상자들이 무너지지않게 맨 위의 가장 나중에 쌓은 상자부터 빼야 한다. 스택도 마찬가지다. 가장 나중에 들어온 데이터를 가장 먼저 빼는 후입선출(LIFO: Last In First Out) 구조를 가진다. 파이썬에서는 별도의 라이브러리 없이 기본 리스트 자료형으로 스택을 쉽게 구현할 수 있다. # Stack으로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 구현 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stac..

"코딩 테스트를 떨어졌다!" 최근에 가장 많이 맞닥뜨린 상황이다. 인턴, 정규직 지원은 아니지만 간절히 원하던 교육 프로그램에 지원할 때마다 항상 2차 코테를 넘어서지 못하고 있다... 비전공자의 입장이다 보니 코테에 대한 제대로 된 지식 없이 약간의 문제 풀이 연습으로 도전한 게 화근인 듯싶다. 처음에는 1차 코테를 통과하길래 솔직히 "오? 되나?" 싶었다. 그러나 다른 분들 후기를 보고 나니 코테는 시간 복잡도나 알맞은 자료구조 선택 같이 깊게 생각하고 코드에 녹여야 할 요소가 많았다. 사실, 교육 프로그램 입과를 목표로 했기 때문에 코테 준비사항에서도 큰 요구가 없는 것 같았다. '자료구조'나 '알고리즘'이 중요한 과목임을 알지만 '들어가서 공부하자' 싶었다. 특히, 비전공자니까 혼자 공부하는 것보..