문제 분해와 알고리즘

• 복잡한 문제를 해결 가능한 작은 문제로 분해하고 모델링한다.
• 데이터를 정렬하는 다양한 알고리즘의 특징과 효율을 비교·분석한다.
• 데이터를 탐색하는 다양한 알고리즘의 특징과 효율을 비교·분석한다.

1

2

여행 계획, 어떻게 효율적으로 세울 수 있을까?

일상을 떠나 새로운 곳으로의 여행을 통해 휴식과 즐거움을 찾는 사람이 많다. 그러나 여행을 떠나려는 결심을 하고 계획을 세우기 시작하면서 어디로 여행을 갈 것인지, 일정을 어떻게 계획해야 할 것인지, 교통편을 어떻게 이용하는 것이 좋을지, 숙박과 관광지 코스는 어떻게 정해야 할지 등 해결해야 할 크고 작은 문제들을 만난다.

이와 같이 해결해야 할 요소가 다양할 때는 문제를 분해하여 각각의 요소로 나누어 해결하는 것이 바람직하다.

즐거운 여행에 필요한 요소는 어떻게 나누어 계획을 수립할 수 있을까?

3

3

3

3

3

3

3

알고리즘의 원리

문제 분해와 모델링

문제의 이해

• 문제란 해결이 필요한 모든 것을 의미
• 문제는 현재 상태와 목표 상태의 차이로 인해 발생
• 문제 해결은 현재 상태를 목표 상태로 만드는 과정
• 효율적인 알고리즘을 설계하여 문제를 쉽게 해결 가능

4

복잡한 문제를 해결 가능한

작은 문제로 분해하여 모델링

할 수 있다.

• 컴퓨팅 시스템을 활용하면 계산 문제와 같은 복잡한 문제를 빠르고 정확하게 해결할 수 있음

​

​

5

01. 문제 분해와 모델링

6

6

6

6

6

6

6

문제해결을 위한 추상화 방법 5단계

문제 분해와 모델링

복잡한 문제는 추상화를 통해 단순화 가능

① 작은 문제로 분해

• 대부분의 문제는 작은 문제로 분해할 수 있음
• 문제를 작게 분해할수록 해결이 쉬워짐

7

01. 문제 분해와 모델링

② 모델링을 통해 단순화

• 모델링은 데이터를 이해하기 쉽게 재구성하는 과정
• 핵심적인 요소를 제외한 나머지를 제거하여 효율적인 의사소통이 목적
• 모델링 결과는 문자, 수식, 그림, 표, 픽토그램 등 다양한 형태로 제시될 수 있음

8

01. 문제 분해와 모델링

문제를 모델링하여 해결하기

• 가상의 인물 루루의 사진으로 추상화 단계를 거쳐 표현해 보고 친구들과 비교해 보자.

​

​

​

​

​

​

• 다음의 사례에서 문제를 발견하고 모델링해 보자.

9

주어진 문제 상황을 분석하여 현재 상태와 목표 상태로 정의해 보자.

​

​

​

주어진 문제 상황을 분해하여 작은 문제로 정의할 수 있는 방법을 적어 보자.

10

분해한 문제를 표, 그림 등을 활용하여 모델링해 보자.

11

정렬 알고리즘

정렬 알고리즘의 의미

• 정렬은 항목이나 데이터를 오름차순 또는 내림차순으로 재배치하는 작업

12

• 정렬의 개념을 이해하고, 다

양한 정렬 알고리즘에 대해

설명할 수 있다.

• 다양한 정렬 알고리즘의 효율

을 비교·분석할 수 있다.

• 정렬 알고리즘은 데이터를 체계적으로 정리하여 탐색과 분석을 용이하게 함
• 정렬 알고리즘 활용의 장점
• 데이터를 원하는 기준으로 정리할 수 있음
• 대규모의 데이터를 활용하고 관리하면 문제를 효율적으로 해결할 수 있음

​

13

02. 정렬 알고리즘

정렬 알고리즘의 종류

① 버블 정렬

• 인접한 두 개의 값을 비교하여 순서가 맞지 않으면 교환하는 방식
• 버블 정렬 알고리즘(오름차순 정렬일 때)

① 맨 왼쪽부터 시작하여 배열의 첫 번째 값부터 마지막 값까지 순차적으로 비교한다.

② 두 인접한 값을 비교하여 만약 순서가 맞지 않는다면 두 데이터의 위치를 교환한다.

③ 모든 인접한 요소를 비교하면 가장 큰 값이 배열의 맨 오른쪽에 이동하게 되며, 가장 큰 값부터 정렬이 이루어진다.

④ ①~③의 과정을 반복하면서 주어진 데이터를 정렬한다.

14

02. 정렬 알고리즘

