4학년 1학기 시작

매번 강의를 블로그에 정리하려고 한다. 자료구조 선행 학습을 적절히 마쳤고, 마음 가짐을 고치고 회복하는 시간을 가졌다.

---

알고리즘

컴퓨터 과학에서 알고리즘의 위치는?

컴퓨터 과학 = 컴퓨터 + 데이터
데이터를 컴퓨터에 입력하고, 정보를 얻어낸다.
데이터를 처리하기 위한 정확한 프로그램을 만들어내는데, 이 프로그램은 어떻게 만들어지는가?

컴퓨터 과학 = 알고리즘 과학
컴퓨터 과학은 모두 알고리즘을 다루는 것이다.

알고리즘이 존재한다면 프로그램을 만들 수 있고, 알고리즘이 존재하지 않으면 프로그램을 만들 수 없다.

알고리즘을 배우는 이유

잘 알려진 특정 문제를 통해 알고리즘의 설계 및 분석 방법을 습득한다.

결국, 모든 내용은 어떻게 설계하고 어떻게 분석할 것인가? 에 초점을 맞추고 학습을 하게 된다.

• 정렬, 탐색, 그래프, etc...

컴퓨터 기반 문제 해결에 대해 체계적으로 생각하는 훈련
주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상을 이루어내야 한다.

필요한 것

• 기초적인 프로그래밍 언어 능력
• 기초적인 수학 능력
• 논리적으로 사고할 수 있는 능력
• 기초적인 자료구조의 이해

앞으로 배울 것들

알고리즘은, 컴퓨터를 이용해서 문제를 해결하기 위한 학문이다.

자료구조

기본적인 자료구조 6가지

• 배열

• 연결리스트

• 큐

• 스택

• 트리

• 그래프

이 6가지는 항상 기억하고 있어야 한다.
배열, 연결리스트, 큐, 스택은 선형 자료구조이며
트리, 그래프는 비선형 자료구조이다.

선형 자료구조는 데이터 사이의 논리적 관계를 선형으로 표현한 방식이다. (데이터를 한 줄로 줄 세울 수 있다는 뜻.)
비선형 자료구조는, 데이터 사이의 논리적 관계를 한 줄로 나열할 수 없다.

배열

같은 자료형을 갖는 여러개의 데이터를 하나의 변수의 이름으로 모아놓은 데이터의 집합체.

삽입과 삭제가 발생하게 되면, 자료의 이동이 발생하게 된다.
즉, 자료가 많을 경우 자료의 이동이 부담이 될 수 있다.
삽입과 삭제가 빈번하게 발생하는 경우 배열을 사용하는 것이 적절하지 않을 수 있다.

연결리스트

노드(하나 이상의 데이터 필드와 하나 이상의 링크 필드로 구성)이라는 저장구조를 연결해서 선형 링크드 리스트를 구현하는 방법.

배열과 같이 공부하는 이유는, 삽입과 삭제가 빈번하게 발생하는 경우에 적합하기 때문이다.
특징은, 논리적인 순서와 실제 순서가 맞지 않을 수 있다는 것이다.
ex) 일 - 월 - 화 - 수 - 목 - 금 - 토
데이터를 찾아갈 때 순차적으로 접근하게 되며, 데이터가 많을 경우 데이터를 찾아가는 경우가 쉽지 않다.
다만, 데이터 삭제 시 다음을 가리키는 포인터를 수정하면 되기 때문에 삭제가 간편하다!
데이터 삽입도 마찬가지!

스택

한 쪽 끝에서만 데이터의 삽입과 삭제가 수행되는 선형리스트, 후입선출(LIFO) 리스트

데이터를 입력하면, 데이터가 쭉 쌓이게 된다.

몇 개까지 데이터가 쌓였는지 알아야 한다 = 스택의 맨 위를 top이라는 변수를 사용하여 알 수 있게 된다.

push(데이터 삽입)

pop(데이터 뽑아내기)

큐

