자료구조,알고리즘,시간복잡도,공간복잡도,BigO,점근표기법,추상데이터타입,ADT,프로그래밍기초
| 자료구조 & 알고리즘 기초 정리 |
프로그래밍의 기초가 되는 자료구조와 알고리즘의 핵심 개념을 정리합니다. 처음 보면 막막하지만, 분류와 흐름을 잡아 두면 이해가 한결 수월해집니다.
목차
자료구조란?
자료구조(Data Structure)는 효율적인 접근과 수정을 위해 자료를 조직·관리·저장하는 방식을 말합니다. 즉 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미합니다.
자료구조의 분류
| 분류 | 종류 |
| 단순 구조 | 정수, 실수, 문자, 문자열 |
| 선형 구조 | 순차 리스트, 연결 리스트(단순·이중·원형), 스택, 큐, 덱(deque) |
| 비선형 구조 | 트리(일반·이진), 그래프(방향·무방향) |
| 파일 구조 | 순차, 색인, 직접 |
알고리즘
알고리즘은 문제를 해결하기 위한 절차나 방법, 즉 어떤 행동을 하기 위해 만들어진 명령어들의 유한 집합입니다. 다음 요건을 만족해야 합니다.
| 요건 | 의미 |
| 입력 | 0개 이상의 외부 자료가 존재 |
| 출력 | 최소 1개 이상의 결과를 가짐 |
| 명확성 | 각 단계는 명확하고 애매함이 없어야 함 |
| 유한성 | 유한한 횟수의 단계 후 종료해야 함 |
| 효과성 | 각 연산은 종이와 연필로 수행 가능할 만큼 충분히 단순해야 함 |
알고리즘 표현 방법
- 자연어 – 일상 언어로 표현
- 의사코드(pseudocode) – 자연어를 프로그래밍 언어처럼 표현
- 순서도 – 정의된 기호·도형으로 표현
- 프로그래밍 언어 – 실제 코드로 표현
알고리즘 성능 분석
성능은 주로 Big-O 표기법으로 나타내며, 공간과 시간 두 측면으로 분석합니다.
- 공간 복잡도 – 프로그램 실행에 필요한 자원 공간의 양. (고정 공간 + 가변 공간)
- 시간 복잡도 – 알고리즘 실행을 완료하기까지 총 소요 시간. (컴파일 시간 + 실행 시간)
컴파일 시간은 프로그램마다 거의 고정적이고, 실행 시간은 컴퓨터 성능에 따라 달라지므로, 보통 명령문의 실행 빈도수로 계산합니다. 시간도 적게 쓰고 자원도 적게 쓰는 것이 가장 최적이며, 대부분의 경우 시간 복잡도를 기준으로 사용합니다.
분석의 4종류
| 종류 | 설명 |
| 최악 경우 | 어떤 입력에도 수행 시간이 일정 이상을 넘지 않는다는 상한(Upper Bound) |
| 평균 경우 | 입력의 확률 분포(보통 균등 분포)를 가정해 분석 |
| 최선 경우 | 가장 빠른 수행 시간을 분석 |
| 상각 분석 | 일련의 연산 총 횟수를 합해 연산 횟수로 나누어 분석 |
점근 표기법(Asymptotic Notation)
수행 시간은 기본 연산 횟수를 입력 크기에 대한 함수(다항식)로 표현하는데, 이를 입력 크기에 대해 나타내기 위해 점근 표기법을 사용합니다.
- Big-O – 상한(Upper Bound)
- Big-Omega(Ω) – 하한(Lower Bound)
- Theta(Θ) – 상·하한이 일치하는 경우
세 표기법의 자세한 설명은, 빅오 표기법을 유머와 함께 잘 풀어 둔 이 글을 참고하면 좋습니다.
추상 데이터 타입(ADT)
추상 데이터 타입(Abstract Data Type)은 유사한 작동을 하는 데이터 구조 집합, 또는 프로그래밍 언어에서의 특정 데이터 구조를 위한 수학적 모델입니다. 컴퓨터 과학에서 자료들과 그 자료에 대한 연산들을 가리킵니다.
- 추상화 = "What" – 무엇인지 논리적으로 정의
- 구체화 = "How" – 어떻게 할지 실제로 표현
크고 복잡한 문제를 단순화해 쉽게 해결하기 위한 방법이 추상화이며, 자료 추상화는 처리할 자료·연산·자료형에 대한 추상화를 표현합니다.
| 용어 | 정의 |
| 데이터 | 의미 있는 정보를 가진 모든 값 |
| 데이터 타입 | 데이터의 집합 + 적용 가능한 연산의 집합 (예: 정수 −1·0·1, 연산 +·−·×) |
| 추상 데이터 타입 | 자료 구조를 추상적·수학적으로 정의한 것 |
알아두면 유용한 사이트
- 백준 온라인 저지(BOJ) – 알고리즘 문제 풀이
- codeground.org – 코딩 테스트 연습
출처: 위키백과, 나무위키 / 『자바와 함께하는 자료구조의 이해』(양성봉, 생능출판)