15

02. 정렬 알고리즘

② 선택 정렬

• 현재 위치에 들어갈 데이터를 찾아 선택하고 교환하는 방식
• 선택 정렬 알고리즘(오름차순 정렬일 때)

① 정렬되지 않은 맨 왼쪽부터 시작해서 오른쪽으로 이동하면서 배열의 각 위치를 순차적으로 선택한다.

② 현재 위치부터 오른쪽으로 이동하면서 값을 비교하고 가장 작은 값(최솟값)을 찾는다.

③ 찾은 최솟값을 현재 위치의 값과 교환하게 되며 가장 작은 값부터 정렬이 이루어진다.

④ ①~③의 과정을 반복하면서 주어진 데이터를 정렬한다.

16

02. 정렬 알고리즘

17

02. 정렬 알고리즘

③ 삽입 정렬

• 이미 정렬된 데이터에 새로운 데이터를 올바른 위치에 삽입하는 방식
• 삽입 정렬 알고리즘(오름차순 정렬일 때)

① 정렬되지 않은 맨 왼쪽부터 시작해서 오른쪽으로 이동하면서 정렬되지 않은 값(현재 값)을 삽입할 위치를 찾는다.

② 정렬된 값 중 큰 값부터 작은 값 순서대로 하나씩 현재 값과 비교한다.

③ 현재 값보다 작거나 같은 값이 나오면 비교한 값 오른쪽에 현재 값을 삽입한다.

④ 정렬된 모든 값을 비교했다면 맨 앞에 현재 값을 삽입한다.

⑤ ①~④의 과정을 반복하면서 주어진 데이터를 정렬한다.

18

02. 정렬 알고리즘

19

02. 정렬 알고리즘

④ 퀵 정렬

• 피벗을 설정하고 이를 기준으로 데이터를 분할하여 정렬하는 방식
• 퀵 정렬 알고리즘(오름차순 정렬일 때)

① 정렬할 데이터 중 하나를 피벗으로 설정한다.

② 데이터를 피벗과 비교하여 작은 데이터는 피벗의 왼쪽, 큰 데이터는 피벗의 오른쪽에 배치하여 피벗을 중심으로 작은 데이터 그룹과 큰 데이터 그룹으로 분할한다.

③ 분할된 데이터 그룹에서 다시 피벗을 설정하고, 피벗을 기준으로 데이터를 분할한다.

④ ①~③과정을 반복하면서 주어진 데이터를 정렬한다.

​

​

20

02. 정렬 알고리즘

21

02. 정렬 알고리즘

정렬 알고리즘의 비교

① 정렬 알고리즘의 종류별 특징

• 알고리즘마다 상황에 따라 다른 성능을 발휘

22

02. 정렬 알고리즘

병합 정렬 비교 기반 정렬 알고리즘이며, 분할 정복 알고리즘의 하나

힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법

② 정렬 알고리즘의 효율성 비교

​

​

■ 버블 정렬 알고리즘을 사용하여 정렬하기

23

02. 정렬 알고리즘

​

​

​

■ 선택 정렬 알고리즘을 사용하여 정렬하기

24

02. 정렬 알고리즘

​

​

​

■ 삽입 정렬 알고리즘을 사용하여 정렬하기

25

02. 정렬 알고리즘

​

​

​

■ 퀵 정렬 알고리즘을 사용하여 정렬하기

26

02. 정렬 알고리즘

27

02. 정렬 알고리즘

여러 가지 방법으로 정렬하기

• A학급 학생들의 시험 점수를 참고하여 제시된 문제를 해결해 보자.

28

교내 정보 올림피아드에 참여할 학생을 선발하기 위해 A학급 학생들을 정렬하려고 한다.

정렬 알고리즘 중 하나를 선정하고 정렬 과정을 작성해 보자.

29

A학급에서 교내 정보 올림피아드에 출전할 학급 대표 학생 3명을 선발하려고 한다.

어떤 학생들을 선발할 것이며 그 이유는 무엇인지 적어 보자.

30

탐색 알고리즘

탐색 알고리즘의 의미

• 탐색은 여러 개의 자료 중 원하는 자료를 찾는 작업
• 탐색 알고리즘은 대규모 데이터에서도 원하는 데이터를 빠르게 찾을 수 있음

31

• 탐색의 개념과 다양한 탐색

알고리즘에 대해 설명할 수

있다.

• 다양한 탐색 알고리즘의 효율

을 비교·분석할 수 있다.

탐색 알고리즘의 종류

① 순차 탐색

• 데이터를 순서대로 하나씩 확인하며 탐색하는 방식
• 순차 탐색 알고리즘

① 배열되어 있는 맨 왼쪽 데이터부터 탐색을 시작한다.

