Manta Ray's

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 : ① DFS를 이용핸 도달할 수 있는 모든 경로를 탐색. ② 탐색 한 경로의 최소값을 출력 2021.09.19 - [알고리즘/알고리즘] - 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 ..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 : BFS를 이용해 지점을 잇는 경로를 탐색 ① 지점을 잇는 경로를 탐색한다. ② ①에서 탐색되지 않은 지점를 시작으로 재탐색한다. * computer[i][i] 가 1이므로, 어느 지점과 연결되지 않으면 자기자신하고만 연결되는 경로 (네트워크) 1개가 세어진다. 2021.09.19 - [알고리즘/알고리즘] - 너비 우선 탐색 Breath-f..

플로이드-와샬 알고리즘 모든 정점 사이의 최단 거리를 찾는 알고리즘. 그래프를 인접행렬로 표현한다. 정점마다 경로 가중치를 기록한 인접행렬을 탐색하여 최단경로를 찾는 방식이다. 슈도코드 ① 인접행렬 A 생성 ② for ( k to 정점갯수) { for ( i to 정점갯수) { for ( j to 정점갯수) { //현재 경로 값과 정점 K를 거쳐가는 경로 값을 비교하여 더 작은 값을 저장 if (A ( i , j ) > A ( i , k ) + A( k , j ) ) { A ( i , j ) = A ( i , k ) + A( k , j ); } } } } 시간복잡도 ① 정점 K를 거쳐가는 경로를 탐색 ② ①을 수행할 때마다 경로 가중치를 기록한 인접행렬 V²을 탐색 O(V³) 구현 JAVA package..

벨만-포드 알고리즘 음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘. 벨만-포드 알고리즘에서 최단 경로는 출발점으로부터 도달가능하며 음의 값을 가지는 순환이 없는 경우를 의미함. 그래프에 있는 모든 정점을 한번씩 탐색함. 슈도코드 BELLMANFORD(그래프, 가중치, 시작점) 시작점 초기화 최단경로의 비용을 MAX으로 초기화 ① 모든 경우의 수 for ( 그래프의 모든 정점을 탐색) { for ( 그래프의 모든 엣지를 탐색){ if( U를 거쳐서 V로 가는 비용 < 현재 V의 최단 비용 ){ V로 가는 비용

깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 탐색한 후 다음 하위 노드를 탐색하는 방법 일단 경로 하나의 모든 층을 탐색한 후 그 다음 경로의 모든 층을 탐색하는 방법 재귀나 스택을 이용해 구현 백트래킹 문제의 해답을 찾지 못했을 때 이전 단계로 돌아가는 것 자식노드에서 값을 찾지 못했을 때 부모노드로 돌아가는 것 슈도코드 DFS(그래프, 시작 정점) { 시작점 방문여부 = true for ( 시작점과 연결된 정점 탐색 ){ if (탐색 정점의 방문여부 == false){ 탐색 정점의 방문여부 = true DFS(그래프, 탐색 정점) //재귀 } } } 시간복잡도 초기화 시간 : Ο(노드갯수) 그래프 탐색 시간 : Ο(노드갯수 + 간선갯수) 정점은 최대 1번 탐색한다. 간선은 최대 2..

너비 우선 탐색 시작점에서 도달 가능한 모든 간선을 탐색하여 찾는 과정 탐색을 하면서 시작점으로부터 거리를 계산한다. 탐색을 하면서 직전 정점의 위치를 저장한다. (거쳐온 정점을 기록한다.) 탐색을 하면서 정점의 상태를 변환한다. 초기화 : not discovered = white 발견한 정점 : discovered = gray 완료된(방문한) 정점 : finished = black 슈도코드 1. 주어진 모든 Graph를 초기화 * 정점의 상태 : 초기화(white) * 시작점으로부터의 거리 : ∞ * 바로 직전의 정점 : 초기화(NULL) 2. 시작 위치 저장 * 시작 정점의 상태 : 발견(gray) * 시작점으로부터의 거리 : 0 * 바로 직전의 정점 : NULL * Queue에 방문한 경로에 현재위..