priority queue2 [C/C++] 프로젝트 오일러 #110 Diophantine Reciprocals II(우선순위큐) 이 문제는 #108 문제와는 아주 비슷합니다. https://sdev.tistory.com/1968 [C/C++] 프로젝트 오일러 #108 Diophantine Reciprocals I(소인수분해)프로젝트 오일러 문제 #108: Diophantine Reciprocals I는 다음과 같은 문제입니다:이 문제는 다음과 같은 형태의 Diophantine 방정식을 다룹니다:1x+1y=1n 여기서 x, y,sdev.tistory.com 요구하는 것도 비슷하지만, 문제 난이도는 #108이 30%로 책정되었지만, 이번 문제는 40%로 책정되어 있습니다. 다음과 같은 형태의 방정식을 고려합니다:\[ \frac{1}{x} + \frac{1}{y} =.. 2024. 12. 2. A* 알고리즘을 위한 우선순위 큐 구현 알고리즘 그래프 이론을 들어가면, 가장 끝판왕은 역시나 A* 알고리즘이라고 생각합니다. A* 알고리즘은 게임 프로그래밍에서도 많이 쓰이는 기법이니, 알아두는 것이 좋지 않을까 하네요. A* 알고리즘을 적용할 때, 방문해야할 노드 수가 많을 때, 속도에 영향을 미치는 부분은 두가지가 있습니다. 첫번째는 가장 작은 에너지 함수값을 갖는 노드를 찾는 것입니다. 두번째는 방문한 셋에 포함되어 있는지 찾는 것입니다. 제 경우에는 작은 에너지 함수값을 갖는 노드를 찾는 것은 힙을 이용한 우선순위 큐를 사용합니다. 힙을 이용하게 되면, 삽입과 삭제의 경우 O(logn)의 점근적 시간이 필요합니다. 선형으로 찾는 것보다 훨씬 빠르게 삽입 삭제를 할 수 있습니다. 방문한 셋에 포함되어있는지 검사하는 방법은 해.. 2014. 12. 8. 이전 1 다음 728x90
