본문 바로가기

컴퓨터과학개론_이관용, 정광식16

3.3 알고리즘의 분석 3.3 알고리즘의 분석 알고리즘의 설계를 마친 후 - 그 알고리즘이 원하는 결과를 정확히 생성하는지 확인해야 함. - 해당 알고리즘을 수행하기 위해서 얼마나 많은 컴퓨터 자원을 필요로 하는지의 효율성을 분석 필요. (정확성 + 효율성) 3.3.1 정확성 분석 정확한 알고리즘은 유효한 입력이 주어졌을 때 유한 시간 내에 원하는 정확한 결과를 생성해야 함. - 올바른 정확성 분석을 위해서는 다양한 수학적 기법을 사용해서 알고리즘이 예상한 대로 수행되는지에 대한 증명 방법을 개발 필요. 3.3.2 효율성 분석 알고리즘 분석 - 정확성 분석보다는 알고리즘이 주어진 문제를 시간적으로 또는 공간적으로 얼마나 효율적으로 풀 수 있는지에 대한 분석을 의미. - 효율적인 알고리즘이란 가능한 한 적은 메모리와 더 빠른 수.. 2022. 12. 25.
3.2 알고리즘의 설계 3.2 알고리즘의 설계 - 순차 탐색(sequential search)- 원하는 데이터를 찾는 방법 - 데이터가 주어지는 상태에 따라 적용되는 알고리즘이 충분히 달라짐 -> 주어진 문제마다 조건과 특성 등을 고려해 각각의 알고리즘을 설계해야 함. - 방법: 분할정복(divide and conquer) 방법, 동적 프로그래밍(dynamic programming) 방법, 욕심쟁이(greedy) 방법 3.2.1 분할정복 방법 분할정복 방법 - 순환적으로 문제를 푸는 방법. 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적으로(recursively) 분할하고, 이렇게 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법 • 분할(div.. 2022. 12. 18.
3.1 알고리즘의 개념 3.1 알고리즘의 개념 알고리즘(algorithm) - 주어진 문제를 해결하기 위한 단계적인 풀이 과정의 모임 : 컴퓨터과학을 알고리즘과 관련된 이슈를 다루는 학문 3.1.1 알고리즘의 정의 비정형적으로 알고리즘 - 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것 이론적인 측면으로 컴퓨터를 사용한 문제 해결의 가능성이므로 아래의 조건을 모두 만족해야 함 - 입출력(input & output): 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 함. - 명확성(definiteness): 각 명령은 모호하지 않고 단순 명확해야 함. - 유한성(finiteness): 한정된 수의 단계를 거친 후에는 반드시 종료해야 함. - 유효성(effectiveness): 모든 명령은 컴퓨터에서 실행 가능해야 함.. 2022. 12. 11.
2.6 그래프 2.6.1 그래프의 개념과 용어 그래프 G는 정점(vertex)들의 유한집합 V와 2개의 정점을 연결하는 간선(edge)들의 유한집합 E로 정의. (G=(V, E)로 표시) 방향 그래프(directed graph, digraph) - 두 정점을 연결하는 간선이 방향성을 가짐 무방향 그래프(undirected graph) - 간선에 방향성이 없음 위 그림을 집합으로 표현하면 다음과 같다. V(Gi)={1, 2, 3, 4} E(G₁)= {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} V(G2)={1, 2, 3, 4} E(G₂) = {, ,,,,} 무방향 그래프의 간선 - '(', ‘)’로 표현 방향 그래프의 간선 - ‘’로 표현 두 정점이 간선으로 직접 연결 - 인접(.. 2022. 12. 4.

티스토리툴바