알고리즘 공부3 A* 알고리즘 A* 알고리즘은 컴퓨터 게임뿐만 아니라 자동차 네비게이션 자연어 파싱 등에도 사용된다. A*알고리즘의 수식은 다음과 같다. f (n) = g(n) + h(n) 최종값 = 경로값 + 휴리스틱 예측값 휴리스틱 예측값 - 현위치에서 목적지까지의 최단 거리로 설정 - 상황에 따라 다른 함수로 만들어서 사용해도 무관하다. -> 다양한 상황에서 사용 가능. 최단 경로를 나타내는 다익스트라 알고리즘의 식은 다음과 같다. f(n) = g(n) 즉 A*는 다익스트라 알고리즘에서 h(n) (휴리스틱 예측값)이라는 값을 더해서 사용하는 것이다. 그래프 예시입니다. A* 알고리즘 순서를 나타내보겠습니다. A부터 B까지 A*값 = 5.5 , C까지 A*값 = 6.5 -> B가 더 작으므로 B에서 진행 B와 이어져있는 D까지 A.. 2024. 3. 10. 퀵소트 VS 머지소트 C++의 헤더에 있는 sort와 stable_sort를 공부를 하다가 sort의 내부적인 sort인 '퀵소트' vs stable_sort의 내부적인 sort인 '머지소트' 가 궁금해져서 이렇게 알고리즘에 대해 살짝 공부를 해보기로 했습니다. https://penpen.tistory.com/entry/Algorithm-Quick-Sort-Merge-Sort-%EB%B9%84%EA%B5%90%EC%B2%B4%ED%97%98 [Algorithm] Quick Sort, Merge Sort 비교체험 ! 이전글에 계속하여.. Quick Sort vs Merge Sort 알고리즘 수업시간에 귀가 따갑도록 들었던 이 두 정렬방법. 당연히 퀵이 빠른거 아니야? 했지만, 누군가는 데이터가 커질수록 Merge가 좋다하고.... 2021. 7. 7. merge sort - 병합 정렬 정리 이번에 알고리즘 공부를 하며 알게 된 merge sort에 대해서 정리를 해보겠습니다. 이 sort를 이해하기 위해서는 기본적으로 재귀함수에 대해서 알고 계셔야합니다. 재귀함수란 함수 자신이 자신을 다시 부르는 함수를 의미합니다. 그리고 재귀함수 내에서 정해진 return에 알맞은 조건을 만족하게 되면 return을 하여 값을 도출하는 형태입니다. 글로만 설명하니 너무 어려운것 같아서 재귀함수부터 간단히 그림으로 설명드리겠습니다. 이처럼 자신의 복사본을 불러서 계산을 하고 return되는 조건에 알맞으면 return이 되는 형식을 재귀함수라고 부른다. 검은 글자가 자신의 복사본을 늘려가는 과정이고 붉은 글씨가 int값이 정해져서 return되고 있는 상황입니다. 처음으로 이렇게 그림을 그려서 설명을 해봤.. 2021. 2. 7. 이전 1 다음
