포시코딩

문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 난이도 보고 덤볐다가 백준의 매운맛을 3일동안 제대로 맛 본 문제 시간, 메모리 제한 쪽으로 너무 깐깐해서 두손 두발 다 들었다. 그 덕분에 버블, 삽입, 선택, 퀵, 병합 정렬만 알던 내가 계수 정렬 까지 알게 됐으니 고마운 문제기도 하다. 내 풀이 N = int(input()) arr = [] for _ in range(N): arr.append(int(input())) count = [0] * (max(..

병합 정렬(Merge Sort) 분할 정복 알고리즘의 기법을 사용하는 정렬 알고리즘 중 하나 (분할 정복 알고리즘의 대표적인 예 중 하나기도 하다.) 데이터를 잘게 쪼개 정렬한다. Memoization을 사용하지 않음 재귀 용법을 활용 사용방법 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 구현 재귀 용법으로 데이터를 나누는 함수, 나눠진 데이터를 병합하는 함수 두 단계를 함수로 만들어 사용 def merge_sort(data): return split(data) def split(data): if len(data) lp and len(right) > rp: if left..

퀵 정렬(Quick Sort) 정렬 알고리즘의 꽃 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해 다시 동일 함수를 호출하여 위 작업을 반복 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴한다. 배우기 앞서 기대한 알고리즘 중 하나 파이썬에서 구현 시 아름다울 정도라는데 얼마나 감동할 수 있을지 기대를 잔뜩 하고 들어갔던 것 같다. 크게는 아래 순서를 따라간다. pivot은 보통 제일 앞에걸로 지정 pivot을 기준으로 분류 분리된 left, right를 재귀 함수를 통해 1~2 반복 그렇게 데이터 수가 1개가 될 때 까지 반복한다. 구현 def qsort(l..

삽입 정렬 선택 정렬이 전체에서 최솟값을 '선택'하는 정렬이었다면 삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식이다. 버블 정렬과 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿨지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이라고 할 수 있다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 이런식으로 비교할 인덱스가 어떤식으로 전개될지 쭉 써보고 그 중에 i 값은 뭐가 될지 그에 따른 j 값은 뭐가 되고 어떻게 구해야할지 생각해보면 for문을 어떻게 짤지 대충 감이 온다. arr = [4, 6, 2, 9, 1] # 1 2 1 3 2 1 4 3 2 1 def insertion_sort(arr): n = len(arr) for..

선택 정렬 선택 정렬은 처음부터 끝까지 하나씩 확인하며 제일 작은 값을 찾아 맨 앞으로 보낸 후 다시 두번째부터 끝까지 하나씩 확인하며 이번에 제일 작은 값을 두번째로 보내는 과정을 반복하는 정렬이다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 arr = [4, 6, 2, 9, 1] # 0 1 2 3 4 1 2 3 4 2 3 4 3 4 def selection_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-i): print(i+j) selection_sort(arr) 버블 정렬과 다른점은 '최솟값'을 찾아 변경한다는 부분이다. 인덱스를 하나씩 돌며 제일 작은 값을 찾아 인덱스만 따로 min_i 변수에 저장한 뒤..

정렬이란? 데이터를 순서대로 나열하는 방법을 의미. 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게도 한다. 버블 정렬 버블 정렬은 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, ... 이런식으로 (n - 1) 번째 자료와 n 번째 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다. ex) 첫 루프에서 두 개씩 비교해서 끝까지 가면 제일 큰 수가 마지막에 위치하게 된다. 이제 마지막 수는 고려하지 않아도 되므로 제외하고 다시 처음부터 마지막-1 번째까지 두 개씩 비교하고 다시 마지막-1 번째도 제외하고.. 를 반복해서 정렬시키는 방식이다. 코드로 구현해보자 input = [4, 6, 2, 9, 1] 위와 같은 숫자로 이루어진 배열이 있을 때 버블 정렬을 통해..