한 쪽 끝에서만 데이터의 삽입만 이루어지고, 반대쪽 한 쪽에서는 데이터의 삭제만 이루어지는 자료구조, 선입선출(FIFO) 리스트

데이터를 입력하면, 데이터가 쌓이지만 삭제할 때는 가장 먼저 들어간 데이터가 나오게 된다.

몇 개까지 데이터가 쌓였는지 알아야 한다 = 맨 앞과 맨 뒤, front(head), rear(tail)이라는 변수를 사용한다.

초기 상태에서 데이터 A를 삽입한다, head와 tail 모두 A가 된다.

삽입과 삭제가 계속 반복되면, front가 계속 이동한다.

---

트리

노드라는 정보 항목이 간선으로 표현되어 계층적인 구조를 표현하는 비선형 자료구조

하나 이상의 노드로 구성된 노드의 유한 집합

노드와 간선들을 통하여, T의 원소 가운데 루트 노드(root node : 뿌리 노드)가 존재한다.

루트 노드를 제외한 나머지 노드는 n개(0개 이상의 데이터)의 서로 분리된 부분집합 $T_1$, $T_2$... $T_n$으로 나누어지며,
각 $T_i$(서브트리)는 트리가 된다.

주요 용어

차수 (노드의 차수, 트리의 차수)
각 노드가 갖고 있는 트리의 개수이다.

트리에 있는 노드의 차수 중에서, 가장 큰 값을 트리의 차수 라고 부른다.
즉, 해당 트리의 차수는 3이다!

리프 노드(단말 노드)
노드의 차수가 0인 것을 뜻한다.
해당 그림에서 리프 노드는 J, K, L, C, M, N, I등이 리프 노드에 해당한다.

비 단말노드
리프 노드를 제외한 나머지 노드를 뜻한다.
해당 그림에서 비 단말노드는 J, K, L, C, M, N, I를 제외한 모든 것들이다.

부모 노드, 자식 노드, 형제 노드
한 노드가 있으면, 그 아래에 있는 노드를 자식 노드라 하고, 자식 노드의 위에 있는 노드를 부모 노드라 한다
해당 그림에서 A의 자식 노드는 B, C, D이며 이들은 서로 형제 노드이다. (같은 부모이기 때문)

조상 노드, 자손 노드
예를 들어, F 노드의 조상 노드는 A이며, A의 부모 노드가 있다면 계속 거슬러 올라가 조상 노드라고 한다.

⭐️ 레벨 ⭐️
루트 노드로부터의 거리이다.
루트 노드 A는 레벨이 0이다
자식 노드 B, C, D는 레벨이 1이다.
E, F, G, H, I는 레벨이 2이다.
J, K, L, M, N은 레벨이 3이다.

높이
해당 그림에서 트리의 높이는 4이며, 깊이와 같은 말이다.
트리에 레벨 + 1을 하면 높이를 알 수 있다. 헷갈리지 말자.

숲(forest)
루트 노드를 없다고 생각했을 때, 그 서브트리로 이루어지는 집합을 숲이라고 표현한다. (B, C, D)

⭐️ 이진트리 ⭐️

컴퓨터에서 가장 많이 사용되는 자료구조

각 노드의 차수가 2 이하인 순서 트리 (0, 1, 2)
해당 트리의 차수가 2인 것, 각 노드가 최대 2개의 서브트리를 갖는 순서 트리를 이진트리라고 한다.

⭐️ 순서트리 ⭐️

해당 그림에서 4번째, 5번째 트리는 같은 트리가 아니다.

첫 번째 그림처럼 공백도 이진트리로 취급한다.

이진트리의 특성

레벨 i에서 최대 노드의 개수 (i>=0) => $2^i$

그렇다면, 높이가 h인 이진 트리의 최대 노드 개수는? (단, h는 1보다 크다)
$2^h$ - 1

노드의 개수를 정확히 알 수는 없으나, 최대로 가질 수 있는 노드의 개수를 알 수 있다.

