[자료구조] 1. 자료구조와 알고리즘의 이해

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다.

 

1. 자료구조에 대한 기본적인 이해

📌 자료구조

데이터의 표현 및 저장 방법

 

✍🏻 자료구조의 분류

• 선형 자료구조 : 자료를 표현하고 저장하는 방식이 나란히 또는 일렬로 저장하는 방식
• 비선형 자료구조 : 자료를 표현하고 저장하는 방식이 나란하지 않게 저장하는 방식

 

📌 알고리즘

표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법

• 자료구조에 따라 알고리즘을 달라진다.
• 알고리즘은 자료구조에 의존적이다.

 

2. 알고리즘의 성능 분석 방법

2-1. 시간 복잡도와 공간 복잡도

✍🏻 알고리즘을 평가하는 두 가지 요소

1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느리냐
2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐

즉, 하나는 속도에 관한 것, 다른 하나는 메모리의 사용량에 관한 것

 

📌 시간 복잡도 (Time complexity)

알고리즘을 실행하는 데 필요한 시간

📌 공간 복잡도 (Space complexity)

알고리즘을 실행하는 데 필요한 메모리 공간

• 메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라고 할 수 있다.
• 하지만 일반적으로 알고리즘을 평가할 때는 메모리 사용량보다 실행 속도에 초점을 맞춘다.
• 따라서 알고리즘의 수행 속도를 평가할 때는 연산의 횟수를 세고, 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

 

✍🏻 시간 복잡도의 평가 기준

• 알고리즘을 평가할 때 '최선의 경우'는 대부분 만족스러운 결과를 보여 관심 대상이 아니다.
• 데이터의 수가 많아지면 '최악의 경우'에 수행하는 연산의 횟수는 알고리즘에 따라 크게 달라지므로 성능 판단의 기준이 된다.
• 평균적인 경우는 분석에 필요한 여러 시나리오와 데이터를 합리적으로 구성해야 하는데 쉽지 않으므로 활용하지 않는다.

 

2-2. 이진 탐색 알고리즘

📌 이진탐색 (Binary Search)

정렬된 배열이나 리스트에서 특정한 값을 효율적으로 찾기 위한 검색 알고리즘

• 배열이 반드시 정렬된 상태여야 한다.
• 시간 복잡도 : O(log n)

✍🏻 이진탐색 동작 원리

1. 배열의 가운데 요소를 선택하고, 찾고자 하는 타겟 값과 일치하는지 확인
2. 타겟 값이 가운데 값보다 작으면 왼쪽 하위 배열에서 탐색, 크면 오른쪽 하위 배열에서 탐색을 반복
3. 위의 과정을 통해 값을 찾거나, 검색 범위가 비어 있을 때까지 반복

 

2-3. 빅-오 표기법

📌 빅-오 표기법 (Big-Oh Notation)

입체 크기에 따른 연산 횟수의 증가 형태를 표현하는 방법

• 최악의 경우 분석 : 빅오 표기법은 알고리즘의 최악의 실행 시간을 나타냄
• 상수 및 낮은 차수 제거 : 성능에 미치는 큰 영향에 집중하기 위해 상수 계수나 차수가 낮은 항을 생략
• 알고리즘의 효율성을 비교하고, 입력 크기가 매우 커질 때 성능을 예측하는 데 유용

 

✍🏻 대표적인 빅-오

• O(1) : 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘
• O(log n) : 로그형 빅-오, 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘
• O(n) : 선형로그형 빅-오, 데이터의 수와 연산 횟수가 비례하는 알고리즘
• O(n log n) : 선형로그형 빅-오, 데이터의 수가 두 배로 늘 때 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘
• O(n²) : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘 (이중 중첩 반복문)
• O(n³) : 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘 (삼중 중첩 반복문)
• O(2^n) : 지수형 빅-오

 

참고자료

책 - 윤성우의 열혈 자료구조 (2012년 1월)