728x90
반응형
정보처리기사 실기 문제 패턴
프로그램 활용 문제에 대한 내용은 매우 중요합니다. SQL과 함께 약 50%정도의 문제 비율을 가지고 있습니다. 그런데, 이 문제들이 늘 새로울 수는 없습니다. 또한 채점을 위해서라도 기존에 많이 쓰이거나 공식화된 코드를 가지고 나올 가능성이 높습니다. 그렇다면 이미 있는 알고리즘을 알고 있는 것이 중요합니다.
아래의 피보나치 및 정렬 방법은 필수로 알고 있어야합니다.
피보나치 수열
피보나치 수열을 두 숫자를 더해가며 다음 숫자를 찾는 수열입니다. 피보나치 수열은 답이 늘 정해져있을 가능성이 높습니다. 첫 시작의 숫자만 파악하고 피보나치 수열 알고리즘만 파악하면 쉽게 풀 수 있습니다. 다른 기능을 쓰지 않고 일반적인 수식으로 작성할수도 있으며, 재귀함수로 쓰는 경우도 있습니다.
| p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7] | p[8] | |
| 피보나치 수열 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
| 연산 | 0+1 | 1+1 | 2+1 | 3+2 | 5+3 | 8+5 | 13+8 | ||
| p[0]+p[1] | p[2]+p[1] | p[3]+p[2] | p[4]+p[3] | p[5]+p[4] | p[6]+p[5] | p[7]+p[6] |
규칙이 보이시나요? 현재 주소지의 값을 연산하기 위해 앞 주소(n-1)과 앞앞 주소(n-2)의 값을 더하고 있습니다. 0부터 시작하는 것이면 매번 동일한 규칙의 값이 나올 것입니다.
난이도를 높이려면 재귀함수로 쓰겠죠. 아래 예시를 보며 말씀드리겠습니다.
C에서의 피보나치
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
int main() {
int n = 10; // 출력할 피보나치 수열의 길이
int i;
for (i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
return 0;
}JAVA에서의 피보나치
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args) {
int n = 10; // 출력할 피보나치 수열의 길이
for (int i = 0; i < n; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}Python에서의 피보나치
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
n = 10 # 출력할 피보나치 수열의 길이
for i in range(n):
print(fibonacci(i), end=" ")
위 코드들을 보면 앞서 설명한 표의 연산식이 이해되실 겁니다.
정렬 문제 패턴
버블정렬(필수)
앞에서부터 두 숫자를 비교하여 작은 숫자를 앞으로 큰 숫자를 뒤로 보내는 방법입니다. 즉, 인접한 두 개의 요소를 비교하여 필요에 따라 위치를 교환하는 방식으로 정렬하는 알고리즘입니다. 순차적으로 배열을 탐색하면서 가장 큰 요소가 마지막으로 이동합니다.
if (arr[j] > arr[j + 1]); 이 등장 한다는 것을 꼭 기억해야합니다. 두 자리의 순서를 바꾸기 위해 temp 변수를 사용합니다.
C언어
// 버블 정렬(Bubble Sort)
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 두 요소의 위치를 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
bubbleSort(arr, n);
printf("Bubble Sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");JAVA
public class SortingExamples {
// 버블 정렬(Bubble Sort)
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 두 요소의 위치를 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}Python
# 버블 정렬(Bubble Sort)
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
# 두 요소의 위치를 교환
arr[j], arr[j + 1] = arr[j + 1], arr[j]선택정렬(필수)
정렬되지 않은 부분에서 최솟값을 선택하여 정렬된 부분의 다음 위치로 이동시키는 방식으로 정렬하는 알고리즘입니다. 배열 전체를 탐색하면서 가장 작은 요소를 선택하여 정렬합니다. (arr[j] < arr[minIndex]) 와 같이 작은 수를 찾는 부분을 주의해야합니다.
C언어
// 선택 정렬(Selection Sort)
void selectionSort(int arr[], int n) {
int i, j, minIndex;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최솟값과 현재 요소의 위치를 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 선택 정렬
selectionSort(arr, n);
printf("Selection Sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
JAVA
// 선택 정렬(Selection Sort)
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최솟값과 현재 요소의 위치를 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}Python
# 선택 정렬(Selection Sort)
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# 최솟값과 현재 요소의 위치를 교환
arr[i], arr[min_index] = arr[min_index], arr[i]삽입정렬(필수)
배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 정렬된 부분의 올바른 위치에 삽입하는 방식으로 정렬하는 알고리즘입니다. 배열의 왼쪽부터 순차적으로 요소를 선택하여 삽입합니다. (j >= 0 && arr[j] > key)와 같은 부분을 주의해야합니다. key에 숫자를 저장해두고 자기 자리를 찾았을 때 넣어주는 작업입니다.
C언어
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// 삽입 정렬
insertionSort(arr, n);
printf("Insertion Sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");JAVA
// 삽입 정렬(Insertion Sort)
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}Python
# 삽입 정렬(Insertion Sort)
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key퀵정렬(나올 확률 낮음)
분할 정복(divide and conquer) 방법을 사용하여 배열을 재귀적으로 정렬하는 알고리즘입니다. 배열에서 하나의 요소를 선택하고, 선택한 요소를 기준으로 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 분할하여 정렬합니다.
C언어
// 퀵 정렬(Quick Sort)
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
int j;
for (j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 두 요소의 위치를 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗과 i+1 위치의 요소를 교환
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}JAVA
// 퀵 정렬(Quick Sort)
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 두 요소의 위치를 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗과 i+1 위치의 요소를 교환
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}Python
# 퀵 정렬(Quick Sort)
def quick_sort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quick_sort(arr, low, pivot - 1)
quick_sort(arr, pivot + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i = i + 1
# 두 요소의 위치를 교환
arr[i], arr[j] = arr[j], arr[i]
# 피벗과 i+1 위치의 요소를 교환
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1병합정렬(나올 확률 낮음)
분할 정복 방법을 사용하여 배열을 재귀적으로 분할하고, 분할된 배열을 병합하여 정렬하는 알고리즘입니다. 배열을 반으로 나눈 뒤, 나누어진 배열을 정렬하며 병합합니다.
C언어
// 병합 정렬(Merge Sort)
void merge(int arr[], int left, int middle, int right) {
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
// 임시 배열 생성
int L[n1], R[n2];
// 임시 배열에 데이터 복사
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[middle + 1 + j];
}
// 임시 배열을 합병하여 정렬된 배열로 복사
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 남은 요소들을 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}JAVA
// 병합 정렬(Merge Sort)
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// 임시 배열 생성
int[] L = new int[n1];
int[] R = new int[n2];
// 임시 배열에 데이터 복사
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[middle + 1 + j];
}
// 임시 배열을 합병하여 정렬된 배열로 복사
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 남은 요소들을 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}Python
# 병합 정렬(Merge Sort)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
merge(arr, left, right)
def merge(arr, left, right):
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1힙정렬(나올 확률 낮음)
입니다. 배열을 힙으로 만든 뒤, 힙에서 최대값 또는 최소값을 추출하여 정렬된 배열에 차례로 저장합니다.
C언어
// 힙 정렬(Heap Sort)
void heapify(int arr[], int n, int i) {
int largest = i; // 가장 큰 요소
int left = 2 * i + 1; // 왼쪽 자식
int right = 2 * i + 2; // 오른쪽 자식
// 왼쪽 자식이 가장 큰 요소인지 확인
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 가장 큰 요소인지 확인
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 가장 큰 요소가 root가 아니라면 위치를 교환
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// 힙 생성
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 요소를 하나씩 힙에서 추출하여 정렬
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
JAVA
// 힙 정렬(Heap Sort)
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 가장 큰 요소
int left = 2 * i + 1; // 왼쪽 자식
int right = 2 * i + 2; // 오른쪽 자식
// 왼쪽 자식이 가장 큰 요소인지 확인
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식이 가장 큰 요소인지 확인
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 가장 큰 요소가 root가 아니라면 위치를 교환
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void heapSort(int[] arr) {
int n = arr.length;
// 힙 생성
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 요소를 하나씩 힙에서 추출하여 정렬
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}Python
# 힙 정렬(Heap Sort)
def heapify(arr, n, i):
largest = i # 가장 큰 요소
left = 2 * i + 1 # 왼쪽 자식
right = 2 * i + 2 # 오른쪽 자식
# 왼쪽 자식이 가장 큰 요소인지 확인
if left < n and arr[left] > arr[largest]:
largest = left
# 오른쪽 자식이 가장 큰 요소인지 확인
if right < n and arr[right] > arr[largest]:
largest = right
# 가장 큰 요소가 root가 아니라면 위치를 교환
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 힙 생성
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 요소를 하나씩 힙에서 추출하여 정렬
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
계수 정렬 (Counting Sort)(나올 확률 낮음)
정수나 정수로 표현할 수 있는 자료에 대해 작동하는 안정적인 선형 시간 정렬 알고리즘입니다. 각 요소의 개수를 세어 정렬하는 방식으로 작동합니다.
C언어
// 계수 정렬(Counting Sort)
void countingSort(int arr[], int n, int max) {
int output[n];
int count[max + 1];
int i;
// count 배열 초기화
for (i = 0; i <= max; i++) {
count[i] = 0;
}
// 각 요소의 개수 세기
for (i = 0; i < n; i++) {
count[arr[i]]++;
}
// 누적 합 계산
for (i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// output 배열에 요소 복사
for (i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// output 배열을 arr 배열로 복사
for (i = 0; i < n; i++) {
arr[i] = output[i];
}
}JAVA
// 계수 정렬(Counting Sort)
public static void countingSort(int[] arr, int max) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[max + 1];
// count 배열 초기화
for (int i = 0; i <= max; i++) {
count[i] = 0;
}
// 각 요소의 개수 세기
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 누적 합 계산
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// output 배열에 요소 복사
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// output 배열을 arr 배열로 복사
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}Python
# 계수 정렬(Counting Sort)
def counting_sort(arr, max_value):
n = len(arr)
output = [0] * n
count = [0] * (max_value + 1)
# 각 요소의 개수 세기
for num in arr:
count[num] += 1
# 누적 합 계산
for i in range(1, max_value + 1):
count[i] += count[i - 1]
# output 배열에 요소 복사
for i in range(n - 1, -1, -1):
output[count[arr[i]] - 1] = arr[i]
count[arr[i]] -= 1
# output 배열을 arr 배열로 복사
for i in range(n):
arr[i] = output[i]기수 정렬 (Radix Sort)(나올 확률 낮음)
각 자리수를 기준으로 정렬하는 알고리즘입니다. 자리수를 기준으로 일의 자리부터 가장 큰 자리수까지 반복하여 정렬합니다.
C언어
// 기수 정렬(Radix Sort)
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
int i;
// 각 자리수의 개수 세기
for (i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 누적 합 계산
for (i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// output 배열에 요소 복사
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// output 배열을 arr 배열로 복사
for (i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");JAVA
// 기수 정렬(Radix Sort)
public static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 각 자리수의 개수 세기
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 누적 합 계산
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// output 배열에 요소 복사
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// output 배열을 arr 배열로 복사
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
public static void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}Python
# 기수 정렬(Radix Sort)
def radix_sort(arr):
max_value = max(arr)
exp = 1
while max_value // exp > 0:
count_sort(arr, exp)
exp *= 10
# 기수 정렬
radix_sort(arr.copy())
print("Radix Sort:", arr)
728x90
반응형
댓글