[알고리즘] 알고리즘 개념

자료구조(data structure)

효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미
그릇(자료)을 효율적으로 관리하는 방법

개념

컴퓨터 프로그래밍 언어에서 효율적인 자료(데이터)의 형태

종류

단순 자료구조

정수, 실수, 문자, 문자열

선형 자료구조

데이터를 한 줄로 순차적으로 표현한 형태 : 선형 리스트, 연결 리스트, 스택, 큐 등

비선형 자료구조

하나의 데이터 뒤에 여러 개가 이어지는 형태 : 트리와 그래프 등

파일 자료구조

파일 내용이 디스크에 저장되는 방식에 따라 순차 파일과 직접 파일로 구분

순차 파일(Sequential File)

파일 내용을 논리적인 처리 순서에 따라 연속해서 저장하는 것
구조가 간단하기에 저장되는 공간 효율이 높지만,
다른 내용을 추가하거나 삭제할 경우에는 파일 내용을 재구성해야 하므로 상당히 시간이 오래 걸림

직접 파일(Direct File)

파일 내용을 임의의 물리적 위치에 기록하는 방식으로 직접 접근 방식(Direct Access Method)

색인 순차 파일

순차파일과 직접 파일이 결합된 형태

알고리즘(Algorithm)

문제를 해결하거나 함수를 계산하기 위해 좇아야 할 모호함이 없는
간단한 명령들로 구성된 일련의 순차적 단계

특정한 작업을 수행하기 위한 유한 명령어들로 구성되며
컴퓨터의 수행에 적합한 문제 해결을 위한 방법

알고리즘의 목표

단순히 원하는 결과를 얻을 수 있는 알고리즘이 아닌,
처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘을 개발하는 것이 주요 목표

효율성

효율적인 해결 방법들을 발견하여 활용함

추상화

복잡한 문제도 효율적인 알고리즘으로 해결할 수 있는 단순한 문제들로 분류 가능

재사용성

단순한 문제를 효율적 해결 가능한 알고리즘은 다른 많은 문제 해결에도 활용

알고리즘의 역할

역할	설명
모듈성 (Modularity)	- 소프트웨어 설계는 모듈성을 얻기 위해 Black Box 개발에 초점을 둠 - 사용자는 모듈에 대해 개발자가 규정한 공개 인터페이스를 통해서만 접근 가능 - 모듈 상세 구현에 관심이 불필요하며 모듈 내부 임의 변경도 이론 상 불가능
단순성 (Simplicity)	- 문제 해결에서 똑똑한 결과는 가장 단순한 방법
가독성 (Readability)	- 의미 있는 주석을 다는 것 - 적절한 이름을 가진 식별자를 사용하는 것 - 그 자체로 설명되어지는 코드를 만드는 것 - 헤더 파일을 이용해 자료구조와 알고리즘에 대한 공개 인터페이스 정의하고 공개하여 가독성을 높임
일관성 (Consistency)	- 규칙과 규칙을 바탕으로 만들어진 것을 이해하면 이 후 그것들을 보기만 해도 이해 가능 - 일관성은 가독성과 단순성 증진 - 형식에 대해 사용되는 대표적인 규칙 - 개인함수(private function: 공개 I/F 미포함 함수)로써 정적 함수를 사용하는 방법

알고리즘의 조건

구분	내용
입출력 (Input/Output)	- 외부에서 0개 이상 입력을 받아 1개 이상 출력을 생성
명확성 (Definiteness)	- 각 단계가 단순해야 하며, 모호하지 않고 이해하기 쉬움 - 특정 프로그래밍 언어로 변환 하는데 어려움을 느끼지 않을 정도
유한성 (Finiteness)	- 한정된 수의 작업 후에는 반드시 끝내야 함
실용성 (Practicality)	- 모든 명령이 수행 가능해야 함
효율성 (Effectiveness)	- 궁극적으로 컴퓨터를 통해서 구현되는데 충분히 큰 입력에 대하여 알고리즘의 수행 시간은 크게 차이가 발생 가능 하기 때문에 효율적으로 수행 되어야 함

알고리즘 표현법

일반 언어 표현

일반적인 자연어를 사용해서 설명하듯이 알고리즘을 표현

순서도를 이용한 표현

의사코드를 이용한 표현

프로그램 코드로 표현

실제로 사용하는 프로그래밍 언어의 코드로 바로 작성 가능

혼합 형태

간단한 알고리즘은 직접 코드로 작성

알고리즘 성능 측정

알고리즘을 소요 시간을 기준으로 알고리즘 성능을 분석 방법이 ‘시간 복잡도(Time Complexity)’

알고리즘 성능 표기

빅-오 표기법(Big - Oh Notation)으로 O(f(n)) 형태