1 알고리즘과 절차 지향 프로그래밍

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 번의 검색 끝에 데이터를 찾음

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