01 알고리즘과 절차 지향 프로그래밍
- 배우기 쉬운 알고리즘을 몇 가지 소개할 것
- 지금까지 배운 프로그래밍 언어의 기능으로 특정 문제를 해결하는 코드를 작성하는 기법을 배울 것
- 알고리즘을 바탕으로 입력, 처리, 출력의 단계로 진행되는 프로그래밍 언어의 절차 지향 프로그래밍 기법을 정리함
- 절차 지향 프로그래밍에서 사용되는 것이 입력, 처리, 출력의 단계
1. 알고리즘 (Algorithm)
- 알고리즘(풀이법)이란, 프로그램 개발에 있어 필요한 문제를 해결하는 방법을 체계적으로 정리한 것, 즉, "문제 해결 능력"
- 주어진 문제를 어떻게 풀이하는가에 따라 그 문제를 해결할 수도, 못할 수도 있으므로 프로그램 작성에 있어 알고리즘이란 중요한 자리를 차지하고 있음
- 프로그램의 가장 작은 단위는 일반적으로 입력(input) → 처리(process) → 출력(output)의 단계를 거침
- 입력(input): 자료 구조(Data Structure)가 담당하는 영역
- 처리(process): 알고리즘 처리 영역
- 출력(output): UI가 담당하는 영역. 일반적으로 콘솔, 데스크톱, 웹, 모바일 등의 영역으로 나누어서 가공된 데이터가 출력됨
- 순서도 (FlowChart): 알고리즘을 정해진 기호로 표시한 것을 순서도라고 함 (현업에서는 잘 사용하지 않기에 이 강의에서도 다루지 않을 것. 그러나 정보처리기사와 같은 자격등 취득하려면 알고 있으면 유용)
2. 학습용 쉬운 알고리즘
- 다음 12개의 쉬운 알고리즘을 학습할 것
- 모든 소스 코드는 디버거를 사용하여 줄 단위로 코드를 실행하면서 코드의 흐름을 익히는 것 권장
난이도 | 알고리즘 | 사용 유형 |
초급 | 합계 (SUM) | 합계를 출력하시오 |
개수 (COUNT) | 자료 건수를 출력하시오 | |
평균 (AVERAGE) | 평균을 출력하시오 | |
최댓값 (MAX) | 최댓값을 출력하시오 | |
최솟값 (min) | 최솟값을 출력하시오 | |
중급 | 최댓값(MAX) → 최솟값(min) | ~에 대해서 최댓값을 구하되, 동일값 발생시 ~에 대해서 최솟값을 구하시오 |
최솟값(min) → 최댓값(MAX) | ~에 대해서 최솟값을 구하되, 동일값 발생시 ~에 대해서 최댓값을 구하시오 | |
최댓값(MAX) → 최댓값(MAX) | ~에 대해서 최댓값을 구하되, 동일값 발생시 ~에 대해서 최댓값을 구하시오 | |
최솟값(min) → 최솟값(min) | ~에 대해서 최솟값을 구하되, 동일값 발생시 ~에 대해서 최솟값을 구하시오 | |
최댓값(MAX) - 최솟값(min) | ~에서 최댓값과 최솟값을 구하고, 최댓값과 최솟값의 차를 구하시오 | |
고급 | 근삿값 (NEAR) | ~에 가장 가까운 값을 구하시오 |
순위 (RANK) | 순위를 구하시오 | |
정렬 (SORT): 오름차순/내림차순 | ~에 대해서 오름차순/내림차순 정렬하시오 | |
검색 (SEARCH) | 특정 자료를 검색하시오 | |
병합 (MERGE) | 2개의 배열을 하나의 배열로 합치시오 | |
최빈값 (MODE) | 가장 빈도수가 높은 자료를 구하시오 | |
그룹 (GROUP) | 특정 항목별 그룹화하여 소계를 구하시오 |
3. 정렬 (SORT) 알고리즘
1) 정렬 (SORT) 알고리즘
- 주어진 범위 내에서 불규칙적으로 나열된 순서를 일정 기준에 따라 순서대로 나열하는 알고리즘
- 정렬 알고리즘은 선택 정렬 (SELECTION SORT), 버블 정렬 (BUBBLE SORT), 퀵 정렬 (QUICK SORT) 등 많이 있음
- 그 중 선택 정렬 알고리즘을 사용할 것
- 오름차순 정렬: 1, 2, 3 순으로 작은 것부터 큰 순으로 정렬 (1, 2, 3; 가, 나, 다; A, B, C)
- 내림차순 정렬: 3, 2, 1 순으로 큰 것부터 작은 순으로 정렬 (3, 2, 1; ㄷ, ㄴ, ㄱ; c, b, a)
2) 선택 정렬 (SELECTION SORT) 알고리즘
- 데이터 하나를 기준으로 나머지 데이터와 비교하여 가장 작거나 큰 데이터와 자리를 바꾸는 식으로 반복 비교하는 정렬 방법
- 선택 정렬은 데이터의 개수가 n개이면 전체 회전수는 n-1회
- 선택 정렬 알고리즘은 오름차순 기준으로 배열의 처음부터 가장 작은 데이터가 채워짐
3) 선택 정렬 회전수
- 배열 data[5]에 다음과 같이 데이터가 입력되어 있을 경우 선택 정렬을 사용하여 오름차순으로 정렬시키는 단계를 간단히 표현해 볼 것임 (지면상 모든 단계를 표현하는 것이 아닌 왼쪽에 가장 작은 값이 들었을 때까지만 표현할 것임)
- 1회전: data[0]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복하면 data[0]에는 가장 작은 값이 들어감
- 2회전: data[1]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복함. 2회전이 끝나면 data[1]에 두 번째로 작은 값이 들어감
- 3회전: data[2]를 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복함. 3회전이 끝나면 data[2]에 세 번째로 작은 값이 들어감
- 4회전: data[3]을 기준으로 나머지 데이터와 비교하여 가장 작은 값과 자리를 바꾸는 과정을 반복함. 4회전이 끝나면 data[3]에 네 번째로 작은 값이 들어감
4) 참고: 선택 정렬 관련 정보처리긱사 필기 문제
- 문제: 자료가 다음과 같이 주어졌을 때 선택 정렬 (selection sort)을 적용하여 오름차순으로 정렬할 경우 pass 2를 진행한 후의 정렬된 값으로 옳은 것은?
- 답: 나
- 해설: 가장 작은 데이터를 왼쪽으로 하나씩 채우는 형태로 각 회전이 끝난 후의 배열 모양은 다음과 같다.
- pass 1: 4, 9, 5, 11, 8
- pass 2: 4, 5, 9, 11, 8
- pass 3: 4, 5, 8, 11, 9
- pass 4: 4, 5, 8, 9, 11
4. 검색 (SEARCH) 알고리즘
1) 검색 (SEARCH) 알고리즘
- 검색 알고리즘은 배열 등의 데이터에서 특정 값을 검색하는 알고리즘
- 일반적으로 순차 검색과 이진 검색 등으로 구분할 수 있음
- 순차 검색: 전체 데이터를 처음부터 끝까지 순서대로 검색
- 이진 검색: 정렬되어 있는 데이터를 절반으로 나눠서 검색
2) 이진 검색 (BINARy SEARCH) 알고리즘
- 이진 검색 알고리즘은 주어진 데이터가 오름차순으로 정렬되어 있다고 가정하고 시작함 (만약 데이터가 정렬되어 있지 않다면 정렬한 다음 이진 검색 알고리즘 로직을 적용해야 함)
- 이진 검색 알고리즘은 나누기 및 정복 (Divide and Conquer) 알고리즘으로 표현하는데 의미 그대로 데이터를 절반으로 나눠 검색하여 순차 검색보다 효율을 높임
- 다음 그림과 같이 1차원 배열에서 1, 3, 5, 7, 9의 데이터가 있을 경우 이진 검색을 사용하면 중간 인덱스 값을 찾는 것이 핵심 로직
- 중간 인덱스를 mid로 설정하고 low 인덱스는 0, high 인덱스는 4로 본 후 각 회전마다 중간 인덱스를 구하고 중간 인덱스의 값이 찾으려는 데이터인지를 비교하면 됨
- 위 그림 설명:
- 1 회전
- 1 회전 들어가기 전: low = 0, high = 4, mid = (low + high) / 2 = (0 + 4) / 2 = 2
- 1 회전: mid 값인 2 인덱스의 데이터인 5와 찾으려는 9 비교, 찾으려는 데이터가 5보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해 low 값을 mid + 1로 증가해서 low를 3으로 재설정
- 2 회전
- 2 회전 들어가기 전: low = 3, hight = 4, mid = (3 + 4) / 2 = 3
- 2 회전: mid 값인 3 인덱스의 데이터인 7과 찾으려는 9 비교, 찾으려는 데이터가 7보다 크므로 왼쪽 영역은 버리고 오른쪽 영역만 비교하기 위해 low 값을 mid + 1로 증가해서 low를 4로 재설정
- 3 회전
- 3 회전 들어가기 전: low = 4, hight = 4, mid = (4 + 4) / 2 = 4
- 3 회전: mid 값인 4 인덱스의 데이터인 9와 찾으려는 9 비교, 3 번의 검색 끝에 데이터를 찾음
- 1 회전
3) 참고: 이진 검색 관련 정보처리기사 필기 문제
- 문제: 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교되는 횟수는?
- 답: 나
- 해설:
- 1 회전: (0 + 14) / 2 = 7 번째 인덱스의 값인 8
- 2 회전: (8 + 14) / 2 = 11 번째 인덱스의 값인 12
- 3 회전: (12 + 14) / 2 = 13 번째 인덱스의 값인 14 ←찾으려는
기타
1. 개발 도구
- Visual Studio - C/C++언어로 개발 시 유용
- Visual Studio Code
2. 강의 소스
- https://github.com/VisualAcademy/C
'C > C 알고리즘 입문 (이젠 강의 내용)' 카테고리의 다른 글
2 초급 알고리즘 (sum, sequence, count, avg, max, min) (0) | 2024.06.18 |
---|