자료구조

자료

• 현실세계로부터 관찰이나 측정을 통해서 수집된 사실이나 값
• 자료형태는 숫자로 표현되는 수치값이나 문자들로 구성되는 스트링을 포함

정보

• 어떤 상황에 대한 적절한 의사결정을 할 수 있게 하는 데이터의 유효한 해석이 나 상호 관계
• 자료가 처리되어 발생하는 결과
• 한시성
• 비소모성
• 공공성
• 독점성

자료구조

• 데이터를 효율적으로 사용할 수 있도록 자료의 특성에 따라 분류하여 구조를 만들어서 저장해 둔 것
• 단순 자료구조: integer, float, char 등 단일자료
• 선형 자료구조: 리스트, 스택, 큐
• 비선형 자료구조: 트리, 그래프
• 파일구조: 보조기억장치에 저장되는 대용량의 자료구조

알고리즘

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
• 입력, 출력, 명확성, 정확성, 유한성, 효율성, 일반성

순서도

• 사다리꼴 입출력
• 타원 터미널
• 마름모 비교, 판단
• 육각형 준비

추상

• 자세한 정보는 감추고 사용자가 자료를 사용하는 데 필요한 정보만 인터페이스를 통해 외부로 노출하는 것

프로시져

• 추상화 제공
• 재사용 가능
• 여러 프로그래머가 같은 문제를 해결할 수 있게 도와줌
• 구조 파악이 쉽다

프로시져 간 자료 전달 방법

• Call By Value: 값에 의한 호출, 프로시저를 호출하기 전에 실인수의 값을 계산하고 값을 호출시에 대응되는 국소적 변수인 가인수에 대입함으로써 전달하는 방식
• Call By Reference: 참조에 의한 호출, 주소와 포인터 등 실인수를 참조하기 위한 정보가 가인수에 전달되어 동일한 데이터를 참조하게 되어 호출된 프로시저에서 참조하는 값이 변경되면 실인수의 값도 동일하게 변경된다.

재귀

• 함수가 직접 자신을 호출하는 방식

공간 복잡도

• Space Complexity, 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양

고정 공간

프로그램 입출력의 횟수나 크기와 관계없는 공간 요구

가변 공간

• 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들이 필요로 하는 공간

시간 복잡도

• 프로그램의 기능을 수행하기 위해 프로그램이 취한 단계수로 표현하는 것

빅오

• f(n) = O(g(n))은 모든 n, n >= n0에 대해 f(n) <= cg(n)인 조건을 만족하는 두 양의 정수 c와 n0이 존재하기만 하면 f(n) = O(g(n))이다.

배열

• 같은 자료형과 같은 크기를 가진 원소가 순서를 가지고 만들어진 집합
• 인덱스에 의해 참조

순서 리스트

• 나열한 원소들 간에 순서를 가지고 있는 리스트
• 평균 이동 횟수 (n+1)/2, 삭제 시 (n-1)/2
• 삽입 삭제시 전체를 밀어야되지만, 기억장소 효율은 가장 좋다.

연결 리스트

• 공간 제약이 없다.
• 삽입 삭제가 효율적이다.

주소 저장

• 행 우선: 시작주소 + (행 전체 열 크기 + 열) 원소 크기
• 열 우선: 시작주소 + (열 전체 행 크기 + 행) 원소 크기

희소행렬

• 행렬의 대부분 원소가 0일 경우 기억공간의 낭비가 발생하므로 0이 아닌 원소만 추출하여 [행 번호, 열 번호, 원소] 쌍으로 2차원 배열에 저장하는 방식
• 연산 측면에선 반복적인 패턴을 찾을 수 없어 비효율적

전치행렬

• 행과 열을 바꾼 것, B = A^T로 표현
• A^T = A면 대칭행렬

스택

• 한 끝에서 삽입과 삭제가 일어나는 순서 리스트
• LIFO

시스템 스택

• 함수가 호출될 때마다 프로그램은 활성 레코드 또는 스택이라는 구조를 생성하고 시스템 스택의 top pointer에 적재한다.

