[고등학교 정보교과서] 3. 문제 해결과 프로그래밍 (2) 알고리즘 Algorithm ② - 씨마스

고등학교 정보교과서 3. 문제 해결과 프로그래밍 (2) 알고리즘 Algorithm ② - 씨마스

 

---

 

알고리즘 분석 Algorithm Analysis

같은 문제를 해결할 수 있는 서로 다른 알고리즘이 2개 이상일 수 있습니다.

여러가지 해결방법 중 어떤 알고리즘을 선택하는 것이 좋을까요?

동일한 결과를 반환한다면, 컴퓨터의 연산 횟수가 적은 알고리즘이 더 효율적이라고 할 수 있습니다.

1~100 까지 정수의 합을 구하는 알고리즘은 아래와 같이 2가지가 있을 수 있습니다.

• 방법1. 1~100 까지 반복하여 정수를 하나씩 더한다.
• 방법2. 가우스의 공식을 사용한다.

방법1은 1~100까지 정수의 개수인 100회를 실행해야 하고,

방법2는 가우스의 공식 1번만 실행하여 동일한 결과값을 반환하므로 방법2의 알고리즘이 더 효율적입니다.

 

정렬 알고리즘

무작위 순서대로 나열된 여러 자료들을 특정 기준에 맞게 순서대로 나열하는 알고리즘입니다.

▶ 버블정렬 Bubble Sort

첫번째 요소부터 자신의 이웃한 요소와 비교하며 위치를 바꾸는 정렬방식입니다.

직관적이어서 이해하기 쉽지만, 모든 요소와 비교해야 하므로 처리 시간이 오래 걸린다는 단점이 있습니다.

버블정렬 [출처] 고등학교정보교과서 씨마스

 

▶ 선택정렬 Selection Sort

두번째 요소부터 가장 첫번째 요소와 비교하여 위치를 바꾸는 정렬방식입니다.

요소들 간의 비교 연산은 많지만 위치 변경 연산은 적어 버블정렬보다 시간적으로 효율적입니다.

선택정렬 [출처] 고등학교정보교과서 씨마스

 

탐색 알고리즘

정렬 알고리즘으로 자료들을 기준에 맞게 나열했다면, 원하는 자료를 최대한 빠르게 찾기 위해 탐색 알고리즘을 사용합니다.

▶ 순차탐색 Sequential Search

첫번째 요소부터 순서대로 모든 요소를 방문하여 원하는 자료를 찾는 방법입니다.

구현하기에는 간단하지만, 원하는 자료가 맨 마지막에 위치한 최악의 경우 모든 요소들을 방문해야 하므로 탐색 속도는 느립니다.

순차탐색 [출처] 고등학교정보교과서 씨마스

 

▶ 이진탐색 Binary Search

정렬된 요소들의 중간값을 원하는 자료와 비교하여 탐색 범위를 줄여가는 방법입니다.

중간값보다 크면 오른쪽 요소 집합, 작으면 왼쪽 요소 집합에서 찾는 방식으로 탐색 속도가 빠릅니다.

이진탐색 [출처] 고등학교정보교과서 씨마스