사과하는 제라스

출처 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 8 3. 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 92 4. 풀이 이 문제를 풀고자 백트래킹 알고리즘을 공부를 했다. 우선 ..

출처 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 5 5 4 3 2 1 3. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과..

출처 : https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 10 5 2 3 1 4 2 3 5 1 7 3. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 1 1 2 2 ..

[정렬 방법] 정렬에 앞서, 이 정렬을 이용하고자 할 때 조건은 정해진 범위 내의 숫자들만을 배열의 원소값으로 가져야 한다는 것이다. 이렇기에 나중에 타 정렬들과 비교했을 때 상대적으로 시간 복잡도가 작고 빠른 특성을 띤다. 먼저, 임의의 배열 arr에 정해진 범위의 숫자들(ex)0~20)을 넣는다. 이후 20 크기의 배열 c_arr을 만들고 arr을 for문을 돌리면서 원소값과 같은 index의 c_arr의 값을 1씩 증가시킨다. 이후 결과로 사용할 result 배열에 arr의 값들을 정렬시킬 것인데, arr의 가장 마지막 원소값(k)부터 시작해서 그 원소값과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result 배열의 원소값에 k를 넣는다. 이 과정을 거치면 사용된 c_arr의 원소값을 -1..

합병정렬은 분할 정복(Divide and Conquer) 알고리즘을 이용하여 푸는 방식이다. 1. 먼저, 주어진 배열을 절반의 크기로 나누는데 그 크기가 2짜리 배열이 될 때까지 계속해서 반복한다. 2. 이후, 길이가 2인 각 배열들 내에서 크기 순으로 정렬하고, 이웃한 2개의 배열을 합쳐서 또 정렬한다. 이를 모든 배열들이 합쳐져 원래 크기의 배열의 길이가 될 때까지 반복한다. 3. 이때, 정렬은 다음과 같은 방식으로 진행한다. ex) arr[0~3] arr[4~7]을 비교하여 정렬 시. arr[0]와 arr[4]를 비교하고 작은 수를 먼저 temp[0~7]라는 임의의 배열의 temp[0]에 넣는다. 그 수가 만약 arr[0]이었다면, 다음엔 arr[1]과 arr[4]를 비교한다. 이런 식으로, 두 배..

유클리드 호제법의 기능부터 살펴보자면 2개의 자연수에 대해서 최대공약수(GCD)를 구하고 이를 바탕으로 최소공배수(LCM)를 구할 수 있다. 두 수 A, B에 대해서 큰수 A를 작은 수 B로 나누는데 이때 나머지가 0이면 작은 수가 최대공약수이다. 만약 나눠떨어지지 않으면 B를 A/B의 나머지로 다시 나눈다. 이때 나눠 떨어지면 A/B의 나머지가 최대공약수가 된다. 이 과정을 나눠떨어질 때까지 반복을 하는데 간단히 보자면 두 수를 서로 나누는 과정을 나눠떨어질 때까지 반복하고 나눠떨어질 때 나누는 수가 최대공약수가 된다. 유클리드 호제법을 간단히 예시를 통해 풀이해보자면... 1. 다음과 같이 두 수가 주어진다. 231, 84 2. 이 두 수를 유클리드 호제법을 이용하면 231를 84로 나누면 나머지는 ..

출처 : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 5 5 2 3 4 1 3. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 1 2..

[정렬 방법] 전체(n개의 값)에서 arr[1], arr[2], ..., arr[n-1] 순으로 기준값(key)으로 두고 바로 왼쪽 값부터 왼쪽에 있는 값들이 key보다 클 경우 한칸씩 오른쪽으로 옮긴다. 작을 경우엔 멈추고 비교대상이던 값의 오른쪽에 key값을 넣어준다. 이 과정을 arr[n-1]까지 진행하면 정렬된다. [정렬 과정] n 크기의 임의의 배열 arr에서 - 1번의 비교 arr[1] 값을 key값으로 둔 후, arr[0]와 비교해서 key값이 작으면 arr[1] = arr[0], arr[0] = key, key값이 크면 arr[1] = key - 최대 2번의 비교 arr[2] 값을 key값으로 둔 후, arr[1]와 비교해서 key값이 작으면 arr[2] = arr[1]로 한 후 (1), ..