스택의 적용

• 부프로그램 호출 시 복귀 주소 저장
• 함수 호출의 순서 제어
• 인터럽트 복귀 주소 저장
• 중위 표기식을 후위 표기식으로 변환
• 후위 표기법으로 표현된 산술식 연산
• 0-주소 지정방식의 명령어 자료 저장소
• 재귀 프로그램의 순서 제어
• 컴파일러를 이용한 언어 번역

큐

• 리스트의 한 쪽에선 원소를 삽입하고 다른 쪽에서는 삭제만 하는 구조
• FIFO
• front pointer: 가장 먼저 삽입된 자료의 포인터
• rear pointer: 가장 나중에 삽입된 자료의 포인터
• 초기 조건: front == rear = -1
• 공백: front == rear = 1 && front == rear
• 가득참: rear = n - 1

원형큐

• 큐가 가득 찬 후에 첫 번째 큐를 Q[0]에 위치하게 조정하는 배열 이동은 시간이 많이 걸려 원형으로 만듦
• 초기 조건: front == rear == 0
• 삽입 위치: rear = (rear + 1) % n
• 삭제 위치: front = (front + 1) % n
• 공백: front == rear
• 가득참: front == (rear + 1) % n

큐의 적용

• 작업 버퍼 큐
• 프로세스 스케줄링
• 큐잉 시뮬레이션

데크

• 원소의 삽입과 삭제가 리스트의 양쪽 끝에서 이뤄지는 자료구조
• 스택과 큐의 결합
• Double Ended Queue

스크롤

• 입력 제한 테크
• 한 쪽에선 삭제만 가능

셀프

• 출력 제한 데크
• 한 쪽에선 삽입만 가능

스택 수식 계산

• 우선순위: 승제 > 가감 > 시프트 > 비교 > 등가 > 비트 > 논리

연결 리스트

순서 리스트의 문제점

• 삽입 삭제시 많은 이동
• 할당 공간 부족시 재할당
• 표현방법과 기억 공간의 크기가 달라지면 컴파일부터 다시 실행

비사용 기억공간

• 기억 공간이 필요하여 요청하는 경우 할당해 줄 수 있는 공간

연결 리스트의 응용

• 다항식 표현

이중 연결 리스트

• 링크의 방향을 양방향으로 이동할 수 있어 검색 효율성이 좋다.

원형 연결 리스트에서 헤드 노드를 사용하는 이유 모든 원소가 환형으로 연결되어 있기 때문에 무한 루프에 빠질 수 있어 헤드 노드를 두어 리스트의 시작을 알린다.

트리

• 정보의 검색 및 자료 보관을 위해 널리 사용되고 있는 자료구조
• 사이클을 포함하지 않는 연결 그래프의 일종
• 계층적 자료구조
• 노드와 각 노드를 연결하는 간선으로 구성
• 임의의 노드에서 다른 노드로의 연결은 하나만 가능하다.
• 루트 노드는 하나만 존재
• 트리의 부분 집합은 하나의 트리, 이 것을 서브 트리라고 한다.
• 노드 연결에 순환이 존재하지 않는다.

균형트리

• B-tree, AVL tree, Red-black tree

용어

• 노드: 자료를 담는 영역
• 간선: 노드 간의 연결 선
• 차수: 하위 노드의 개수
• 레벨: 계층 구조의 노드의 위치 값
• 높이 또는 깊이: 루트에서 터미널 노드까지의 레벨의 개수
• 터미널 노드: 최하위 노드
• 포리스트: 루트 노드를 제거하고 생기는 서브 트리들

이진 트리

