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

1. 자료구조와 알고리즘

자료구조란?

데이터를 구성하고, 저장하고, 조작하는 방법을 정의하는 데 사용되는 일련의 방법 및 기술이다. 데이터를 효율적으로 조작하고 처리하기 위해 사용됩니다. 자료구조는 기본 데이터 타입(숫자, 문자 등)을 기반으로 하며, 이러한 기본 데이터 타입을 더 큰 덩어리로 묶는 방법을 제공합니다. 이렇게 묶은 데이터는 여러 가지 방법으로 저장, 관리 및 접근이 가능합니다. 자료구조는 다양한 알고리즘에 사용되며, 이를 통해 프로그램이 더욱 효율적으로 동작할 수 있습니다.

자료구조는 크게 단순 자료형 구조와 복합 자료구조로 구분할 수 있습니다. 단순 자료형 구조는 정수, 실수, 문자 등과 같은 기본적인 자료형을 말하며, 하나의 값만을 가지는 구조입니다. 반면 복합 자료구조는 여러 개의 단순 자료형을 조합하여 만들어진 자료구조로, 선형 구조와 비선형 구조로 나눌 수 있습니다.

선형 구조는 데이터를 일렬로 배열한 형태로, 배열 구조와 연결된 구조로 나뉩니다. 배열 구조는 메모리 상에 데이터를 연속적으로 배치한 구조로, 인덱스를 이용해 데이터에 접근할 수 있습니다. 반면, 연결된 구조는 포인터를 이용해 각각의 데이터를 서로 연결한 형태로, 메모리 상에 연속적으로 저장되어 있지 않아도 됩니다.

비선형 구조는 데이터를 계층 구조나 그래프 형태로 표현한 구조로, 트리와 그래프로 나뉩니다. 트리는 부모-자식 관계로 구성된 계층 구조로, 그래프는 정점과 간선으로 구성된 구조로, 간선을 이용해 정점들이 연결되어 있습니다.

또한, 자료구조에는 다양한 알고리즘이 존재합니다. 순환 알고리즘은 자료구조의 원소들을 순환하며 처리하는 알고리즘으로, 주로 반복문을 사용합니다. 정렬 알고리즘은 데이터를 정렬하는 알고리즘으로, 선택 정렬, 삽입 정렬, 버블 정렬 등이 있습니다. 탐색 알고리즘은 데이터에서 원하는 값을 찾는 알고리즘으로, 이진 탐색, 순차 탐색 등이 있으며, 고급 정렬 알고리즘은 퀵 정렬, 합병 정렬, 힙 정렬 등이 있습니다.

알고리즘이란?

알고리즘(Algorithm)은 어떤 문제를 해결하기 위한 일련의 절차나 방법을 의미합니다. 이러한 알고리즘은 주로 컴퓨터 과학 분야에서 사용되며, 입력값을 받아 출력값을 만들어내는 과정을 수행합니다. 알고리즘은 입력값의 크기에 따라 수행시간이 결정되며, 일반적으로 입력값의 크기가 증가할수록 수행시간도 증가합니다. 따라서 효율적인 알고리즘은 입력값의 크기가 크더라도 빠른 수행시간을 보장하므로, 컴퓨터 프로그래밍 및 문제해결에 매우 중요한 역할을 합니다.

2. 추상 자료형

추상 자료형이란?

추상 자료형은 데이터 타입의 추상화를 의미합니다. 즉, 데이터 타입이 가져야 할 속성과 연산을 정의한 것으로, 이를 이용해 구체적인 자료형을 구현할 수 있습니다. 추상 자료형은 구현과 사용을 분리하여 프로그램을 설계하고 구현하는 데 도움이 됩니다. 이를 통해 다른 프로그래머와 협업하기 쉽고, 코드의 유지보수성과 재사용성을 높일 수 있습니다. 추상 자료형의 대표적인 예로는 스택, 큐, 리스트, 집합, 맵 등이 있습니다.

3. 알고리즘의 성능 분석

알고리즘의 성능 분석 기법

알고리즘의 성능 분석 기법은 주로 실행시간 측정과 알고리즘 복잡도 분석으로 나눌 수 있습니다.

