본문 바로가기

분류 전체보기126

최단 경로 알고리즘(다익스트라, 플로이드-워셜) 최단 경로 알고리즘가장 짧은 경로를 찾는 알고리즘각 지점은 그래프에서 노드로 표현지점 간 연결된 도로는 그래프에서 간선으로 표현다양한 문제 상황한 지점에서 다른 한 지점까지의 최단 경로 → BFS 이용한 지점에서 다른 모든 지점까지의 최단 경로 → 다익스트라 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로 → 플로이드 워셜 알고리즘최단 경로 알고리즘 동작 과정최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가진다.처리 과정에서 더 짧은 경로를 찾으면 더 짧은 경로로 값을 갱신 다익스트라 알고리즘특정한 노드에서 출발해서 다른 모든 노드로 가는 최단 경로 계산다익스트라 알고리즘은 음의 간선이 없을 때 정상적으로 동작- 현실 세계의 간선은 음의 간선으로 표현X- 음의 간선이 포함될 때는 .. 2026. 4. 5.

그래프 탐색 알고리즘, BFS(Breadth First Search) BFS(너비 우선 탐색)그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법완전 탐색을 수행하기 위해 사용할 수 있는 방법 중 하나(모든 간선의 길이가 동일할 때) 최단 거리를 탐색하기 위한 목적으로 사용 가능탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미대표적인 그래프 탐색 알고리즘 중 하나큐 자료 구조 이용(DFS-스택, BFS-큐) 큐 구현class Queue { constructor() { this.queue = {}; this.headIndex = 0; this.tailIndex = 0; } enqueue = (value) => { this.queue[this.tailIndex++] = val.. 2026. 4. 4.

그래프 탐색 알고리즘, DFS(Depth-First Search) DFS(깊이 우선 탐색)특정 방향으로 최대한 깊이 들어가서 빠져나오는 방식DFS는 스택 자료구조 사용스택(Stack): 먼저 들어온 데이터가 나중에 나가는 형식 → FILODFS는 2차원 배열(리스트)로 그래프 표현그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법으로, 완전탐색 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나인접 리스트 표현 방식0 12, 321, 531, 4, 543, 552, 3, 4 기본 동작 방식시작 노드를 스택에 넣고 [방문 처리]스택에 마지막으로 들어온 노드에 방문하지 않은 인접 노드가 있는지 확인• 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 [방문 처리]• 없다면, 현재 노드(스택에 마지막으로 들어온 노드)를 스택에서 추출2번 과정을 .. 2026. 4. 4.

백트래킹 모든 경우의 수 고려할 때 사용일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용DFS와의 차이점DFS는 일반적으로 완전 탐색 목적으로, 재귀 함수를 이용해 구현백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 단순히 완전 탐색하는 것이 아니라 조건에 따라 유망한 노드로 이동그래프 표현 방식(2가지)1. 인접행렬0100101101010110 2. 인접리스트0 1221, 3, 432, 442, 3 백트래킹 기본 형태function recursive() { if 종료 조건을 만족한다면 { 처리; } for 자식 노드를 하나씩 확인하며 { if 임의의 조건을 만족한다면 { 자식 노드 방문 처리; 재귀 함수 호출; .. 2026. 4. 4.

이전 1 ··· 17 18 19 20 21 22 23 ··· 32 다음

티스토리툴바