Coder's Cattitude

5. 파이썬 정렬 라이브러리 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted() 함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다. 병합 정렬은 일반적으로 퀵 정렬보다 느리지만, 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. 이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 물론 집합이나 딕셔너리 자료형을 입력받아도 return 값은 리스트이다. 1) sorted.py array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] result = sorted(array) print(result) - 출력 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 2) sort.py..

2. 삽입 정렬 삽입 정렬은 앞서 했던 선택 정렬에 비해 구현 난이도는 높지만, 실행 시간 측면에서 더 효율적인 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효과적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. 삽입 정렬은 특정한 데이터를 적정한 위치에 삽입한다는 의미에서 삽입 정렬 (Insertion sort)이라고 부른다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 다음, 그 위치에 삽입된다는 점이 특징이다. 아래와 같이 초기 데이터가 ..

정렬 정렬 (sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 이진 탐색 (binary search)의 전처리 과정이기도 하다. 정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 다양한 알고리즘이 존재하고, 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘을 공식처럼 사용해야 한다. 만약 상황에 적절하지 못한 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하고 필요 이상으로 시간을 많이 소요한다. 이제 문제 상황을 가정해 보자. 숫자가 하나씩 적힌 카드가 10장이 있다. 이를 오름 차순으로 정렬해보자. 우리는 보통 카드를 한번 훑고 숫자가 0 ~ 9로 구성된 것을 눈치채고 0에서 9까지 순서대로 나열한다. 이것은 우리도 모르게 데..

🔒 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 🖨 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 📚 예제 Ex1) 3 4 ohhenrie charlie baesangwook obama b..

🔒 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, ..

🔒 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있..

🔒 문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다. merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

🔒 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X&#39;i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X&#39;1, X&#39;2, ..., X&#39;N를 출력해보자. ⌨ 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 🖨 출력 첫째 줄에 X&#39;1, X&#39;2, ..., X&#39;N을 공백 한 칸으로 구분해서 출력한다. 📍 제한 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 📚 예제 Ex1) 5 2 4 -10 4 -9 2 3 0 3 1 Ex2..

🔒 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. ⌨ 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 🖨 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력..

🔒 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 ⌨ 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 🖨 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 📚 예제 Ex1) 13 but i wont hesitate no more no more it cannot wait im yours i im it no but more wait wont yours cannot hesitate..