알고리즘

알고리즘

• 분해, 패턴인식, 추상화 과정을 통해 명확해진 문제들을 문제를 해결 순서대로 나열하는 것

• 자연어, 순서도, 의사코드

라면 제조

• 구체적으로 얼마만큼 값을 제공해야하는지 명확하게 설명해야함

사람이 이해할 수 있는 언어로 작성

• 컴퓨터로 실행하고자 한다면 알고리즘을 컴퓨터가 이해할 수 있는 언어로 바꿔야함

알고리즘의 조건

• 순차성 : 올바른 순서대로 진행되어야함

• 명확성 : 명령어는 명확해야함

• 유효성 : 실행가능한 연산이어야 함

• 유한성 : 한정된 수의 명령어가 실행된 후에는 반드시 종료되어야 함

• 효율성 : 가장 효율적인 방법으로 문제를 해결해야함

오름차순으로 나열하기

컴퓨터는 한번에 여러개를 비교할 수 없음

그래서 하나하나 계산해야함

수가 8,5,12,3이 있을때 순서대로 정렬하기 위해서 사람은 바로 최솟값이 3인걸 알지만 컴퓨터는 한번에 못찾음

1. 최솟값을 저장하는 공간을 두고, 맨 처음의 수를 최솟값에 저장해둠

2. 그 다음 값과 최솟값의 값을 비교해서 더 작은 값을 최솟값에 다시 저장함

3. 반복해서 주어진 배열을 모두 돌아서, 최솟값을 찾아냄

이렇게 해서 최소값을 하나 찾아내는거임

그리고 이후 두 번째 값부터 1~3까지 다시 반복함

계속 반복하면 3,5,8,12라는 순서로 정렬되게 됨

최솟값을 찾아 순서대로 나열하는 방법→ 선택 정렬

4개에서 최솟값찾는것

3개에서 최솟값 찾는것

2개에서 최솟값 찾는것이 패턴이 됨

정렬문제에 대한 고찰

• 사람은 4개의 숫자를 한번에 파악가능

• 그러나 정렬 방법이나 과정을 설명하기 어려움

• 알고리즘은 복잡한 단계를 반복적으로 실행해서 어렵게 결과를 도출한다.

• 방법과 과정을 명확하게 설명할 수 있다.

많은 숫자를 정렬하려면

• 사람의 방법으로는 하기 어렵다.

• 위의 알고리즘을 따라하면 많은 단계를 거치지만 정렬이 가능해진다.

• 컴퓨터로 알고리즘을 변환하여 실행하면? → 단순하고 많은 반복단계를 매우 빠르게 실행

특정한 값 찾기

• 찾을 대상이 속한 배열이 정렬이 되어있는 경우 더 빠르게 찾을 수 있다.

• 배열의 가운데값을(5개라면 3번째 값 평균값이나 중간값이 아님)기준으로 큰가 작은가 비교

• 크면 작은값들을 제외함

• 작으면 큰값들을 제외함

• 반복

이진탐색(Binary search)

가장 효율적인 방법은?

• 비교 횟수를 최소로 하는 알고리즘

• 처음부터 차례로 비교하는 경우 최대 1000개 비교 평균 500번 비교

• 중간 값을 비교하여 범위를 좁혀가는 경우 최대 log2 1000번 10번

컴퓨터 알고리즘이라는 과목에서 자세하게 알게됨

Uploaded by N2T