코딩하는 털보

합병 정렬은 분할 정복 알고리즘을 이용한 정렬 방법이다. 분할 정복은 큰 문제를 작은 문제로 쪼개어 작은 단위의 문제를 먼저 해결하면서 병합시켜 마지막으로 가장 큰 문제를 해결하는 문제 풀이 방법이다. 합병 정렬의 과정은 크게 배열을 분할하는 부분과 분할된 배열을 다시 합병하는 부분으로 나뉘어 진다. 분할에서는 배열을 두 개의 배열로 분할한다. 합병에서는 두 배열을 정렬을 하면서 합친다. 시간복잡도는 분할에서 log2(N), 합병에서 N으로 분할이되는 만큼 다시 합병하기 때문에 둘을 곱하여 N*log2(N)이 된다. 성능이 선택, 버블, 삽입 정렬과 비교하여 효율적이고 안정적이기 때문에 자주 사용되는 정렬 방법 중 하나이다. Java의 Arrays.sort() 및 Python sorted() 또한 합병 ..

버블 정렬은 배열에서 차례대로 두 개의 붙어있는 인덱스를 비교하여 더 큰 값을 뒤로 보내는 정렬 방법이다. 가장 큰 값이 먼저 맨 뒤로 보내지고 그 다음 뒤에서부터 순차적으로 정렬이 완성된다. n = array length 처음엔 인덱스 0부터 n-2까지 그다음 인덱스와 비교하면서 다음 인덱스가 크면 서로 교환 위 절차를 0~n-3, 0~n-4, 0~n-5, ... 0~0으로 총 n-1번 순회 i : 0~n-2 j : 0~n-2-i 최선의 경우, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 성능이 좋지 못하여 구현이 쉽다는 장점 말고는 다른 정렬 방법과 비교했을 때 좋은 정렬 방법이 아님.

배열이나 리스트의 원소를 하나씩 비교하면서 알맞은 위치에 삽입하여 정렬하는 방법 쉽게 생각하면 배열 앞부분부터 정렬을 시작하고 모든 배열이 정렬될 때 까지 하나씩 정렬 영역에 알맞는 위치에 삽입하는 정렬 방법이다. 선택 정렬과 마찬가지로 O(n^2)의 비효율적인 시간 복잡도를 가지게 된다. 정렬을 하는 방법인데 정렬이 안되어있을수록 성능이 떨어지게 된다. 정렬이 어느정도 잘 되어있다는 보장이 있다면 좋을 수 있지만 그렇지 않다면 다른 정렬 방법이 선호된다.

선택 정렬은 배열의 부분 배열에서 최소값(또는 최대값)을 찾아 부분 배열의 시작 인덱스와 값을 교환하는 정렬 방법이다. 선택 정렬 알고리즘의 구체적인 과정은 다음과 같다. 배열의 첫 번째 원소를 선택 이후 원소들 중에서 최소값 검색 최소값을 찾았다면, 해당 최소값을 현재 선택한 원소와 교환 배열의 다음 원소를 선택하여 위 과정을 반복 모든 원소에 대해 위 과정을 반복하여 정렬을 완료 코드만 봐도 알수 있듯이 이 정렬법의 시간 복잡도는 O(n^2)이다. 배열의 크기가 클수록 성능이 좋지 못하므로 일반적으로는 이보다 더 효율적인 정렬 알고리즘을 사용하게 된다.

문제 자연수 N(N)과 정수 K(K)가 주어졌을 때 이항 계수 (NK)(\binom{N}{K})를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(N)과 K(K)가 주어진다. (1 ≤ N(N) ≤ 10, 0 ≤ K(K) ≤ N(N)) 출력 (NK)(\binom{N}{K})를 출력한다. 풀이 이항 계수가 무엇이고 어떻게 계산하는지만 알면 쉽게 풀 수 있는 문제이다. import sys n, k = map(int, sys.stdin.readline().rstrip().split()) a = 1 b = 1 while k > 0: a = a * n b = b * k n = n - 1 k = k - 1 print(a//b)

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 풀이 동적 계획법 N

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 풀이 브루트 포스, 모든 경우의 수를 확인한다. import sys n = int(sys.s..

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..

문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 풀이 친절하게도 모든 약수를 준다. 그냥 최댓값에서 최솟값을 곱하면 양수 N을 구할 수 있다. import sys size = int(sys.stdin.readline().rstrip()) num_list = list(map(..