② 현재 확인하는 데이터가 찾고자 하는 데이터라면 탐색을 종료한다.

③ 만약 찾고자 하는 데이터가 아니라면 오른쪽 데이터로 넘어간다.

④ ②~③단계를 반복하며 모든 데이터를 확인하면 탐색을 종료한다.

32

03. 탐색 알고리즘

33

03. 탐색 알고리즘

② 이분 탐색

• 데이터가 정렬된 상태에서 탐색 범위를 반으로 줄여가며 탐색하는 방식
• 이분 탐색 알고리즘

① 정렬된 데이터의 가운데 위치부터 확인한다.

② 현재 확인하는 데이터가 찾고자 하는 데이터라면 탐색을 종료한다.

③ 현재 확인한 데이터가 정렬 순서상 찾고자 하는 데이터보다 앞에 있으면 오른쪽 범위를 탐색하고, 뒤에 있으면 왼쪽 범위를 탐색한다.

④ ①~③단계를 반복하며 모든 데이터를 확인하면 탐색을 종료한다.

​

34

03. 탐색 알고리즘

35

03. 탐색 알고리즘

탐색 알고리즘의 비교

• 각 탐색 알고리즘은 상황에 따라 장단점이 있으며, 적절하게 활용해야 함

​

36

03. 탐색 알고리즘

여러 가지 방법으로 탐색 체험하기

• 3~4명이 한 팀이 되어 UP/DOWN 게임을 해 보자.

​

​

​

​

​

​

자신이 생각한 숫자와 정답을 맞히기까지 걸린 횟수를 적어 보자.

​

​

만약 숫자의 범위가 [1~1,000]으로 늘어나면 몇 번의 기회가 필요한지 적어 보자.

37

최대 10번의 기회가 필요하다.

알고리즘의 효율성 평가

• 알고리즘의 효율성: 문제를 해결하는 데 어떤 알고리즘이 가장 적합한지를 평가하는 기준
• 효율적인 알고리즘의 선택 기준: 알고리즘 수행 시 메모리 사용량, 수행 시간

38

• 효율적인 알고리즘의 선택

기준을 설명할 수 있다.

• 정렬과 탐색 알고리즘의 효율

성을 비교·분석할 수 있다.

빅-오 표기법 알고리즘이 데이터를 처리하는 데 걸리는 시간을 측정하여 알고리즘 성능을 평가하는 것으로, 보통 최악의 경우를 예상하여 성능을 평가한다. 이를 통해 해당 알고리즘의 최저 성능을 파악하고 비교한다. 빅-오 표기법은 알고리즘의 개략적인 성능을 표시하기 때문에 정확한 단위 연산의 적용 횟수나 소요 시간을 나타내지 않고 데이터의 크기와 데이터 처리에 필요한 단위 연산의 적용 횟수와의 관계를 나타낸다.

• 알고리즘의 수행 시간은 알고리즘의 정확한 효율성을 판단하기 어려움
• 주로 수행 횟수를 통해 알고리즘을 비교함

39

04. 알고리즘의 효율성 평가

정렬 알고리즘 비교하기

• A학교의 학급 대항 축구 경기 결과를 통해 모둠별로 정렬의 기준을 선정하고 정렬 알고리즘을 활용하여 학급 순위를 정해 보자.

​

40

모둠에서 정한 학급 정렬의 기준을 적어 보자.

​

​

​

​

​

자신이 선택한 정렬 알고리즘을 사용하여 정렬하고, 비교 횟수와 교환 횟수를 계산해 보자.

​

​

​

​

모둠원이 계산한 알고리즘의 효율성을 비교하고, 효율적인 알고리즘을 순서대로 나열해 보자.

41

퀵 정렬 > 삽입 정렬 > 선택 정렬 > 버블 정렬

탐색 알고리즘 비교하기

• 정렬된 시험 성적에서 85점인 학생의 이름을 찾으려고 한다. 순차 탐색과 이분 탐색을 사용했을 때의 탐색 횟수를 활용하여 알고리즘의 효율성을 비교해 보자.

​

​

​

순차 탐색을 사용하여 탐색했을 때의 효율성을 계산해 보자.

​

​

​

이분 탐색을 사용하여 탐색했을 때의 효율성을 계산해 보자.

42

8번

2번

어떤 알고리즘이 효율적이라고 생각하는지 탐색 횟수를 비교하여 설명해 보자.

​

​

​

​

순차 탐색이 효율적인 상황과 이분 탐색이 효율적인 상황을 찾아 작성해 보자(현재 데이터는 정렬되어 있지 않은 상태이다).

43

순차 탐색의 탐색 횟수가 이분 탐색에 비해 4배 차이 나기 때문에 이분 탐색이 효율적이다.