게으름뱅이의 앞구르기

퀵정렬이란? "빠른" 정렬 알고리즘. 피벗을 기준으로 큰 값과 작은값을 서로 비교하고 교체하는 정렬. 리스트 가운데서 피벗이라고 하는 하나의 원소를 고름 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복하며 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복됨 값을 서로 교체하는데 N번, (엇갈렸을때) 전체 원소 나누는데 평균 logN번이 소요되므로 평균적으로 O(NlogN)의 시간복잡도를 가짐 최악의 경우에는 O(N²)번의 비교를 수행함 퀵정렬은 완전..

선택정렬이란? 제자리 알고리즘의 하나로 제일 작은 값을 "선택"해서 앞으로 보내는 정렬 주어진 리스트 중에 최소값을 찾음 그 값을 맨 앞에 위치한 값과 교체 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체 가장 작은 것을 선택하는데 N번, 앞으로 보내는데 N번의 연산으로 O(N²)의 시간 복잡도를 가짐 가장 작은 수를 앞으로 보내줄 때, 선택된 수가 현재 있는 위치와 맞바꿈 이중포문을 이용해 정렬 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음 참고 | Wikipedia, Fast Campus 컴퓨터 공학 전공 필수

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are. For example, there are n=7 socks with colors ar=[1,2,1,2,1,3,2]. There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The n..