애옹쓰

본 글에선 스택과 큐에 대해 알고 있다는 가정하에 설명합니다. DFS와 BFS는그래프에서 탐색을 하기 위한 알고리즘입니다. 그래프는 아래와 같이 노드와 간선으로 이루어진 구조를 말합니다. 잘 아실 이진트리도 이에 해당합니다. 긴말 없이 DFS부터 알아보도록 하겠습니다. Depth First Search DFS는 자료구조 stack을 이용해 구현됩니다. DFS의 작동 과정을 말로 먼저 알아보면 시작 노드를 스택에 삽입하고 방문처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드를 스택에 삽입하고 방문처리한다.(여러 개일 경우 통상적으로 가장 작은 노드부터 삽입한다.) 방문하지 않은 인접 노드가없을 경우 최상단 노드를 꺼낸다. 방문하지 않은 노드가 없을 때 까지 과정 2,3번을 반복한다. 탐색의 시간 복..

그리디 알고리즘(greedy algorithm)을 직역하면 탐욕 알고리즘입니다 말그대로 현재 상황에서 가장 최적의 해라고 생각되는 것을 선택해 나가는 방식의 알고리즘 입니다. 따라서 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 그리디 알고리즘은 사실 특정 알고리즘이라고 한정 짓기에는 범위가 상당히 방대하다 따라서 floyd warshall 또는 dijkstra와 같은 암기를 하거나 팀노트를 준비하는 식의 방법으로는 문제를 전부 풀 수는 없습니다. 범위가 방대한만큼 사전 지식 없이도 풀 수 있는 문제(예시로 많이드는 거스름돈 문제)도 있지만 여러 유형을 접해보고 문제를 풀어보며 훈련해야합니다. 그럼 같이 기초문제를 먼저 풀어보겠습니다. 1이 될 때까지 어떠한 수 n이 1이 될 때까지 다..

힙 정렬은 기본적으로 힙 자료구조를 기반으로 한다. 간단히 힙 자료구조에 대해 알아보면 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'이다. 최솟값 or 최댓값을 빠르게 찾아내는 것이 힙의 핵심이다. 위 사진은 heap tree를 시각화한 것이다. 하지만 트리의 인덱싱을 아는 사람이라면 위 사진이 무엇인가 이상해 보일 거다. 바로 형제 노드 간의 정렬은 되어있지 않다는 점이다. 이를 weak heap, 반정렬 상태 등등이라 부른다. "아니 그러면 어떻게 정렬을 하나요?" 위에서 힙의 핵심은 최솟값 or 최대값을 빠르게 찾아내는 것이라 했다. 힙의 root node는 항상 우선순위가 1등이다. 즉 최소값 또는 최댓값이란 것이다. 이를 이용해 root node를 삭제..