• 모든 노드의 차수가 2 이하인 특수한 형태의 트리
• 순서트리의 특성을 가지므로 노드의 위치 또는 순서가 중요한 의미를 가진다.
• 편향 이진 트리: 단말노드를 제외한 트리의 구성 노드들이 왼쪽 또는 오른쪽 자식 노드만을 가지는 형태의 트리
• 전 이진 트리: 단말노드를 제외한 노드들이 왼쪽 자식과 오른쪽 자식 노드를 모두 가지고 있는 형태의 트리
• 포화 이진 트리: 단말노드를 제외한 모든 노드의 차수가 2이면서 최하위 자식 노드들이 모두 차여 있는 형태의 트리
• 완전 이진 트리: 루트 노드에서부터 하위 레벨로 순차적으로 왼쪽 자식, 오른쪽 자식 노드 순으로 추가된 트리의 형태
• 균형 이진 트리: 단말 노드의 레벨 값의 차이가 1 이하인 형태 (완전 이진 트리와 포화 이진 트리를 포함)
• 일차원 배열(완전 이진트리로 가정)과 연결 리스트로 표현하는 방법

이진 트리 순회

• 중위 순회: 좌 루트 우
• 후위 순회: 좌 우 루트
• 전위 순회: 루트 좌 우

이진 트리 정렬

• 루트부터 비교하면서 작으면 왼쪽 자식, 크면 오른쪽 자식
• 완성되면 중위 순회

스레드 이진 트리

• 터미널 노드의 null 값의 링크를 조상 노드에 연결해 알고리즘 성능을 향상시키는 방식

히프

• 완전 이진 트리의 자료구조
• 가장 큰 값이나 가장 작은 값이 완전 이진 트리의 루트에 항상 존재하는 자료구조
• 데이터 목록에서 가장 작은 값이나 가장 큰 값을 빠르게 찾을 수 있도록 구성된 자료구조

우선순위 큐

• FIFO를 지키면서 우선순위가 부여된 원소는 큐에서 위치와 상관 없이 먼저 출력되는 구조
• 배열, 연결리스트, 히프로 표현이 가능하다.
• 히프 사용시 O(logn)의 복잡도

이진 탐색 트리

• 이진 트리의 구조로 자료 검색 삭제 및 삽입에 효율적인 자료구조
• 원소들은 유일한 키 값을 가지며 좌측 서브 트리는 루트 값보다 작은 값들로 구성된 이진 탐색트리고 우측 서브 트리는 루트의 값보다 큰 값들로 구성된 이진 탐색 트리로 구성
• 중간 노드 삭제시 왼쪽 서브트리의 최대 원소와 오른쪽 서브트리의 최소 원소를 비교하여 중간 노드 값으로 올린다.
• 최대 높이는 n, 최소 높이는 log₂(n)

선택 트리

• N개의 원소를 임의의 개수로 나눈 원소를 가진 K개의 목록을 합병 정렬할 목적으로 구성

승자 트리

• 2개의 자식 노드 중 값이 작은 노드가 승자가 되어 상위 부모 노드로 올라가는 트리

패자 트리

• 승자 대신 패자 원소를 나타내고 승자는 상위 부모 노드에 올린다.

포리스트

• 서로 연결되지 않은 여러 개의 서브 트리로 구성된 구조
• 자료 접근에 어려움이 있어 이진 트리로 변환해야 한다.

• 이진트리에서 루트 레벨이 1로 시작할 때 레벨 i에서 최대 노드의 수는 2^(i-1) 개 이다.
• 이진트리에서 깊이가 i라면 최대 노드 수는 2^i-1개다.

그래프

• 공집합이 아닌 정점들의 유한집합과 공집합도 허용하는 간선들의 유한집합으로 구성
• 완전 그래프: 최대 수의 간선을 가지는 그래프
• 가중 그래프: 간선에 가중치가 할당된 그래프

그래프의 표현

• 인접 행렬: 간선이 있으면 1 없으면 0
• 인접 리스트: vertex와 link로 표현

그래프 순회

• 깊이 우선 탐색: 스택
• 너비 우선 탐색: 큐
• 신장 트리: 그래프의 간선들로만 구성되고 그래프의 모든 정점을 포함하는 트리, 사이클이 포함되면 안된다.

최소 비용 신장 트리

• 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리
• 비용은 거리 및 시간을 의미한다.
• Prim, Kruskal, Sollin 알고리즘이 있다.

Prim

• 가중치가 적은 간선을 선택해 가는 방식

Kruskal

