분류 전체보기

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정해당 문제는 가중치가 없는 그래프에서 최단 거리를 구하는 문제이다. 가중치가 없는 그래프에서 최단 거리를 구하기 위해선 너비우선탐색(BFS)를 활용할 수 있다. 과정은 다음과 같다. 1. (0, 0)에서 시작해서 (n-1, m-1)까지의 최단거리를 구해야 한다.2. 거리를 표시할 해당 맵과 똑같은 크기의 배열을 하나 더 만들어서 출발점을 1, 나머지는 0으로 초기화한다. 3. 0,0에서부터 너비우선 탐색을 시작한다. 이때 방문하는 노드의 거리 값은 현재 노드 + 1로 한다.     결과는..

벨만 포드 알고리즘이란?다익스트라 알고리즘과 벨만 포드 알고리즘 모두 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘이다.하지만 벨만포드가 다익스트라에 비해 갖는 특징이 있다.바로 위와 같은 음의 가중치가 있는 그래프에서도 작동한다는 것이다.더불어 음의 사이클도 감지가 가능하다. 음의 사이클이란? 음의 사이클이란 경로의 합이 음수가 되는 사이클을 말한다.위의 사례에 경우 B에서 C를 거쳐 다시 B로 돌아오는 사이클이 존재하는데 이 경우 -3의 비용이 발생한다. 이렇게 되면 최단 거리가 무한대로 줄어들게 된다.벨만포드 알고리즘은 이러한 음의 사이클까지 감지가 가능하다.  다익스트라 벨만 포드음의 가중치 그래프 적용 가능XO음의 사이클 감지 가능XO 정리하자면 벨만포드 알고리즘은 가중치가 있는 그래프에..

다익스트라 알고리즘(Dijkstra Algorithm)이란?다익스트라 알고리즘이란 에츠허르 다익스트라가 제안한 최단 거리 알고리즘이다.다익스트라 알고리즘은 위와 같이 가중치가 존재하는 그래프에서 특정 노드에서 다른 노드까지의 최단경로 및 최단거리(최소비용)를 구할 때 사용된다.  다익스트라 알고리즘 동작 방식다익스트라 동작방식은 다음과 같다. 1. 시작 노드를 정하고 테이블을 초기화한다. 테이블에는 시작 노드에서 각 노드까지의 최소 비용과 직전 노드를 저장한다.      1-1. 시작 노드의 경우 최소 비용을 0, 직전 노드를 자기 자신으로 초기화 한다.     1-2. 나머지 노드의 경우 최소 비용을 무수히 큰 값, 직전 노드를 임의의 더미 값으로 초기화한다.2. 다음을 수행한다.    2-1. 방문하..

그래프의 탐색그래프를 탐색한다는 것은 그래프의 정점들을 탐색한다는 의미이다.이때 정점을 탐색하는 순서가 중요한데 크게 두 가지로 나눌 수 있다. 바로 깊이 우선 탐색과 너비 우선 탐색이다. 깊이 우선 탐색(DFS: Depth First Search)말 그대로 깊이를 우선적으로 탐색한다.한 정점을 기준으로 더 이상 탐색할 정점이 없을 때까지 가보고 없으면 최근에 방문했던 노드로 되돌아가 다음 가지 않은 노드를 방문한다. 너비 우선 탐색(BFS: Breadth First Search)말 그대로 너비를 우선적으로 탐색한다.한 정점을 기준으로 가장 가까운 정점을 모두 방문하고 다음 정점으로 넘어간다.그 정점에서 가장 가까운 정점부터 모두 방문한다. 지금부터 각각에 대해 자세히 알아보도록 하자. 깊이 우선 탐색(..