퀵 정렬 퀵 정렬... 말 그대로 가장 빠른 정렬 알고리즘입니다. 바로 알아봅시다. 1. 퀵 정렬 동작 과정 퀵 정렬 함수 코드 def quick_sort(lst): def sort(low, high): if high
알고리즘/python
문자열 게임 1. 문제 설명 문제는 간단합니다. W(지워야 하는) 문자열이 주어지고 그 대상 S 문자열이 주어집니다. 그다음 N의 숫자가 주어지며 밑으로 N 개의 줄에는 명령어가 주어집니다. 명령어 L 은 왼쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다. 명령어 R 은 오른쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다. 최종적으로 모든 명령을 수행했을 때 문자열 S에 남은 문자열 W 가 있다면 게임에서 패배하게 됩니다. 출력은 순서대로 성공한 명령어의 수, 남은 문자열 S, 승패 문구입니다. 승리한 경우 Perfect!, 패배한 경우 You lose! 를 출력합니다. 2. 접근과 풀이 이 문제는 결론부터 말하자면 입니다. 그럼 스택으로 접근해 봅시다! aaaaabbbb라는 문자열 S..
다익스트라 1. 최단경로 알고리즘 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘. 플로이드-워셜(Floyd-Warshall) 다익스트라(Dijkstra) 벨만-포드(Bellman-Ford) 노드의 개수가 적을 경우 플로이드-워셜을 사용하는 것이 효율적입니다. 노드와 간선의 개수가 모두 많을 때 다익스트라를 사용하는 것이 효율적입니다. 오늘은 다익스트라를 배워봅시다. 2. 특징 순환 포함 허용 간선에서 음의 가중치를 허용 않음(거리 또는 비용) 기본적으로, 탐욕 알고리즘에 속함 매번 가장 비용이 적은 노드를 선택하려고 함 3. 동작 최단거리 테이블을 최댓값으로 초기화시켜 줍니다. (INF) 출발노드와 도착노드를 설정합니다. 1번 노드가 Start 노드 , 6번 노드가 End 노드입니다. ..
