728x90 컴공생의 Knowledge/Algoritm Notion5 깊이 우선 탐색(Depth First Search)을 알아보자 (feat.JS) 오늘은 바로 어제 알아봤던 너비 우선 탐색의 애인과 같은 길찾기 알고리즘인 깊이 우선 탐색(DFS)에 대해서 공부해보겠습니다. 먼저 너비 우선 탐색과 같이 깊이 우선 탐색(DFS: Depth First Search) 명칭의 의미를 확인해보겠습니다. 먼저 너비 우선 탐색을 보지 않으셨다면 먼저 보고 오시는걸 추천드립니다. 2022.07.31 - [컴공생의 Knowledge/Algoritm Notion] - 너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS) 너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS) 오늘은 바로 지난번에 풀었던 게임 맵 최단거리 문제 풀이에서 알고리즘으로 활용한 너비 우선 탐색(BFS)에 대해서 공부해보려 합니다. 먼.. 2022. 8. 1. 너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS) 오늘은 바로 지난번에 풀었던 게임 맵 최단거리 문제 풀이에서 알고리즘으로 활용한 너비 우선 탐색(BFS)에 대해서 공부해보려 합니다. 먼저 너비 우선 탐색(BFS: Breadth First Search) 명칭의 의미를 확인해보겠습니다. 혹시 지난 게임 맵 최단거리 문제 풀이가 궁금하신 분은 아래에 있는 이전 포스팅을 보고 오시기 바랍니다. 2022.07.29 - [컴공생의 Knowledge/Algoritm Solution] - [프로그래머스] 깊이/너비 우선 탐색 - 게임 맵 최단거리 문제 풀이 (feat.JS) [프로그래머스] 깊이/너비 우선 탐색 - 게임 맵 최단거리 문제 풀이 (feat.JS) 오늘은 프로그래머스에서 오랜만에 깊이/너비 우선 탐색(DFS/BFS) 관련 문제 중 게임 맵 최단거리 문제.. 2022. 7. 31. 프림 알고리즘(Prim's Algorithm)을 알아보자 오늘은 지난번 섬 연결하기 문제에서 다뤘던 프림 알고리즘에 대해 알아보겠습니다. 프림 알고리즘이란? 프림 알고리즘은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘입니다. 여기서 무향 그래프란 방향성이 없는 노드들이 연결되어있는 그래프 자료구조를 뜻합니다. 그래프의 자료구조 형태는 바로 아래 이미지와 같습니다. 즉, 무향 그래프는 두 노드간 방향성이 없고 연결에 대한 가중치만 있는 그래프입니다. 이 무향 그래프에서 모든 노드들을 연결하는데 있어 최소 비용의 합으로 연결되어진 최소 비용 신장 트리를 구하는 알고리즘 중 하나가 프림 알고리즘입니다. 프림 알고리즘.. 2022. 7. 14. 자료구조 힙(Heap)은? 무엇인가? 오늘은 자료구조 중 힙(Heap)을 알아보겠습니다. Heap이란 무엇인가? 힙은 자료구조 중 최댓값, 최소값을 가장 빨리 찾아내는 자료구조로 최댓값을 가장 빨리 찾아내는 힙은 "최대 힙", 최소값을 가장 빨리 찾아내는 힙은 "최소 힙"으로 두가지 종류의 힙이 있습니다. 과연 힙은 어떤 구조로 이루어져 있으며, 어떻게 최댓값 or 최소값을 빠르게 찾아낼 수 있는지에 대해서 공부해보겠습니다. 마지막으로 힙을 활용한 자료구조인 우선순위 큐(Priority Queue)를 JavaScript를 활용하여 구현할 예정이니 끝까지 함께 공부하시면 감사하겠습니다. Heap의 구조 힙은 완전 이진 트리구조로 이루어져 있습니다. 완전 이진 트리란 아래 그림과 같이 자식이 최대 두개인 트리 구조이며, 최하위 노드를 제외한 모.. 2022. 6. 29. 알고리즘 시간복잡도란 무엇인가? 알고리즘 시간복잡도는 무엇일까? 알고리즘 문제 풀이하는 사람들이 품을 수 있는 궁금증이라고 생각합니다. ◆ 시간복잡도의 정의 알고리즘 시간복잡도란 어떤 알고리즘에 대해서 입력 개수(N)에 비례하여 걸릴 수 있는 시간, 실행 횟수를 수치화 시켜서 비교할 수 있는 데이터로 만든 값입니다. 네이버에서 검색한 결과는 아래와 같습니다. 어떤 알고리즘이 더 빠른가 즉, 명령어 실행 횟수가 더 적은가를 분석하기 위해 사용되는 시간 복잡도는 알고리즘을 평가하기 위한 중요한 요소 중 하나입니다. 이제 무엇인지는 알 것 같다는 느낌이 들 것 입니다. ◆ 시간복잡도 표기법 이제는 시간복잡도에 대한 표기 방법에 대해서 설명드리겠습니다. 표기 방법은 아래와 같습니다. O({알고리즘 입력 개수(N)에 비례하여 실행되는 횟수 계산.. 2022. 6. 16. 이전 1 다음 728x90
