백준 - 단계별로 풀어보기

1. 문제 상세 https://www.acmicpc.net/problem/1427 2. 문제 접근 정수를 입력받고 각 자리수를 구하여 배열에 저장한다. 이 자리수들을 내림차순으로 정렬하여 출력하자. 입력받는 수는 최대 1,000,000,000 이다. 따라서 정렬 해야 할 수의 최대 갯수는 10개이다. 정렬 할 수의 개수가 적어서 여러 정렬 알고리즘을 사용할 수 있다. 좀 더 효율 알고리즘인 퀵 정렬 알고리즘을 사용해보자. ■ 퀵 정렬 퀵 정렬 알고리즘은 합병 정렬(merge sort)과 비슷하게 분할 정복 정렬 알고리즘이다. 하지만 합병 정렬과는 다르게 배열을 비균등하게 분할한다는 차이점이 있다. 분할 과정에서는 배열을 임의의 피벗 값을 기준으로 피벗보다 작은 쪽(왼쪽) 과 큰 쪽(오른쪽), 총 2개의 ..

1. 문제 상세 https://www.acmicpc.net/problem/10989 2. 문제 접근 이번 문제에서는 조건으로 수의 갯수와 수가 자연수이고 수의 최대값이 주어졌다. 최대값이 10000인데, 이런 경우 원소들을 비교하며 정렬하는 방식이 아닌 카운팅 정렬(계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다. 계수 정렬 알고리즘에 대해 정리한 글 https://dry-programming.tistory.com/111 계수 정렬 (Counting sort) 주어진 수들을 정렬해야 하는 경우, 수들이 모두 양수이고, 최대값이 정해져 있다면. 카운팅 정렬 (계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다. ■ 계수 정렬? 계수 정렬 알고리즘은 비교를 하 dry-programming.tistory.com 위의..

1. 문제 상세 https://www.acmicpc.net/problem/2751 2. 문제 접근 주어진 수들을 정렬하기 위해 합병 정렬 알고리즘을 사용해보자. 이번 문제에서 유의할 점은 시간 제한이다. 이번 문제에서 정렬 할 수들의 최대 갯수는 1,000,000개이다. 즉 시간복잡도가 O(N2)인 정렬 알고리즘을 사용한다면 제한시간을 초과하게 된다. 지금까지 알아본 버블, 선택, 삽입 정렬은 시간복잡도가 O(N2)이기 때문에 사용할 수 없다. 퀵 정렬을 사용해볼까 싶었지만 퀵 정렬에서도 최악의 경우에는 시간복잡도가 O(N2)이기 때문에 이번에는 합병 정렬을 사용해보자. ■ 합병 정렬 합병 정렬 알고리즘은 주어진 원소들을 분할, 정복, 결합 과정을 통해 정렬해가는 알고리즘이다. 분할 과정에서는 배열을 중..

1. 문제 상세 https://www.acmicpc.net/problem/25305 2. 문제 접근 점수들을 입력받고 점수를 내림차순으로 정렬 후 k 번째 점수를 출력하자. 이번에는 정렬 알고리즘에 삽입 정렬을 사용해보자. ■ 삽입 정렬 삽입 정렬 알고리즘은 원소를 앞쪽의 정렬된 배열의 원소들과 비교하여 맞는 위치를 찾아 삽입하여 정렬해가는 알고리즘이다. 정렬의 크기가 N 이라고 할 때, 오름차순 정렬을 해보자. 2번째 원소부터 시작해 현재 원소의 왼쪽 원소들과 비교하여 원소를 맞는 위치에 삽입하며 정렬해간다. 두 번째 원소를 앞(왼쪽)의 원소인 첫 번째 원소와 비교하고, 작다면 첫 번째 원소를뒤로 밀고 첫 번째 자리에 현재 원소를 놓고, 아니면 현재 자리에 둔다. 첫 과정이 끝나면 세 번째 원소와 두 ..

1. 문제 상세 https://www.acmicpc.net/problem/2587 2. 문제 접근 다섯 개의 숫자를 입력받고, 수들의 평균을 출력하고, 정렬 후 중앙값인 3번째 값을 출력하자. 이번에는 정렬 알고리즘에 선택 정렬을 사용해보자. ■ 선택 정렬 선택 정렬 알고리즘은 최솟값을 찾고 그 값을 맨 앞부터 넣어서 순차적으로 정렬해가는 알고리즘이다. 배열의 크기가 N 이라고 해보자. 선택 정렬은 첫 번째 원소부터 두 번째, 세 번째, ... N 번째 원소까지 비교 후 최솟값을 찾아 그 값을 맨 앞으로 가져온다. 첫 과정이 끝나면 두 번째 원소와 세 번째, 네 번째, ... N 번째 원소까지 비교 후 최솟값을 두 번째 위치로 가져온다. 이 정렬을 계속 수행하면 마지막 값은 자동으로 정렬되기 때문에 N ..

1. 문제 상세 https://www.acmicpc.net/problem/2750 2. 문제 접근 주어진 수들을 정렬하기 위해 버블 정렬 알고리즘을 사용해보자. ■ 버블 정렬 버블 정렬 알고리즘은 인접한 원소를 비교하여 순서를 정렬해가는 정렬 알고리즘이다. 버블 정렬은 인접한 두 값을 비교하여 큰 값을 뒤로 보낸다. 정렬의 크기가 N 이라고 해보자. 첫 번째 원소와 두 번째 원소를 비교하고, 두 번째 원소와 세 번째 원소, 이 순서대로 N - 1번 원소와 N 번 원소까지 비교한다. 이 과정을 한 번 마치고 나면 제일 큰 원소가 맨 뒤로 가게 된다. 따라서 두 번째 과정에서는 맨 마지막 원소를 제외하고 값을 비교해가고, 이 과정을 총 N - 1 번 반복한다. 아래는 버블 정렬의 예시이다. 버블 정렬의 시간..