• 탐욕적 방법
• 매번 선택마다 전체에서 가장 좋다고 생각하는 간선을 선택

그래프의 응용

PERT/CPM

• Program Evaluation and Review Technique / Critical Path Method
• PERT: 프로젝트에 필요한 전체 작업의 상호관계를 표현하는 방법
• CPM: 프로젝트 완성에 필요한 작업을 나열하고 작업에 필요한 소요 기간을 예측하는 데 사용하는 기법
• 상세 계획을 수립하기 쉽고 변화나 변경에 대해 바로 대처할 수 있고 네트워크상 문제점을 파악할 수 있고 중점관리가 가능하나 작성에 많은 시간이 든다.

최단 경로

• Dijkstra 알고리즘: 첫 번째 정점 a에서 최단 경로의 길이인 두 번째 정점을 찾는 알고리즘

탐색

• 주어진 리스트에서 원하는 키를 찾는 것
• 비교 탐색방법: 탐색 대상의 키를 비교하여 탐색하는 방법, 순차 탐색, 이진 탐색, 이진 트리 탐색
• 계산 탐색방법: 계수적인 성질을 이용하여 계산으로 탐색을 하는 방법, 해싱

순차 탐색

• 주어진 리스트에서 탐색키와 같은 레코드를 검색하는 방법
• O(n)

이진 탐색

• 이미 정렬되어 있는 리스트에서 절반을 쪼개가며 값을 찾는 방식
• O(logn)

피보나치 탐색

• 피보나치 수열을 이용해 중간 값을 계산해 속도가 빠르다.

정렬

• 내부 정렬: 리스트가 작아 주기억장치에서 모두 정렬이 가능
• 외부 정렬: 외부 기억장치를 이용해 정렬
• 비교식 정렬: 비교하고자 하는 각 키 값들을 한 번에 2개씩 비교하여 교환하는 방식
• 분산식 정렬: 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하여 각 부분집합을 정렬함으로써 전체를 정렬하는 방식

삽입 정렬

• 정렬되어 있는 값들을 삽입하고자 하는 값과 비교하여 큰 값들은 뒤로 이동한 후 삽입하는 방법
• O(n^2)
• 두번 째 원소를 기준으로 이전의 레코드들과 비교하여 적절한 위치를 찾아 삽입하는 방식

쉘 정렬

• 매개변수 값을 정하여 매개변수의 값만큼 간격을 가지는 레코드들을 여러 개의 서브 파일로 구성하면서 각 서브 파일을 삽입 정렬방식으로 배열하는 과정을 반복하는 것
• interval은 전체 레코드의 개수의 절반인 interval = n/2에서 시작해 매번 interval = interval / 2로 interval 값이 0보다 큰 경우에 반복 수행한다.
• O(n^1.25)

퀵 정렬

• 기준값인 피벗을 중심으로 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방법
• 분할 정복기법
• 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할하는 작업과 기준값보다 작으면 왼쪽 부분집합으로 크면 오른쪽 부분집합으로 정렬하는 정복 작업을 부분 집합의 크기가 1 이하가 될 때까지 반복한다.
• O(nlog₂n), 최악 O(n^2)

버블 정렬

• 인접한 2개의 레코드를 비교하여 위치를 서로 교환하는 방식
• 한 회전을 거치면 리스트의 마지막의 가장 큰 레코드가 남게 된다.
• O(n^2)

2원 합병 정렬

• 이미 정렬된 2개 이상의 배열이 있을 때 이들을 합쳐서 하나의 정렬된 배열을 만드는 것
• O(nlogn)

히프 정렬

• O(nlogn)
• 히프 트리를 이용해 정렬하는 방식으로 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하게 된다.

선택 정렬

• 단순한 정렬방법
• 이동하면서 가장 작은 값을 앞으로 보낸다.
• O(n^2)
• 데이터 양이 적을 때 아주 좋은 성능을 낼 수 있다.

기수 정렬

• 큐를 이용하여 자릿수 (digit) 별로 정렬하는 방식
• 부동소숫점 정렬 불가능
• O(dn)