Judaeng

맨 처음에 힙을 들었을 때 엉덩이(hip)가 생각날 수도 있지만 힙은 heap이다. 무언가를 차곡차곡 쌓아 올린 더미라는 뜻이라고 한다. 그렇다면 힙(heap)이란 무엇인가요? 🤷‍♂️ 1. 힙(heap)은 완전 이진트리의 형태로 만들어져 있고, 우선순위 큐를 위하여 만들어진 자료구조이다. 2. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 3. 힙(heap)은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 4. 힙 트리는 중복 값을 허용한다. 5. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다.(아래 사진 참조) * 완전 이진트리란? * 마지막을 제외한 모든 노드의 자식들이 꽉 채워진 이진트리이다. 힙(heap)의 종류 최대 힙..

첫 정점에서부터 그래프에 존재하는 모든 정점들을 한 번씩 방문하는 것을 그래프의 탐색이라고 한다. 그래프의 탐색 방법에는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 2가지 방식이 있다. 말 그대로 '깊이'를 우선시해서 탐색하는지, '너비'를 우선시해서 탐색하는지에 차이가 있다. 아래 그림을 보면서 이해해보도록 하자. DFS (Depth-First Search, 깊이 우선 탐색) 깊이 우선 탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. 간단히 재귀호출(Recurse)을 사용하여 구현하거나, 스택(Stack)을 사용하여 구현한다. 스택으로 구현할 때는 모든 노드가 중복 없이 딱 한 번씩만 담겨야 하고, 재귀로..

Graph(그래프)란 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조라고 표현할 수 있다. 서로 다른 점들이 직접적인 관계를 가지고 있다면 바로 이어주는 선이 존재하고, 간접적인 관계를 가지고 있다면 다른 여러 점을 거쳐서 이어지는 선이 존재할 수 있다. 여기서 이야기하는 점은 그래프에서는 정점(vertex)이라고 표현하고, 선은 간선(Edge)라고 표현합니다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조가 Graph(그래프)이다. EX) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방통행길), 선수 과목 등 let subway = { '교대': ['동대문운동장','사당','충무로'], '동대문운동장': ['교대','을지로3가','충무..

복잡도(Complexity) 복잡도는 알고리즘의 성능을 나타내는 척도이다. 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 속도에 해당하는 알고리즘의 수행 시간 분석 결과를 말한다. 공간 복잡도는 메모리 사용량에 대한 분석 결과를 말한다. +추가 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다. 시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다. 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(Big-Ω), 빅세타(big-Θ) 표기법 등이 있다. ✏️시..