알고리즘 (3) 썸네일형 리스트형 합승 택시 요금 문제 설명S의 시작점에서 A의 도착점 과 B의 도착점의 최단경로를 구하는문제 문제 풀이해당 문제는 최단 경로를 찾는 문제이기 때문에 다익스트라 알고리즘으로 풀 수 있다.다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.이 과정에서 도착 정점 뿐아니라 모든 정점까지 최단경로로 방문하며 각 정점까지의 최단경로를 찾게된다.최소비용을 구하는 그래프 알고리즘다익스트라 알고리즘벨만-포드 알고리즘프로이드 워샬 알고리즘 동작 단계출발 노드와 도착노드를 설정최단거리 테이블 초기화현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택 후 방문처리해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 .. 하노이의 탑 하노이의 탑 알고리즘 문제는 재귀적으로 해결되는 대표적인 문제이다. 하노이의 탑 규칙한번에 한 개의 원판만 이동 가능더 작은 원판 위에 더큰 원판을 놓을 수 없다 하노이의 탑이 재귀적으로 해결되는 이유N개의 원판을 옮기기 위해서는 N-1개 원판을 옮기는 문제를 해결해야함.N개의 원판을 A -> C로 옮기는 과정(재귀 호출) N-1 개의 원판을 A -> B로 이동(직접 호출) N의 원판을 A -> C로 이동(재귀 호출) N-1개의 원판을 B -> C로 이동 N = 3일 경우 원판을 옮기는 과정원판 1: A → C원판 2: A → B원판 1: C → B원판 3: A → C원판 1: B → A원판 2: B → C원판 1: A → C def hanoi(n,start,to,via,move_list): if n =.. 길 찾기 게임 BTS (binary tree search) 를 구현하는 문제입니다.BTS의 insert, 전위 순회, 후위 순회를 구현하는 문제입니다.각 노드의 번호를 알기위해 enumerate를 사용하고y축으로 각 노드를 정렬한다.def solution(nodeInfo) : sorted_node_info = [] # 트리의 노드를 높이 순으로 정렬하기 위해서 for idx,[x,y] in enumerate(nodeInfo,1): # 정렬과 함께 현재 노드의 번호를 확인하기 위해 sorted_node_info.append([idx,x,y]) # 노드 번호에 따라 값 저장 sorted_node_info.sort(ke.. 이전 1 다음