실행시간 측정: 실행시간 측정은 알고리즘의 속도와 성능을 측정하는 가장 직관적인 방법입니다. 알고리즘을 구현하고 입력 데이터를 대상으로 실행하여 소요된 시간을 측정하는 것입니다. 이 방법은 구현에 따라 정확도가 크게 달라질 수 있습니다.
알고리즘 복잡도 분석 알고리즘 복잡도 분석은 실행시간을 정확하게 측정하기 어려운 경우에 사용하는 방법입니다. 이 방법은 알고리즘의 입력 크기에 대한 실행시간의 증가율을 분석하여 알고리즘의 성능을 평가합니다. 이를 통해 알고리즘의 최악 실행 시간을 예측하고, 입력 크기가 매우 큰 경우에도 실행시간을 예측할 수 있습니다.

알고리즘 복잡도 분석은 보통 시간 복잡도와 공간 복잡도로 나눠집니다. 시간 복잡도는 알고리즘의 입력 크기에 따른 실행 시간 증가율을 분석하며, 대개 Big-O 표기법을 사용하여 나타냅니다. 공간 복잡도는 알고리즘이 사용하는 메모리 공간의 크기에 따른 증가율을 분석합니다.

[시간복잡도 함수]

알고리즘의 시간복잡도 함수는 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는 함수입니다. 이 함수는 입력 크기 n에 대한 알고리즘의 실행 시간을 예측하는데 사용됩니다. 일반적으로 입력 크기 n은 알고리즘에 전달되는 데이터의 양 또는 복잡도를 나타냅니다.

시간복잡도 함수는 주로 알고리즘을 분석하는 데 사용되며, 이를 통해 알고리즘의 실행 시간이 얼마나 빠르거나 느린지 예측할 수 있습니다. 대표적인 시간복잡도 함수로는 O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3) 등이 있습니다.

시간복잡도 함수는 알고리즘의 구현 방법, 실행 환경 등에 따라 달라질 수 있으며, 일반적으로 최악의 경우 시간복잡도를 계산합니다. 이를 통해 알고리즘의 성능을 효율적으로 분석하고 개선할 수 있습니다.

[빅오 표기법]

O(1) : 입력 크기와 무관하게 항상 일정한 실행 시간을 가지는 경우
O(log n) : 입력 크기가 증가함에 따라 실행 시간이 로그함수로 증가하는 경우
O(n) : 입력 크기에 비례하여 실행 시간이 증가하는 경우
O(n log n) : 입력 크기에 로그를 취한 값과 입력 크기의 곱에 비례하여 실행 시간이 증가하는 경우
O(n^2) : 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 경우
O(2^n) : 입력 크기의 지수함수에 비례하여 실행 시간이 증가하는 경우
O(n!) : 입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 경우

위의 표기법은 알고리즘의 성능을 분석하는데 사용되며, 입력 크기에 따른 알고리즘의 실행 시간의 증가 추이를 나타냅니다. O 표기법은 알고리즘의 성능을 비교하는 데 유용하며, 알고리즘의 실행 시간을 예측하는 데도 사용됩니다.

4. 시간 복잡도 분석: 순환 알고리즘

순환 알고리즘이란?

순환 알고리즘은 자신을 호출하여 반복적으로 실행되는 알고리즘입니다. 이러한 알고리즘은 일반적으로 재귀적으로 구현되며, 각 호출은 서로 다른 입력에 대해 작업을 수행합니다. 순환 알고리즘은 주로 트리, 그래프, 분할 정복 알고리즘 등에서 사용됩니다. 이러한 알고리즘은 문제를 더 작고 처리하기 쉬운 하위 문제로 분할하고, 하위 문제의 해결 방법을 결합하여 원래 문제의 해결책을 얻는 방식으로 작동합니다.

빅오 표기법으로 분석하는 시간 복잡도

실행시간에 영향을 주는 가장 큰 항 찾기
- 코드 상에서 가장 빈번하게 실행되는 연산을 찾습니다.
- 반복문이나 재귀 함수 등에서 가장 많이 반복되는 코드 블록 등을 찾습니다.
상수항과 낮은 차수 항 제외
- 빅오 표기법에서는 실행시간에 큰 영향을 주지 않는 상수항과 낮은 차수 항은 제외합니다.
- 즉, O(n)과 O(2n)은 동일한 복잡도를 가집니다.
- 따라서 가장 큰 항만 남기고 나머지는 제외합니다.
빅오 표기법으로 표현
- 가장 큰 항이 남으면, 해당 항의 차수를 빅오 표기법으로 표현합니다.
- 상수항과 낮은 차수 항이 제외되었기 때문에, 해당 항의 계수는 무시됩니다.

예) 다음과 같은 코드가 있다고 가정해봅시다.

