전체 글

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 번 반복한다. 아래는 버블 정렬의 예시이다. 버블 정렬의 시간..

1. 문제 상세 https://www.acmicpc.net/problem/2839 2. 문제 접근 모든 경우의 수를 확인하는 브루트 포스 알고리즘을 사용하여 문제를 해결해보자. 입력받은 무게를 5로 나누었을때 나머지가 0이면 5로 나눈 몫을 무게에서는 빼주고 봉지 수에는 더한다. 위의 경우 봉지 수가 최소 갯수로 계산이 끝난 것이므로 반복을 끝내도록 하자. 입력받은 무게에서 3을 빼고 봉지 수를 하나 추가한다. 나머지가 0이 아니라면 3을 빼고 봉지 수를 하나 추가하는 과정을 반복한다. 반복은 무게가 0보다 작거나 같아질 때 까지 반복하자. 반복이 끝나면 무게가 0보다 작은지 확인, 0이라면 봉지 개수를 출력하고 0보다 작으면 -1을 출력하자. 3. 문제 풀이 #include using namespace..

1. 문제 상세 https://www.acmicpc.net/problem/1436 2. 문제 접근 n 번째로 작은 666이 나오는 숫자를 찾자. 숫자를 666부터 1씩 더해가며 확인하고, 666이 나오는 숫자를 찾으면 카운트, 카운트가 n 과 같아지면 그만두고 그 숫자를 출력하도록 하자. 확인하는 과정에서는 숫자를 1000으로 나눠보고 나머지가 666인지 확인, 아니라면 10으로 나누고 다시 확인하는 과정을 반복하도록 하자. 3. 문제 풀이 #include using namespace std; int main() { int n, count = 0, end = 665; cin >> n; while (count != n) { end++; int temp = end; while (temp != 0) { if ..

1. 문제 상세 https://www.acmicpc.net/problem/1018 2. 문제 접근 이번 문제도 브루트 포스 알고리즘을 사용하여 해결하면 된다. N * M 크기의 체스판이 주어지는데, 1, 1(첫 줄, 첫 번째)번 칸부터 8 * 8 크기의 칸을 모두 확인하여 해당 범위 내에 몇 개의 사각형을 다시 칠해야 하는지 구한다. 이를 1, 1 칸부터 N - 7, M - 7 번 칸까지 반복하며 확인하자. 확인을 위해 1, 1 칸이 검정색으로 시작하는 8 * 8 크기의 보드 배열, 흰색으로 시작하는 보드 배열을 만들고 각 칸이 같은지 비교한다. 모두 비교하여 가장 적은 수의 사각형을 칠해야 하는 경우를 출력하자. 3. 문제 풀이 #include #include using namespace std; in..