분류:알고리즘

알고리즘의 정의에 대해선 알고리즘 문서를 참고하세요. 이 분서는 분류로서의 알고리즘을 다룹니다.

어디까지가 '알고리즘'인가?[편집 | 원본 편집]

컴퓨터 과학에서 다루는 문제의 종류

• Problems-in-the-large (대형 문제): 은행 대출 시스템, 컴파일러, 게임 처럼 큰 소프트웨어 시스템과 관련된 문제.
• Problems-in-the-small (소형 문제): 정렬(Sorting), 행렬 곱셈, 선형 계획법 같은 수학적으로 명확히 정의된 문제.
• 알고리즘 학문(Algorithmics)은 이러한 소형 문제와 그 해결 방법을 연구하는 분야임.

알고리즘 연구의 두 가지 방향

• 응용 중심 (열 중심, column-oriented): 특정 응용 분야(예: 계산 기하학, 계산 생물학)에서 사용하는 알고리즘 연구
• 기술 중심 (행 중심, row-oriented): 정렬, 그래프 탐색, 동적 프로그래밍 같은 공통 알고리즘 기법을 연구

학문으로서의 알고리즘이란?

• 알고리즘이란 계산 문제를 효율적으로 해결하는 방법을 연구하는 학문이다.
• 알고리즘 연구는 알고리즘 설계 기법, 자료구조, 알고리즘 분석을 위한 수학적 도구 등을 포함한다.
• 컴퓨터 소프트웨어의 핵심 요소로서, 다양한 응용 시스템에서 중요한 역할을 한다.
• 대형 소프트웨어 시스템을 구축하기 위해서는 알고리즘뿐만 아니라 데이터베이스 이론과 같은 비알고리즘적 기법도 필요하지만, 본 교재에서는 알고리즘에 집중한다.

알고리즘에서 다루는 것들[편집 | 원본 편집]

응용 중심 접근 (Application-Oriented View)

• 특정 분야에서 활용되는 알고리즘 연구. 예를 들어,
  • 계산 기하학 (Computational Geometry)
  • 계산 생물학 (Computational Biology)
  • 계산 금융 (Computational Finance)
  • 컴퓨터 대수학 (Computer Algebra)

기술 중심 접근 (Technique-Oriented View)

• 특정 분야에 국한되지 않고 여러 분야에서 공통적으로 사용되는 기법 연구. 예를 들어,
  • 정렬 (Sorting)
  • 그래프 탐색 (Graph Searching)
  • 문자열 알고리즘 (String Algorithms)
  • 동적 프로그래밍 (Dynamic Programming)
  • 수치 해석 기법 (Numerical Methods)

알고리즘 연구 주제들

세부 주제들은 더 있지만, 큰 분류는 이렇게 이렇게 4가지 주요한 주제로 나눌 수 있다.

1. 자료구조 (Data Structures)
   • 연결 리스트 (Linked Lists)
   • 스택 (Stacks)
   • 탐색 트리 (Search Trees)
2. 알고리즘 기법 (Algorithmic Techniques)
   • 분할 정복 (Divide and Conquer)
   • 동적 프로그래밍 (Dynamic Programming)
3. 기본 계산 문제 (Basic Computational Problems)
   • 정렬 (Sorting)
   • 그래프 탐색 (Graph Searching)
   • 점 위치 찾기 (Point Location)
4. 알고리즘 분석 기법 (Analysis Techniques)
   • 점화식 (Recurrences)
   • 상쇄 분석 (Amortization)
   • 확률적 분석 (Randomized Analysis)