def sum_elements(arr):
    n = len(arr)
    result = 0
    for i in range(n):
        result += arr[i]
    return result

위 코드의 복잡도를 빅오 표기법으로 분석하면 다음과 같습니다.

실행시간에 영향을 주는 가장 큰 항 찾기
- 반복문에서 가장 많이 반복되는 코드 블록은 result += arr[i] 입니다.
- 따라서 이 연산이 실행되는 횟수에 따라 실행시간이 결정됩니다.
상수항과 낮은 차수 항 제외
- 반복문이 한 번 실행될 때마다 result += arr[i] 연산이 수행됩니다.
- 따라서 이 코드의 실행시간은 n에 비례합니다.
- 상수항과 낮은 차수 항이 없으므로, 해당 항만 남깁니다.
빅오 표기법으로 표현
- 가장 큰 항은 n입니다.
- 따라서 이 코드의 복잡도는 O(n)입니다.

연습문제

난이도에 맞지 않는 문제도 몇 있습니다. 자료구조 전체 강의 수강 후 풀어보시는걸 추천드립니다.

[문제 1.] 다음 중 추상 자료형(Abstract Data Type)의 특징이 아닌 것은? a. 내부 구현이 외부에 노출되지 않는다. b. 자료의 추상적인 특성을 강조한다. c. 동일한 추상 자료형에 대한 여러 구현이 가능하다. d. 자료구조의 성격과 기능을 모두 포함한다.

[문제 2.] 다음 중 선택 정렬의 시간 복잡도에 대한 설명으로 옳지 않은 것은? a. 최악의 경우에도 O(n^2)의 시간 복잡도를 가진다. b. 배열의 크기에 따라 비교 횟수는 변하지 않는다. c. 이동 횟수는 배열의 정렬 여부와 무관하게 일정하다. d. 별도의 메모리 공간이 필요하지 않다.

[문제 3.] 다음 중 연결 리스트의 특징으로 옳은 것은? a. 물리적으로 연속된 메모리 공간에 저장된다. b. 배열과 달리 데이터 삽입/삭제가 용이하다. c. 인덱스를 통해 데이터에 직접 접근할 수 있다. d. 순차 탐색을 이용하여 효율적으로 탐색할 수 있다.

[문제 4.] 다음 순환 알고리즘 중 최대공약수(GCD)를 구하는 알고리즘은? a. 버블 정렬 알고리즘 b. 선택 정렬 알고리즘 c. 삽입 정렬 알고리즘 d. 유클리드 호제법 알고리즘

[문제 5.] 다음 중 시간 복잡도 분석에서 O(n)으로 표기할 수 있는 알고리즘은? a. 선택 정렬 알고리즘 b. 버블 정렬 알고리즘 c. 삽입 정렬 알고리즘 d. 선형 탐색 알고리즘

[문제 6.] 다음 중 순환 알고리즘의 예시가 아닌 것은? a. 퀵 정렬 b. 이진 탐색 c. 타워 of 하노이 d. 이진 트리 순회

[문제 7.] 다음 중 선택 정렬의 시간 복잡도를 올바르게 표현한 것은? a. O(n) b. O(n^2) c. O(log n) d. O(n log n)

[문제 8.] 다음 중 스택의 특징이 아닌 것은? a. 후입선출(LIFO) 구조 b. 삽입(insert)과 삭제(pop) 연산만 수행 가능 c. 큐와 비슷한 구조 d. 배열과 연결 리스트로 구현 가능

[문제 9.] 다음 중 연결 리스트에 대한 설명으로 옳지 않은 것은? a. 메모리를 연속적으로 사용하지 않아도 되어 삽입과 삭제가 용이하다. b. 노드간의 포인터 연결로 구현되어 있다. c. 인덱스를 이용한 접근이 가능하다. d. 단방향, 양방향, 원형 등 다양한 형태로 구현 가능하다.

[문제 10.] 다음 중 분할 정복 알고리즘에 대한 설명으로 옳은 것은? a. 문제를 작은 부분으로 분할하여 각각 해결한 후 결과를 합쳐 최종 결과를 얻는 알고리즘이다. b. 실행 시간은 입력 크기에 비례하여 지수적으로 증가한다. c. 가장 작은 문제가 될 때까지 문제를 계속해서 쪼갠다. d. 선택 정렬, 삽입 정렬, 버블 정렬 등의 정렬 알고리즘에 사용된다.

[정답]

-연습문제