단말 노드(자식이 없는 노드, leaf node)의 개수를 $n_0$이라고 했을 때 차수가 2개인 노드를 $n_2$라고 하자.
그렇다면 $n_0$ = $n_2$ + 1이 성립한다. 활용할 줄 알아야 한다.

포화 이진트리

빈 자리 없이 꽉 차있는 이진트리 (루트 노드를 제외하고 모든 노드의 차수가 2개)

완전 이진트리

맨 마지막 레벨을 제외하고는 포화 이진트리의 형태를 띄고 있다. (그림에서는 레벨 2)
레벨 3에서는 빈 자리 없이 노드가 차 있다.

전 이진트리
노드의 차수가 1인 것이 없다.
각 노드의 차수가 0이거나, 2거나 이 두 가지 경우로만 이루어진 것을 전(full) 이진 트리라고 한다.

균형 이진트리

왼쪽과 오른쪽 서브트리의 높이가 1 이내인 것, (루트 노드 기준)
왼쪽 서브트리의 높이는 2고, 오른쪽 서브트리의 높이는 3이다.
어떤 경우에서 보더라도 높이의 차이가 1 이내이므로, 균형 이진트리이다.

경사 이진트리
각 노드가 자식을 하나 밖에 갖지 않는다.

이진트리의 구현

모든 자료구조는 일차원 배열을 통한 구현, 연결 리스트를 통한 구현으로 나뉜다.

해당 이진 트리가 가질 수 있는 최대 노드의 개수는 $2^4$ -1 = 15
15개일 것이다.

배열을 이용한 이진트리의 구현은, 배열을 15개를 만들어 놓은 후 위치에 맞게 데이터를 채워 넣는 것이고.

연결 리스트를 통한 구현은, 하나의 노드에서 왼쪽을 가리키는 링크필드, 오른쪽을 가리키는 링크필드로 만들어 구현한다.

그래프

그래프는 도형으로 표현되는 비선형 자료구조로서, 연결할 객체를 나타내는 정점의 집합 V와 간선의 집합 E로 구성됨.

$G = (V,E)$
$V$ : 정점의 집합, $E$ : 간선의 집합

무방향 그래프의 경우, 1에서 1로 가든, 3으로 가든 상관이 없다.
(1, 2) = (2, 1)

무방향 그래프에서 두 번째 그래프를 봤을 때
$V(G_2) = {1, 2, 3, 4, 5}$
$E(G_2) = { (1, 2), (1, 3), (2, 4), (3, 5) }$ 로 표현할 수 있다.

이를, 가중 그래프라고 표현한다.

그래프의 구현

배열을 이용하여 구현한다 : 인접 행렬

1에서 2로 이동할 때 간선이 3이다. 2에서 4에서 이동할 때 간선이 1이다.
대각선은 모두 0을 유지한다.

그렇다면, 2에서 3으로 가는 무한대는 무엇을 나타내는가? : 간선이 없는 것을 뜻한다.

가중치 그래프가 아니고, 숫자들이 없는 것은 어떻게 표현하는가? : 간선이 있다, 없다만 표시하면 되기 때문에
간선이 없으면 0, 간선이 있으면 1로 표현한다.

링크드 리스트를 통하여 구현한다 : 인접 리스트

각 정점에서 간선이 존재하는 정점들을 리스트로 표현한다.

1이라는 정점에서 2로 가는 간선이 있다. 이 때 가중치는 3이다.

1이라는 정점에서 4로 가는 간선이 있다. 이 때 가중치는 4다.

각 정점에서 정점으로 이동하는 간선을 리스트에 저장하면 된다.

만약, 가중치가 없다면? : 가운데에 있는 간선을 표현하는 링크필드 (ex : 1에서 2로 갈 때 3)를 없애주면 된다.

정리

알고리즘의 필요성 : 컴퓨터를 이용하여 문제를 해결하기 위해서, 일련의 단계 처리 과정인 효율적 알고리즘이 반드시 필요.
기본 자료구조 : 배열, 연결 리스트, 스택, 큐, 트리, 그래프