[Algorithm] 정렬: 계수 정렬, 선택 문제
+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 계수 정렬 (counting sort) - 범위가 작은 수들을 빠르게 정렬할 때 사용된다. 1. 각 수가 나온 횟수를 센다. (자신보다 작은 원소의 개수를 센다.) 2. 1 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다. (누적합 이용) ex) {5, 9, 3, 6, 9, 5, 2, 10, 1} 1. 하나의 숫자를 찾아갈 수 있는 시간을 Θ(1)이라고 가정할 때, 각 숫자가 나온 횟수를 세는데 Θ(n) 2. 다시 숫자를 정렬된 리스트에 채워넣는데 Θ(n) => Θ(n) ex) {12387, 90123, 39735, 9012344} - (최대값 - 최소값)의 범위 수..
[백준/Python] 9095번: 1, 2, 3 더하기
문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 요약 정수 n을 입력 받고, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. (1 ≤ n ≤ 10) ex) 정수 4를 1, 2, 3의 합으로 나타내는 방법 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 2 1 + 3 3 + 1 코드 T = int(input()) dp =[0] * (11) # dp[i]는 정수 i까지 1, 2, 3으로 나타낼 수 있는 방법의 수 dp[1] = 1 # 1 dp[2] = 2 # 1 + 1, 2 dp[3] ..
