4.1 복잡도
4.1.1 복잡도와 빅오 표기법
•
시간과 메모리 공간 등의 자원이 사용
◦
자원을 낭비하지 않고 효율적인 알고리즘을 짜는 능력이 필요
◦
얼마나 정량화 할 수 있을지
▪
시간 복잡도
•
알고리즘의 실행 시간을 정량화
▪
공간 복잡도
•
실행하는 데 필요한 메모리 사용량을 정량화
•
알고리즘 복잡도는 빅오 표기법
◦
입력 값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도를 표현
▪
최고 차항을 기준으로 표현하는 이유는 연산의 수가 극한에 수렴할 때 나머지 항이 복잡도에 미치는 영향은 미미해서.
▪
계수, 상수항은 무시하고 최고차항만으로 표현
4.2 선형 자료구조
•
연속적으로 데이터가 나열되는 자료구조
•
하나의 데이터 뒤에 다른 하나의 데이터가 연결
◦
배열
◦
리스트
◦
스택
◦
큐
4.2.1 배열
•
정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조
◦
데이터를 배열의 요소
◦
데이터를 가리키는 번호를 인덱스
▪
0부터 -1까지 참조 가능
•
접근
◦
시간 복잡도 O(1)
•
검색
◦
시간 복잡도 O(n)
•
삽입
◦
시간복잡도 O(n)
•
삭제
◦
시간복잡도 O(n)
4.2.2 연결 리스트
•
크기가 정해져 있지 않은 동적 자료구조
•
연결 리스트가 여러 개의 노드로 구성
•
노드는 데이터와 다음 노트가 저정된 주소 값을 가지고 있음
•
연결 리스트
◦
헤드 포인터
◦
테일 포인터
◦
새로운 노드가 추가 되어도 기존 노드들의 위치를 변경하지 않아도 되므로 시간 면에서 효율적
◦
인덱스가 없어서 특정 위치의 데이터에 접근하는데 배열보다 시간이 오래 걸린다.
•
검색
◦
시간복잡도 O(n)
•
추가
◦
데이터를 추가하는 연산 O(1)
◦
데이터를 추가하려는 위치로 이동 O(n)
◦
연결 리스트의 맨 앞에 데이터를 추가하는 경우 O(1)
◦
나머지 위치에 노드를 추가하는 경우 O(n)
•
삭제
◦
첫번째 데이터를 삭제하는 경우 O(1)
◦
첫번째 데이터를 제외한 나머지 위치에서 데이터를 삭제하는 경우 해당 위치까지 이동하기 위한 연산 최대 O(n)
•
연결리스트 종류
◦
단순 연결 리스트 (위에 설명한것들)
◦
이중 연결 리스트
▪
노드는 앞 노드의 주소 값과 다음 노드의 주소값을 모두 저장
▪
양방향 탐색이 가능
▪
한 노드당 주소 값 2개를 저장해야 해서 메모리를 많이 차지하는 단점
▪
노드의 연결 순서와 무관하게 노드를 연속적으로 탐색하는데는 효율적
◦
원형 연결 리스트
▪
마지막 노드가 NULL값이 아니라 첫번째 노드의 주소값을 가리키는 구조
▪
새로운 노드를 맨 마지막 또는 맨 앞에 삽입할 때 상수 시간이 소요
▪
순환 구조
4.2.3 스택
•
데이터를 쌓는 형태
•
마지막에 들어온 데이터가 먼저 나가는 LIFO 형태
•
데이터를 삽입하는 연산 push
◦
가장 위에 데이터를 저장
•
데이터를 삭제하는 연산 pop
◦
마지막에 저장한 데이터를 삭제
•
시간복잡도 O(1)
4.2.4 큐
•
데이터가 순차적으로 들어오는 형태
•
먼저 들어온 데이터가 먼저 나가는 FIFO 형태
•
큐의 맨 앞을 front
•
맨 뒤를 rear
•
큐의 맨 뒤에 데이터가 삽입 → 인큐
•
큐의 맨 앞에서 삭제 → 디큐
•
운영체제에서 프로세스가 CPU를 할당받기 전까지 대기하는 준비 큐
•
어떠한 작업을 처리할 때 작업 요청이 들어온 순서대로 처리하기 위해 주로 큐
덱
양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 자료구조. 큐와 스택을 합친 형태
4.3 비선형 자료구조
•
하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는, 1:N 또는 N:N 구조로 데이터가 나열되는 자료구조
•
계층적 구조
•
데이터를 하나하나 탐색하지 않아도 원하는 데이터를 찾을 수 있다는 장점
4.3.1 그래프
•
데이터를 포함하는 정점/노드
•
정점/노드을(를) 잇는 간선으로 구성된 자료구조
•
인접
◦
두 정점이 간선으로 연결되어 있으면 인접하다
•
차수
◦
정점에 연결된 간선의 수
•
진입 차수
◦
해당 정점으로 향하는 간선의 수
•
진출 차수
◦
해당 정점에서 나가는 간선의 수
그래프의 종류
1.
무방향 그래프
•
간선에 방향성이 없는 그래프
2.
방향 그래프
•
간선에 방향성이 있는 그래프
3.
부분 그래프
•
기존 그래프에서 일부 정점 또는 간선을 제외한 그래프
4.
가중치 그래프
•
간선에 비용이나 가중치가 할당된 그래프
5.
완전 그래프
•
간선을 최대로 가진 그래프
•
연결 그래프
6.
유향 비순환 그래프
•
방향 그래프이면서 사이클이 없는 그래프
경로 탐색
•
시작 정점이 주어졌을 때 간선을 거쳐 모든 정점을 탐색하는 경로
•
그래프 탐색에 사용되는 방법
1.
너비 우선 탐색 BFS
•
탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식
•
탐색하면서 큐에 삽입
2.
깊이 우선 탐색 DFS
•
시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색
•
재귀 호출 또는 스택으로 구현
4.3.2 트리
•
그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현
•
루트 노드
◦
부모 노드가 없는 노드
◦
하나의 루트 노드가 존재
•
부모 노드
◦
루트 노드 방향으로 연결된 노드
•
자식 노드
•
단말 노드
◦
자식 노드가 없는 노드
•
형제 노드
◦
부모 노드가 같은 노드
이진 트리
•
자식 노드가 최대 2개인 트리
1.
완전 이진 트리
•
트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있음
•
마지막 레벨은 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리
2.
포화 이진 트리
•
트리의 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리
•
완전 이진 트리
3.
이진 탐색 트리
•
왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성
•
오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성
•
루트 노드와 가까운 노드일수록 검색해야 하는 노드 개수가 절반으로 줄어듦
◦
값을 검색하는데 O(log n)
•
완전 이진 트리로 이진 탐색 트리를 구성하려면 균형 이진 탐색 트리가 필요
◦
레드-블랙 트리
◦
AVL 트리
4.3.3 우선순위 큐
•
우선순위가 높은 데이터가 먼저 나오는 자료구조
•
큐와 동일하게 데이터 삽입과 삭제 연산을 제공
•
구현 방식
◦
배열
◦
연결리스트
◦
완전 이진 트리인 힙
◦
가장 효율적인 방식인 힙을 사용
4.3.4 힙
•
완전 이진 트리
•
최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조
•
최대 힙
◦
부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
•
최소 힙
◦
부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
4.3.5 해시 테이블
•
하나의 키에 대해 하나의 값을 저장하는 형태의 자료구조
•
키는 해시 함수를 사용해 해시를 얻을 수 있다
•
해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값
•
해시 테이블에는 해시 충돌이라는 단점
◦
해시 충돌은 서로 다른 키에 대해 같은 해시가 도출되는 것
◦
해결 방법
▪
체이닝
•
같은 해시가 나오는 키의 값을 연결 리스트에 저장
•
저장 공간에 대한 제약이 적은 장점
•
하나의 해시에 노드가 몰릴 수 있다는 단점
▪
개방 주소법
•
비어 있는 공간에 값을 저장하는 방식
•
선형 조사법
◦
h[n]에 해시충돌 발생시
▪
h[n+1], h[n+2] 같이 다음 인덱스로 이동해서 빈공간을 찾음
▪
특정 인덱스 범위에 데이터가 몰리는 군집화 현상
•
이차 조사법
◦
h[n+1x1] ,h[n+2x2],h[n+3x3] 거듭제곱한 인덱스만큼 이동하고 빈공간을 찾음
◦
군집화 현상 완전히 해결되지않지만 조금 해결
•
이중 해싱
◦
다른 해시 함수를 한 번 더 적용