파이썬 알고리즘 (20) 썸네일형 리스트형 합병 정렬 합병 정렬 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 가장 작은 부분 문제로 계속 쪼갠 뒤 가장 작게 쪼개진 부분문제들을 점차 합병하면서 최종적으로 큰 문제를 해결하는 알고리즘 1. 가장 작은 부분이 될 때까지 반으로 계속 분할 2. 가장 작은 부분들 2개씩부터 합병하면서 최종적으로 정렬된 하나가 됨 import random # 가장 작은 조각이 될 때까지 계속 분할 + 가장 작은 부분이 되면 거기서부터 점차 합병 def merge_sort(A): if len(A) > 1: mid = len(A) // 2 left = A[:mid] # 0부터 mid-1까지 right = A[mid:] # mid부터 끝까지 # 가장 작은 조각이 될 때까지 계속 분할(가장.. 퀵 정렬 (재귀X) 흔히 퀵 정렬에서는 왼쪽에서 오른쪽으로 가면서 피벗값보다 큰 값을, 오른쪽에서 왼쪽으로 가면서 피벗값보다 작은 값을 찾아 서로 바꾸면서 정렬을 진행함 오늘 할 건 재귀를 사용하지 않고 퀵 정렬을 구현하되 왼쪽에서 오른쪽으로만 이동하면서 정렬을 하고자 함 검색해야 하는 위치 정보를 [p, q]로 스택에 넣고 스택이 비워질 때까지 반복문 수행 8 3 11 9 12 2 6 15 18 10 7 14 가장 처음 스택에는 전체 범위 저장(0~11) i = 피벗 인덱스(검색해야 하는 배열의 가장 앞) j = 피벗 제외 배열을 이동하는 인덱스 j가 왼쪽에서 오른쪽으로 이동하면서 피벗보다 작은 값을 만나면 i를 1 증가시킨 후 그 자리의 값과 작은 값의 위치를 서로 바꿈 현재 i=0 j는 피벗(8) 옆부터 작은 값을 찾.. TypeError: 'list' object is not callable range는 파이썬에서 쓰는 기본적인 함수 이름인데 내가 range라는 변수를 만들어서 거기에 값을 저장하고 출력하려 해서 - object is not callable이라는 에러가 떴다. 파이썬에서 [원래 있던 함수]와 [내가 만든 변수]의 이름이 중복되어 어떤 것을 불러올지 몰라 나타나는 에러 함수 실행 코드가 잘못된 줄 알고 손으로 하나하나 실행과정을 다 따져봤는데도 이상이 없는데 자꾸 저런 에러가 떠서 검색해 보니 파이썬에서는 자주 나타나는 에러임을 알았다. 변수명을 range에서 findRange로 수정하니까 제대로 동작 하노이탑 (재귀X) 하노이탑 재귀이용하지 않고 풀어보기 하노이탑 플레이 Play Tower of Hanoi www.mathsisfun.com 원리 사용자로부터 원반의 개수(n), 출발기둥이름(fr), 보조기둥이름(tmp), 목적기둥이름(to)을 입력받음 기둥 세 개는 각각 A, B, C 리스트로 구현 출력할 때 원반이 어디서 어디로 이동했는지 확인하고 싶어 기둥의 이름들을 리스트의 0번째에 저장 원반의 개수를 입력하면 A라는 리스트에 n부터 1까지 차례대로 추가 (수가 클수록 큰 원반) 출발지(fr)의 원반이 모두 목적지(to)로 옮겨가면 루프 종료. 즉, 목적기둥의 원반 수가 입력받은 원반의 개수보다 작을 경우 while문 반복 (목적기둥리스트의 0번째에 기둥이름을 저장했으므로 요소 총 개수 -1 = 목적기둥에 있는 원반.. 이전 1 2 3 다음
