알고리즘의 기초 이해

알고리즘의 조건

입력- 0개 이상의 입력이 존재해야한다.(입력이 없어도 된다)

출력 - 1개이상의 출력이 존재해야한다.

명백성 - 각 명령어의 의미는 모호하지않고 명확해야 한다.

유한성 - 한정된 수의 단계 후에는 반드시 종료되어야 한다.

유효성 - 각 명령어들은 실행 가능한 연산이여야 한다.

 

알고리즘의 기술방법

자연어 ( ex)메뉴얼 )

1.읽기 쉬움

2.단어들을 정확하게 정의하지 않으면 의미 전달이 모호

 

흐름도

1.직관적이고 이해하기 쉬운 알고리즘 기술방법

2.그러나 복잡한 알고리즘의 경우 상당히 복잡해짐

 

유사코드(슈도코드)

1. 알고리즘의 고수준 기술 방법

2. 자연어보다는 더 구조적인 표현방법

3. 프로그래밍 언어보다는 덜 구체적

 

프로그래밍 언어

1. 알고리즘의 가장 정확한 기술이 가능

2. 실제 구현 시 많은 구체적인 사항들이 알고리즘의 핵심적인 내용에 대한 이해를 방해

---

알고리즘 예시

>>알고리즘이란건 상황 상황 마다 가장 효율적인 방법은 다르다

즉, 가장 완벽한 알고리즘이란건 없다. 효율적인 알고리즘만 있다.

ex) 배열이나 연결리스트에서 n개중에 k 번째 원소를 가져오는 경우

1.배열에서는 첨자를 이용하여 array[k] 처럼 한번에 가능(1회)

2.연결리스트에서는 k-1 노드들을 다 거쳐가야함(k-1회)

 

ex)정렬(sorting)된 배열이나 연결리스트에서 어떤 원소를 찾는 경우

1.정렬된 배열에서는 이진 탐색 기법을 사용(매우빠름)

2.다른 일반적인 방법으로는 찾는 원소보다 작은 원소를 다 살펴봐야함

 

ex)배열에서 새 원소를 삽입하는 경우

1.배열에서는 삽입 후에 자리가 바뀐 모든 원소를 다시 복사(매우 느림)

 

ex)연결 리스트에서 새 원소를 삽입하는 경우

1. 연결고리를 재 배치(크기에 관계 없이 동일한 시간 소요,매우빠름)