연관학습은 알고리즘
• 자료구조와 알고리즘
* 알고리즘algorithm
- 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차를 의미합니다.
- 자료구조가 데이터를 효율적으로 저장하고 관리하기위한 방법을 다룬다면, 알고리즘은 어떤목적을 이루기위한 효율적인 연산방법을 다룬다고 볼 수 있습니다.
-이트리의 순회, 깊이우선탐색, 너비 우선탐색, 최단 경로 알고리즘
- 어떤 자료구조가 사용되었느냐에 따라 사용 가능한 알고리즘이 달라질 수 있음
- 알고리즘의 일종인 너비 우선 탐색과 깊이 우선 탐색은 그래프, 스택 등의 자료구조를 알고 있어야됨
• 시간 복잡도와 공간 복잡도
개발자는 프로그램을 만드는 과정에서 소스 코드를 통해 다양한 데이터를 다루고(자료구조), 그 데이터를 활용해 특정 목적을 이루기 위한 연산(알고리즘)을 구현합니다. 따라서 자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 품질 좋은 코드가 될 가능성이 높습니다. 실제로 같은 목적을 위한 코드라 하더라도 자료구조와 알고리즘을 고려했는지 여부에 따라 극명한 성능의 차이를 보일 수 있습니다.
그렇다면 자료구조와 알고리즘의 고려 여부에 따른 성능의 차이는 어떻게 판단할 수 있을까요?
바로 시간 복잡도와 공간 복잡도를 통해 알 수 있습니다. 시간 복잡도와 공간 복잡도는 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도입니다.
시간 복잡도time complexity란 입력의 크기에 따른 프로그램 실행 시간의 관계를 의미합니다.
프로그램의 실행 시간과 입력의 크기는 서로 밀접한 관계가 있습니다.
가령 ‘서로 다른 N개의 데이터가 있을 때, 앞에서부터 차례대로 하나씩 검사하여 특정 데이터를 찾는 프로그램’이 있다고 가정해 봅시다. 데이터가 하나(N=1)라면 프로그램의 실행 시간이 길지 않겠죠. 그러나 데이터가 100개(N=100)라면 일반적으로 조금 더 오랜 시간이 소요될 것입니다. 나아가 N이 10,000이라면 실행 시간이 평균적으로 훨씬 더 오래 걸릴 것입니다.
• 시간 복잡도와 공간 복잡도
개발자는 프로그램을 만드는 과정에서 소스 코드를 통해 다양한 데이터를 다루고(자료구조), 그 데이터를 활용해 특정 목적을 이루기 위한 연산(알고리즘)을 구현합니다. 따라서 자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 품질 좋은 코드가 될 가능성이 높습니다. 실제로 같은 목적을 위한 코드라 하더라도 자료구조와 알고리즘을 고려했는지 여부에 따라 극명한 성능의 차이를 보일 수 있습니다.
그렇다면 자료구조와 알고리즘의 고려 여부에 따른 성능의 차이는 어떻게 판단할 수 있을까요? 바로 시간 복잡도와 공간 복잡도를 통해 알 수 있습니다. 시간 복잡도와 공간 복잡도는 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도입니다.
시간 복잡도time complexity란 입력의 크기에 따른 프로그램 실행 시간의 관계를 의미합니다. 프로그램의 실행 시간과 입력의 크기는 서로 밀접한 관계가 있습니다. 가령 ‘서로 다른 N개의 데이터가 있을 때, 앞에서부터 차례대로 하나씩 검사하여 특정 데이터를 찾는 프로그램’이 있다고 가정해 봅시다. 데이터가 하나(N=1)라면 프로그램의 실행 시간이 길지 않겠죠. 그러나 데이터가 100개(N=100)라면 일반적으로 조금 더 오랜 시간이 소요될 것입니다. 나아가 N이 10,000이라면 실행 시간이 평균적으로 훨씬 더 오래 걸릴 것입니다.
이때 실행 시간은 연산의 횟수에 비례한다고 간주합니다. N이 1일 때보다 100일때 일반적으로 더 많은 연산이 필요할 것이고, N이 100일 때보다 10,000일 때 더 많은 연산이 필요할 테니까요. 따라서 시간 복잡도는 입력의 크기에 따른 프로그램 실행 시간이라고 할 수도 있고, 입력의 크기에 따른 연산 횟수라고 할 수도 있습니다.
그럼 이번에는 소스 코드로 시간 복잡도를 이해해 보겠습니다. 예를 들어 다음과 같은 코드에서 ‘1+1’이 ‘한 번의 연산'을 의미한다고 생각해 볼게요. 그럼 다음 코드에는 몇 번의 연산이 필요할까요? 너무 쉽습니다. 다섯 번의 연산이 필요하겠죠.
1+1
1+1
1+1
1+1
1+1
코드를 반복문으로 일반화하여 표현해 보겠습니다. 다음과 같은 코드에서 n은 입력으로 주어진 데이터라고 가정할게요. 어떤 프로그래밍 언어인지는 중요하지 않습니다. 주석으로 남긴 의미만 파악해 보기 바랍니다. 다음 코드에는 몇 번의 연산이 필요할까요? n번의 연산이 필요할 것입니다.
for _ in range(n): # 입력으로 주어진 값은 n; n회 반복하며
1 + 1 # 한 번씩 연산
같은 맥락에서 다음 코드에는 2n번의 연산이 필요합니다. 입력으로 주어진 n에 2를 곱한 만큼 반복하며 ‘1+1’을 연산하기 때문입니다.
for _ in range(2 * n): # 입력으로 주어진 값은 n; 2n회 반복하며
1 + 1 # 한 번씩 연산
다음 코드에는 n2번의 연산이 필요합니다. 2개의 반복문이 겹쳐 있기 때문입니다. 다시 말해, ‘n번씩 반복하며 한 번씩 연산하는 것’을 n번 반복하기 때문입니다(n × n). 마찬가지로 3개의 반복문이 겹쳐 있다면 n3번의 연산이 필요하겠죠.
for _ in range(n): # 입력으로 주어진 값은 n; n회 반복하며
for _ in range(n): # 각각의 반복을 n회씩 반복하며
1 + 1 # 한 번씩 연산
마지막으로 다음 코드에서는 몇 번의 연산이 필요할까요? 답은 (n2 + 3n + 2)번입니다.
for _ in range(n): # 입력으로 주어진 값은 n; n회 반복하며
for _ in range(n): # 각각의 반복을 n회씩 반복하며
1 + 1 # 한 번씩 연산
for _ in range(3 * n): # 입력으로 주어진 값은 3; 3n회 반복하며
1 + 1 # 한 번씩 연산
1 + 1 # 한 번씩 연산
1 + 1 # 한 번씩 연산
지금까지의 예제에서는 n의 값이 결정되면 코드의 연산 횟수 및 실행 시간도 함께 결정되었습니다. 하지만 현실 속 대부분의 프로그램은 예제처럼 입력의 크기가 결정된다고 해서 연산 횟수와 실행 시간이 무조건적으로 결정되지는 않습니다. 실제로는 입력하는 n이 같다고 하더라도 프로그램의 연산 횟수와 실행 시간이 달라질 수 있죠.
앞에서 가정했던 ‘서로 다른 N개의 데이터에서 특정 데이터를 찾는 프로그램’을 다시 생각해 봅시다. N이 100이라면 ‘일반적으로’, N이 10,000이라면 ‘평균적으로’ 더 오랜 실행 시간이 소요된다고 설명했습니다. ‘일반적으로’, ‘평균적으로’라는 사족을 붙인 이유는 그렇지 않은 경우도 있기 때문입니다. N이 10,000이더라도 ‘최선의 경우’, 운 좋게 단번에 원하는 데이터를 찾아낼 수도 있고, N이 100이더라도 ‘최악의 경우’, 데이터를 찾는 모든 연산을 끝내야만 원하는 데이터를 찾아낼 수도 있습니다.
그러나 상황에 따라 동일한 입력에 대한 프로그램의 실행 시간이 들쑥날쑥해서는 곤란하겠죠.
제대로 된 성능 판단 척도로서의 기능을 할 수 없을 것입니다.
그래서 시간 복잡도를 표현할 때에는 대중적으로 빅 오 표기법big O notation이 사용됩니다.
빅 오 표기법은 함수의 점근적 상한을 표기하는 방법입니다.
시간 복잡도를 표현하기 위해 빅 오 표기법을 사용한다면 ‘입력에 따른 실행 시간의 점근적 상한’을 의미하는 것입니다.
그렇다면 점근적 상한이란 무엇일까요?
입력하는 n이 점점 증가하여 무한대로 커진다고 생각해 보세요. n에 따라 일반적으로 실행 시간도 점점 증가할 것입니다. 이때 실행 시간이 증가하는 데에도 한계가 있습니다. 이 한계를 점근적 상한이라고 합니다. 입력의 크기 n에 대한 빅 오 표기법은 흔히 실행 시간의 O(상한(n)) 형태로 표현되며, 이는 쉽게 말해 입력하는 n이 점점 증가해 무한대로 커진다고 하더라도 실행 시간이 대략 이 이상(상한)은 커지지 않을 것이라는 의미입니다. 예를 들어, 시간 복잡도에서 빅 오 표기법으로 표현된 O(n2)은 입력값 n이 증가하더라도 실행 시간의 증가율이 n2보다는 작다는 것을 표현합니다.
앞서 살펴본 ‘서로 다른 n개의 데이터에서 특정 데이터를 찾는 프로그램’에 적용해 보겠습니다. 프로그램에서 데이터를 한 번 찾아보는 것을 한 번 연산한 것으로 가정할 때 n이 점점 커져서 무한대로 향하더라도 대략 n번 이상으로 연산하지는(n번 이상으로 찾아보지는) 않을 것입니다. 즉, 이 프로그램의 시간 복잡도를 빅 오 표기법으로 표현하면 O(n)이 됩니다.
빅 오 표기와 관련해 유의해야 할 점이 있습니다. 점근적 상한을 표현할 때에는 최고차항의 차수만 고려한다는 점입니다. 즉, 입력값 n에 대한 실행 시간의 점근적 상한을 수식으로 표현할 때는 최고차항의 차수만 고려합니다. 앞서 설명한 코드 예제를 상기해 봅시다. 입력값 n에 대한 연산 횟수를 n에 대한 식으로 표현했었죠. 이때, n이 점점 증가하여 무한대로 커진다면 계수와 낮은 차수의 항이 끼치는 영향은 무시할 수 있게 됩니다. 따라서 빅 오 표기법으로 점근적 상한을 표기할 때는 입력값 n에 대한 연산 횟수에서 계수와 낮은 차수의 항을 제외시키고, 다음과 같이 최고차항의 차수만 고려하게 됩니다.
| 소스 코드 | 필요한 연산 | 점근적 상한 | 빅 오 표기법 |
| for _ in range(n): 1 + 1 |
n | n | O(n) |
| for _ in range(2 * n): 1 + 1 |
2n | n | O(n) |
| for _ in range(n): for _ in range(n): 1 + 1 |
n2 | n2 | O(n2) |
| for _ in range(n): for _ in range(n): 1 + 1 for _ in range(3 * n): 1 + 1 1 + 1 1 + 1 |
n2 + 3n + 2 | n2 | O(n2) |
빅 오 표기법으로 표현되는 시간 복잡도 중에서도 자주 언급되는 표기들은 어느 정도 정해져 있습니다. 대표적인 시간 복잡도는 다음과 같은 그래프로 표현할 수 있습니다.
이 중 입력값 n이 충분히 클 때 가장 성능이 좋지 않은 시간 복잡도는 O(n!)입니다. 그렇다면 n이 충분히 클 때 O(n2)의 복잡도를 갖는 알고리즘과 O(1)의 복잡도를 갖는 알고리즘 중 더 성능이 좋은 알고리즘은 무엇일까요? 당연히 후자입니다. O(1)은 입력값이 10개, 1억 개가 주어지든 상관없이 항상 알고리즘의 실행 시간이 일정하다(상수 시간이 소요된다)는 의미이고, O(n2)은 n이 증가함에 따라 n의 제곱만큼 실행 시간이 증가한다는 것을 의미하니까요.
동일한 목적을 수행하는 알고리즘이라도 성능이 다를 수 있습니다. 일례로, 다음 표에 제시된 서로 다른 정렬 알고리즘들은 모두 정렬을 수행한다는 점은 동일하지만, 성능이 다를 수 있기 때문에 빅 오 표기법으로 표현된 시간 복잡도가 다릅니다.
| 정렬 알고리즘 | 시간 복잡도 |
| 삽입 정렬 | O(n2) |
| 선택 정렬 | O(n2) |
| 버블 정렬 | O(n2) |
| 병합 정렬 | O(n log n) |
| 퀵 정렬 | O(n log n) |
| 힙 정렬 | O(n log n) |
특정 자료구조를 구성하는 데이터에 대한 접근, 검색, 삽입, 삭제 연산의 시간 복잡도를 빅 오 표기법으로 나타낼 수 있습니다. 자료구조를 통한 다양한 연산이 가능하며, 각 연산에 대한 성능은 빅 오 표기법으로 표현 가능하다는 점에 유의해 주세요.
. 공간 복잡도space complexity는
프로그램이 실행되었을 때 필요한 메모리 자원의 양을 의미합니다. 시간 복잡도가 입력에 따른 실행 시간의 척도라면, 공간 복잡도는 입력에 따른 메모리 사용량의 척도라 할 수 있습니다.
모든 프로그램은 실행을 위해 메모리에 적재되어야 합니다. 같은 동작을 하는 프로그램이라고 하더라도 실행 과정에 많은 메모리가 필요한 경우가 있고, 그렇지 않은 경우가 있습니다. 이때 메모리의 사용량에 따라 많은 메모리가 필요한 경우는 공간 복잡도가 크고, 그렇지 않은 경우는 공간 복잡도가 작다고 할 수 있습니다.
흔히 공간 복잡도는 시간 복잡도처럼 빅 오 표기법으로 표현됩니다. 공간 복잡도를 빅 오 표기법으로 표현하면 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한을 표현하게 되겠죠. 다만, 오늘날 알고리즘의 성능 판단에 사용되는 척도는 주로 공간 복잡도보다는 시간 복잡도인 경우가 많기 때문에 특별한 언급이 없는 한, 빅 오 표기법으로 표현된 알고리즘의 성능은 모두 시간 복잡도를 표현한 것이라고 이해하시면 됩니다.
1.선형 자료구조 (Linear Data Structure
-데이터가 순차적으로 저장됨
- 각 데이터 항목이 이전 및 다음 항목과 관계를 맺는 자료구조
대표적인 선형 자료구조:
배열 (Array): 고정된 크기의 연속된 메모리 공간에 데이터를 저장합니다.
연결 리스트 (Linked List): 각 노드가 데이터와 다음 노드에 대한 참조(주소)를 가지는 자료구조입니다.
스택 (Stack): 후입선출(LIFO, Last In First Out) 방식으로 데이터를 처리합니다. 메모리내에 존재
큐 (Queue): 선입선출(FIFO, First In First Out) 방식으로 데이터를 처리합니다. 스케쥴링의 큐
2.비선형 자료구조 (Non-Linear Data Structures)
-데이터가 순차적으로 저장되지않음
-서로 다른 구조로 연결되어있는 자료구조이다
-트리나 그래프처럼 여러데이터 항목이 여러관계를 맺고있다.
대표적인 비선형 자료구조:
트리 (Tree): 계층적 구조로 데이터를 저장합니다.
각 노드는 부모와 자식 관계를 가집니다.
그래프 (Graph): 정점과 간선으로 이루어져 있으며, 정점들 사이의 관계를 표현합니다. 방향 그래프, 비방향 그래프 등이 있습니다
\
'CS' 카테고리의 다른 글
| C/S 5. 데이터베이스 (1) | 2024.12.03 |
|---|
