컴퓨터 알고리즘이란? #

• 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것
• 알고리즘의 조건 → 입출력, 명확성, 유한성, 유효성

기본적인 자료구조 #

• 선형 구조 → 배열, 연결리스트, 큐, 스택
• 비선형 구조 → 트리, 그래프

알고리즘의 설계 방법 #

• 주어진 문제와 조건 등이 매우 다양하므로 알고리즘의 일반적인 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

욕심쟁이 방법 #

• 해를 구하는 일련의 선택 과정마다 그 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면, 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다.

분할정복(divide and conquer) 방법 #

• 순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 세 단계를 거친다.
• 적용 가능한 문제 → 퀵 정렬, 합병 정렬, 이진 탐색 등

동적 프로그래밍(dynamic Programming) 방법 #

• 주어진 문제를 여러 개의 부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고 이를 이용하여 입력 크기가 더 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법이다.
• 적용 가능한 문제 → 플로이드 알고리즘

알고리즘 분석은 두 가지 측면에서 수행 #

• 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 산출하는지를 판단한다.
• 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 즉 소요되는 메모리 공간의 크기(“공간 복잡도”)와 수행에 걸리는 시간(“시간 복잡도”)을 추정한다.

알고리즘의 수행 시간 #

• 수행 시간 = 각 연산의 수행 횟수의 합
• 수행 시간은 일반적으로 입력 크기(입력되는 데이터의 크기) n의 함수로 표현
• 데이터의 입력 상태에 따라 수행 시간은 달라진다.
• 알고리즘의 우열을 따질 경우에는 알고리즘의 수행 시간을 나타내는 식의 성장률 또는 차수만을 따지는 것이 일반적이며, 　따라서 입력 크기 n의 최고 차수만을 따지며 하위 차수와 상수는 모두 무시한다.

점근 성능 #

• 입력의 크기 n이 충분히 커질 때 알고리즘의 수행 시간이 무엇에 의해 좌우되는가를 나타내는 것 ( 수행 시간이 다항식으로 표현되는 경우에는 입력의 크기가 커짐에 따라 상수항과 차수가 낮은 항들의 역할이 감소하게 되고, 결국 n의 최고차항에 좌우된다.)
• 표기법
• ① “Big-oh” 점근적 상한 f(n) = O(g(n),
• ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)),

• ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))

• 시간 복잡도 함수 간의 크기 관계 → O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!)

Suggested Pages #

• 0.025 Graph Theory
• 0.025 Statistical Graph
• 0.025 Mathmetical Graph
• 0.025 Graph Data Structure
• 0.025 Computer Science
• 0.025 Graph Visualization
• 0.025 빅 데이터
• More suggestions...