자료구조
- 선형 자료구조
- 항목들을 순서적으로 나열하여 저장
- 리스트: 가장 자유로운 선형 자료구조
- 스택, 큐, 덱: 항목의 접근이 맨 앞(전단)이나 맨 뒤(후단)로 제한
- 비선형 자료구조
- 항목들이 보다 복잡한 연결 관계를 가짐
- 트리: 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조
- 그래프: 가장 복잡한 연결 관계를 표현
알고리즘
- 컴퓨터로 문제를 풀기 위한 단계적인 절차
- 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 이해할 수 있는 언어로 기술한 것
- 프로그램 = 자료구조 + 알고리즘
조건
- 입력: 0개 이상의 입력이 존재하여야 함
- 출력: 1개 이상의 출력이 존재해야 함
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함
- 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함
- 유효성: 각 명령어들은 실행 가능한 연산이어야 함
기술 방법
자연어
- 일반적인 자연어를 사용해서 설명하듯이 알고리즘을 표현
- 일반 사람이 이해하기 쉽게 표현할 수 있으나, 최종적으로 코드로 변경하는 데는 한계가 있음
- 어떤 알고리즘을 사용해야 할지 아이디어가 떠오르지 않는 시점에서, 생각 범위를 넓히는 단계 정도에 사용
흐름도
- 여러 종류의 상자와 상자를 이어주는 화살표를 이용해서 명령 순서를 표현
- 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많음
유사코드
- 프로그래밍 언어보다는 좀 더 인간의 언어에 가까운 형태
- 프로그램 코드와 일반 언어의 중간 형태
- 프로그램 코드를 직접 코딩하는 것보다 알고리즘을 좀 더 명확하게 정립하는 데 도움이 되고 코드에 설명을 달지 않아도 이해하는 데 무리 없음
특정 언어
- 실제로 사용하는 프로그래밍 언어의 코드로 바로 작성 가능
- 알고리즘의 가장 정확한 기술 가능
- 구현 시의 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해
- 파이썬: C나 자바보다 훨씬 간결한 표현 가능
추상 자료형
- 데이터와 그 데이터에 대한 추상적인 연산들로써 구성
- 데이터나 연산이 무엇인가를 정의함
- 데이터나 연산을 어떻게 구현할 것인지는 정의하지 않음
- 자료구조는 추상 데이터 타입을 구체적(실제 프로그램)으로 구현한 것
알고리즘의 성능 분석
- 실행 시간 측정
- 두 개의 알고리즘의 실제 실행 시간을 측정
- 실제로 구현하는 것이 필요
- 동일한 하드웨어 사용
- 복잡도 분석
- 직접 구현하지 않고서도 수행 시간을 분석
- 알고리즘이 수행하는 연산의 횟수를 측정하며 비교
- 일반적으로 연산의 횟수는 n의 함수
- 시간 복잡도 분석: 연산 수행 시간 분석
- 공간 복잡도 분석: 수행 시 필요로 하는 메모리 공간 분석
빅오 표기법
- 차수가 가장 큰 항이 절대적인 영향
- 다른 항들은 상대적으로 무시
- 빅오 표기법: 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n₀에 대해 |f(n)| ≤ c|g(n)|을 만족하는 상수 C와 n₀가 존재하면 f(n) = O(g(n))
최선 / 평균 / 최악
- 최선: 수행 시간이 가장 빠름 / 의미가 없는 경우가 많음
- 평균: 수행 시간이 평균적인 경우 / 계산하기가 상당히 어려움
- 최악: 수행 시간이 가장 늦은 경우 / 가장 널리 사용되며, 계산하기 쉽고 응용에 따라서 중요한 의미를 가짐
순환 알고리즘
- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
- 정의 자체가 순환적으로 되어 있는 경우에 적합
- 팩토리얼 구하기, 피보나치 수열, 이항 계수, 하노이의 탑, 이진 탐색 등
- 대부분의 순환은 반복으로 바꾸어 작성할 수 있음
- 반복의 경우 for나 while문이 이용되고 수행속도가 빠르지만 순환적인 문제에서는 프로그램 작성이 어려울 수 있음
