[Algorithm] A* 알고리즘 : 최단 경로 탐색

✍️ 인트로 A* 알고리즘은 그래프의 탐색 알고리즘으로 주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다. 대표적인 그래프 탐색 알고리즘들과 A*의 차이점은 BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며 다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다. 반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다. [※ 정리 ※] BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘 A* : 가중치 그래프, 시작..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 3.
• textsms

[Algorithm] 다익스트라 알고리즘 : 최단 경로 탐색(1) - 배열

인트로 다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 BFS가 가중치 없는 그래프의 최단경로를 찾는 알고리즘이라면 다익스트라 알고리즘은 가중치가 있는 그래프의 최단경로를 구할 때 사용된다. 참고로 다익스트라 길 찾기 알고리즘은 DFS, BFS와 마찬가지로 완전 탐색 알고리즘에 속한다. 다익스트라(Dijkstra) 이해하기 1) 아래와 같은 가중치 그래프가 있다. 0번 정점에서 시작해 5번 정점까지의 최단거리를 구해보자. 최단거리를 저장할 배열(DIST)이 다음과 같은 형태로 있다. DIST[ ∞, ∞, ∞, ∞, ∞, ∞ ] (+ 아직 최단거리를 모르니 모두 ∞로 초기화한다.) 2) 시작 정점인 "0"번 정점을 방문한다. 시작 정점인 "0"번 정점은 최단거리가 "0"이므로 DIST[ 0, ∞, ∞, ∞..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 31.
• textsms

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : SideWinder 미로(3)

인트로 C# 콘솔 프로그래밍으로 미로를 만들고 BFS, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다. Part1에선 2차원 미로를 만들어보려 한다. (+ Visual Studio 기준으로 포스팅을 이어나갈 예정입니다.) [C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(1) [C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(2) [C#] 미로 만들기와 길찾기 알고리즘 Part 2 : Player 만들기 [C#] 미로 만들기와 길 찾기 알고리즘 Part 3 : BFS 길 찾기 SideWinder 미로 생성 알고리즘 미로를 만드는 것은 의외로 간단한데 Empty 지역의 동서남북을 Wall로 채우는 것부터 시작한다. Board 클래스의 InitializeB..

• format_list_bulleted C#
• · 2021. 8. 30.
• textsms

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(2)

인트로 C# 콘솔 프로그래밍으로 미로를 만들고 BFS, 다익스트라, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다. Part1에선 2차원 미로를 만들어보려 한다. (+ Visual Studio 기준으로 포스팅을 이어나갈 예정입니다.) [C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(1) [C#] 미로 만들기와 길찾기 알고리즘 Part 1 : SideWinder 미로(3) [C#] 미로 만들기와 길찾기 알고리즘 Part 2 : Player 만들기 [C#] 미로 만들기와 길 찾기 알고리즘 Part 3 : BFS 길 찾기 Board를 2차원 배열로 관리하기 이전 포스팅에선 미로 맵을 데이터로 관리하지 않고 그저 이중 for문을 돌며 출력만 했다. 하지만 갈 수 있는 곳과 그..

• format_list_bulleted C#
• · 2021. 8. 29.
• textsms

[Algorithm] 50. 영지(territory) 선택

인트로 피보나치 수열로 동적 프로그래밍을 이해했다면 그다음 단계로 풀어볼 적당한 문제인 것 같다. 영지(territory)선택 문제 세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 25.
• textsms

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)

인트로 +컴퓨터공학을 전공하셨거나 코딩 테스트를 준비하시는 분들은 한 번쯤 접해보셨을 동적 프로그램(DP, 동적 계획법)을 쉽게 이해하기 위해 작성한 글입니다. ★ 동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. 이렇게 보면 동적 프로그래밍은 분할 정복이 동일하다고 생각할 수 있지만 해를 구하기 위해 쪼갠 "부분 문제"의 특성이 다르다. 분할 정복과 비교했을 때 동적 프로그래밍의 도드라지는 특성은 작게 쪼개진 "부분 문제"가 중복돼서 나타난다는 것이다. 이에 대해선 차차 알아보기로 하고 알기 쉽게 동적 프로그래밍을 이해해 보자. 동적 프로그래밍 (DP, 동적 계획법) 피보나치 수열을 예로 들어 동적 프로그래밍을 설명하..

• format_list_bulleted Algorithm/동적 프로그래밍(DP)
• · 2021. 8. 25.
• textsms