[Python Algorithm] Ch1. 알고리즘 개요

1.1 알고리즘이란?

알고리즘

주어진 문제를 해결하기 위한 단계적 절차(명령어들의 집합)

• 명령어: 컴퓨터에서 수행되는 문장
• 알고리즘이 되기 위한 조건: 입력, 출력, 명확성, 유한성, 유효성
• 한 문제를 풀기 위한 알고리즘은 여러 개가 존재

알고리즘의 기술 방법

1. 자연어: 영어, 한국어 등
2. 흐름도(flow chart)
3. 유사코드(슈도 코드)
4. 프로그래밍 언어(Python, C 등)

1.2 문제 해결 과정

알고리즘 개발 과정

1. 문제의 이해
   • 문제를 정확히 이해하고, 모호성을 없앰
2. 개발 방향 결정
   • 계산 장치의 특성에 따른 알고리즘의 결정: 순서적 알고리즘과 병렬처리 알고리즘
   • 해를 구하는 방식: 최적해와 근사해
3. 알고리즘 설계 기법
   • 억지기법, 완전탐색, 축소정복, 분할정복, 그리디 기법, 백트래킹 등
4. 알고리즘의 정확성 검증
   • 유효한 입력에 대해 유한한 시간 내에 정확한 해를 구하는가?
   • 검증법: 실험적 분석(사례 입력), 증명적인 분석
5. 알고리즘 분석(효율성 검사)
   • 해당 알고리즘이 얼마나 효율적으로 동작하는가?
   • 효율성 종류: 시간 효율성, 공간 효율성, 코드 효율성
6. 알고리즘의 구현
   • 검증이 완료된 알고리즘을 특정 언어로 구현

1.3 중요한 문제의 유형들

정렬

데이터를 순서대로 재배열하는 문제

• 사물들이 서로 비교가 가능해야 함
• 자료의 탐색에서 중요
• 레코드를 키(key)의 순서대로 재배열 하는 것
  • 레코드: 정렬 대상
  • 필드: 하나의 레코드는 여러 필드로 이루어짐
  • 키(정렬 키): 정렬의 기준이 되는 필드
• 정렬을 위한 알고리즘: 삽입, 선택, 버블 정렬, 퀵, 힙 정렬 등

탐색

주어진 레코드의 집합에서 원하는 값을 가진 레코드(탐색 키)를 찾는 작업

• 순차탐색, 이진탐색, 해싱 등

문자열 처리

숫자가 아닌 데이터인 문자열을 처리하는 작업

• 대표적인 문제로는 택스트에서 어떤 단어를 찾는 문자열 매칭 문제

그 외 문제들

• 그래프 문제: 순회문제, 위상정렬, 최단경로 문제 등
• 조합 문제: 어떤 조건을 만족하는 순열, 조합, 부분집합과 같은 조합 객체를 찾는 문제
• 기하학적 문제: 점, 선, 다각형 등 기하학적 객체에 관한 문제

1.4 기본적인 자료구조와 파이썬

자료구조

자료들을 정리하고 조직화하는 여러 가지 구조

• 단순 자료구조: 정수, 실수, 문자 등
• 복합 자료구조: 여러 개의 자료를 모은 창고
  • 배열 구조(인접한 메모리 공간에 나열), 연결된 구조(자료들을 연결고리(링크)를 이용해 연결)
  • 선형구조, 비선형 구조

선형 자료구조

항목들을 순서적으로 나열하여 저장하는 형태

• 항목들을 접근하는 방법에 따라 리스트, 스택, 큐, 덱 등으로 나뉨

비선형 자료구조

항목들을 일렬로 나열하여 저장하지 않는 구조

• 그래프, 트리, 우선순위 큐 등