백준 문제는 아니지만 이번에 과제로 퀵소트 구현하고 python의 메서드와 비교하라는 문제가 있어 간단히 정리해봅니다. 퀵소트는 기준이 되는 pivot 값보다 크고, 작음을 이용해 분리해주고, pivot을 제 위치에 넣습니다. 그리고 pivot보다 작은 애들에 대해 똑같이 정렬해주고, 큰 애들에 대해 똑같이 정렬해줍니다. (이번에 하면서 머지소트를 폰 노이만이 만든 것을 알게되었다. 일반적으로 퀵소트가 더 빠르지만 최악의 상황이 발생하지 않는 머지소트. 역시 갓 노이만) 코드는 다음과 같습니다. (과제가 csv 파일 불러와서 시간, 메모리 측정하고, 정렬하는 거라 함수만 보면 됩니다.) # 랜덤한 리스트 (100만개 원소) 오름차순 (ex. 1 2 3 4 5) 정렬 퀵소트 import time # 시간 ..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 자기 전에 간단한 문제를 풀어보았습니다. 애들을 줄 세우는데 최소 몇 번 옮겨서 줄을 다시 맞출 수 있는지를 구하는 문제로, LIS 와 동일합니다. 학생들이 3 7 5 2 6 1 4 로 줄을 서 있다면 맨 앞에 학생부터 자기가 최대 몇 번 째 증가 수열의 원소가 될 수 있는지 구하면 됩니다. 3 => 1 7 => 2 5 => 2 2 => 1 6 => 3 1 => 1 4 => 2 이므로 6번 학생이 마지막..
https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net N개의 원판에 M개의 수가 있을 때 규칙에 맞춰 진행 후 최종 남은 수의 합을 구하는 문제입니다. 규칙은 다음과 같습니다. - 회전 방법은 정해져 있다. - 번호가 xi의 배수인 원판을 di 방향으로 ki 칸 회전시킨다. (di : 0, 1 : 시계, 반시계) - 원판에 수가 남아있으면 인접한 모든 수를 지운다. - 지울 수가 없으면 전체 남은 수의 평균을 구해 평균보다 크면 -1..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 자기 전에 간단한 문제를 하나 풀고 자겠습니다. 문제는 주어진 입력이 X1, X2, .., Xn 일 때 Xi 보다 작은 값이 몇 개인지 구하는 문제입니다. 처음 입력에 대해 중복을 제거한 오름차순 정렬 후 해당 값의 index를 구해주면 됩니다. 예제를 예를 들면 입력이 2 4 -10 4 -9 일 때 -10 -9 2 4 로 중복 제거 오름차순 =>..