자료구조
- 자료 구조, 알고리즘
자료구조 : 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조
알고리즘 : 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.
- 시간 복잡도 : 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 → 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타냄(빅오 표기법) : 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타냄
- 공간 복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
선형 자료구조
- 선형 자료구조 : 요소가 일렬로 나열되어 있는 자료 구조
- 연결 리스트 : 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성인 자료 구조
- prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결 시킨 것
삽입, 삭제 : O(1)
탐색 : O(n)
- 배열 : 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합, 중복을 허용하고 순서가 있다.
삽입, 삭제 : O(N)
탐색 : O(1) → 랜덤 접근 가능
배열은 인덱스에 해당하는 원소를 빠르게 접근(랜덤 접근)하거나 간단하게 데이터를 쌓고 싶을 때 사용
- 랜덤 접근 VS 순차적 접근
랜덤 접근 : 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
순차적 접근 : 데이터를 저장된 순서대로 검색
- 배열 VS 연결 리스트
- 배열은 상자를 순서대로 나열한 데이터 구조이고, 몇 번째 위치인지만 알면 해당 위치의 요소를 뺄 수 있다.
- 연결 리스트는 선으로 연결한 데이터 구조이고, 요소를 알기 위해서는 접근하여 노드를 열어야 데이터 확인이 가능하다.
- 데이터 추가 삭제는 연결 리스트가 빠르다(포인터만 바꿔서 추가 및 삭제), 탐색은 배열이 더 빠르다(랜덤 접근 가능)
- 스택 : 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 LIFO 성질을 가진 자료구조
재귀적인 함수, 알고리즘에 사용되고 웹 브라우저 방문 기록에 사용
삽입, 삭제 : O(1)
탐색 : O(N)
- 큐 : 먼저 집어넣은 데이터가 먼저 집어넣은 데이터가 먼저 나오는 FIFO 성질을 가진 자료구조
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비, 우선 탐색, 캐시 등에 사용
삽입, 삭제 : O(1)
탐색 : O(N)
비선형 자료구조
- 비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계나 복잡한 구조
- 그래프 : 정점과 간선으로 이루어진 집합 자료 구조
- 정점 : 노드, 간선 : 정점과 정점 간을 잇는 선
- 가중치 : 간선과 정점 사이에 드는 비용
- 트리 : 그래프 중 하나로, 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합
- 부모, 자식 노드로 이루어져 있고, V - 1 = E
- 루트 노드 : 가장 위에 있는 노드
- 내부 노드 : 루트 노드와 내부 노드 사이에 있는 노드
- 리프 노드 : 자식 노드가 없는 노드
- 깊이 : 루트 노드에서 특정 노드까지 최단 거리로 갔을 때 길이
- 높이 : 루트 노드 부터 리프 노드까지 거리 중 가장 긴 거리
- 서브 트리 : 트리 내의 하위 집합
- 이진 트리 : 자식의 노드 수가 2개 이하인 트리
- 이진 탐색 트리(BST) : 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 노드
- 검색에 용이 → 왼쪽은 작은 값, 오른쪽에는 큰 값으로 정해져 있어서 탐색은 O(logn), 최악은 O(N) → 선형적일 수 있기 때문에
- 이진 탐색 트리의 선형적일 때를 해결 하기 위한 2가지 트리
- AVL 트리 : 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이가 난다.
탐색, 삽입, 삭제 : O(logn)
삭제를 할 때 마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전하여 균형을 맞춤
- 레드 블랙 트리 : 레드 블랙 비트를 통해 리프 노드와 루트 노드는 블랙이고 부모가 레드이면 자식은 블랙으로 설정하여 균형 유지
탐색, 삽입, 삭제 : O(logn)
- 힙 : 완전 이진 트리 기반의 자료 구조, 힙에 따라 특정한 특징을 지킨 트리
- 최대 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어진다.
- 최소 힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 하고, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
- 힙의 삭제 : 최대 힙은 루트 노드값 삭제, 마지막 노드와 루트 노드 스왑 반복
- 우선 순위 큐 : 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조
- 맵 : 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조, 삽입 하면 자동으로 정렬
- 셋 : 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이고, 중복되는 요소가 없다.
- 해시 테이블 : 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다.
삽입, 삭제, 탐색 : O(1)
Java Collection
자바의 대표 Collection에는 List, Map, Set, Stack, Queue와 같은 것들이 있다. 이 추상화된 Collection 인터페이스 아래, 특정한 기법으로 구현된 자료구조가 들어간다. 예를 들어, List라는 인터페이스에는 구현방법에 따라 ArrayList가 들어갈 수도, LinkedList가 들어갈 수도 있다.
- ListArrayList자바의 Vector를 개선한, 배열로 구현된 List이다. 그 말인 즉슨, 데이터가 저장된 순서가 같다는 말이다. 사실상 배열과 같은 자료구조이기 때문에, 리스트의 연산 자체의 수행시간 속도는 배열과 같다.LinkedList다음 노드의 주소를 기억하고 있는 List로, 배열에 비해 삽입과 삭제가 간단하다. 그러나 탐색의 경우 첫 번째 노드부터 탐색해 나가야 하기 때문에 느리다.
- MapHashMap가장 일반적으로 사용하는 Map. HashTable을 사용, Key값에 해시함수를 적용하여 나온 index에 Value를 저장하는 식. 중복성을 허용하지 않으며, 순서가 없다는 것이 특징TreeMapRed-Black Tree 자료구조를 이용한 Map이다. Tree 구조이기 때문에 어느 정도 순서를 보장한다.LinkedHashMapLinkedList로 구현된 HashMap이다. List로 구현되어있기 때문에 순서가 보장된다. 하지만 LinkedList 특성상 랜덤 접근에서 느릴 수 있다.
- SetHashSetHashMap에서 Key값이 없는 자료형. 집합이라고 생각해도 무방하다. 값이 포함되어 있는지 아닌지만 관심이 있다. 순서를 보장하지 않으며, 중복값을 허용하지 않는다. Set중에는 가장 많이 사용된다.TreeSetRed-Black Tree 자료구조를 사용한 Set.LinkedHashSetLinkedList로 구현된 HashSet. 순서를 보장한다.
- Stack & QueueStack직접 new 연산자로 객체를 생성하여 사용 가능.QueueLinkedList 에 new 연산자로 객체를 생성함으로서 사용 가능.
- 추가로 자바 Array와 ArrayList의 다른점.둘 다 배열이라는 점은 동일하나, Array는 인덱스로 접근하는 반면, ArrayList는 메서드를 통해 접근한다(어짜피 Index로 호출한다는 점은 동일 하겠지만..). 또한 Array는 Object 뿐만 아니라 원시 형태(Primitive, 예를 들어 int, double 등)도 담을 수 있지만, Array는 Object형(Reference, 객체)만 담을 수 있다. 따라서 정수를 ArrayList에 넣을 경우 Integer형은 가능하지만 int형은 안 된다. 덧붙여서, Integer처럼 int와 같은 원시타입을 담을 수 있는 객체를 Wrapper Class라고 한다.
알고리즘
[ 버블소트, 힙소트, 머지소트, 퀵소트, 삽입소트 ]
버블소트는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬합니다. 시간복잡도는 O(n2) 입니다.
힙소트는 주어진 데이터를 힙 자료구조로 만들어 최대값 또는 최소값부터 하나씩 꺼내서 정렬하는 알고리즘입니다. 힙소트가 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만을 필요로 하는 경우입니다. 시간복잡도는 O(nlog2n)입니다.
머지소트는 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘입니다. 시간복잡도는 O(nlog2n)입니다.
퀵소트는 매우 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로 합병정렬과 달리 리스트를 비균등하게 분할합니다. 피봇을 설정하고 피봇보다 큰값과 작은값으로 분할하여 정렬을 합니다. 시간복잡도는 O(nlog2n)이며 리스트가 계속해서 불균등하게 나눠지는 경우 시간복잡도가 O(n2) 까지 나빠질 수 있습니다.
삽입정렬은 두 번째 값부터 시작하여 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘입니다. 삽입 정렬의 평균 시간복잡도는 O(n2)�(�2) 이며, 가장 빠른 경우 O(n)�(�) 까지 높아질 수 있습니다.
[ 정렬 알고리즘 시간복잡도 비교 ]
[ 동적 프로그래밍(Dynamic Programming)이란? ]
동적 프로그래밍(Dynamic Programming) 이란 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 해결하는 방식입니다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모이제이션(Memoization) 기법으로 속도를 향상 시킬 수 있습니다.
[ 동적 프로그래밍(Dynamic Programming)의 두 가지 조건 ]
동적 프로그래밍(Dynamic Programming)으로 문제를 해결하기 위해서는 주어진 문제가 다음의 조건을 만족해야 한다.
- Overlapping Subproblem(중복되는 부분문제): 주어진 문제는 같은 부분 문제가 여러번 재사용된다.
- Optimal Substructure(최적 부분구조): 새로운 부분 문제의 정답을 다른 부분 문제의 정답으로부터 구할 수 있다.
[ 재귀 알고리즘과 재귀의 시간 복잡도 ]
재귀 알고리즘이란 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 문제를 해결하는 알고리즘입니다. 재귀 알고리즘은 자기가 계속해서 자신을 호출하므로 끝없이 반복되게 되므로 반복을 중단할 조건이 반드시 필요합니다.
팩토리얼을 계산하는 재귀 함수에서는 T(n) = T(n-1) + c (C는 n과 f(n-1)을 곱하는 비용)을 조회하고 점화식을 계산하면 아래와 같이 O(n)이 됨을 보일 수 있습니다.
T(n) = T(n-1) + c
= T(n-2) + 2c
= T(n-3) + 3c
= ……
= T(2) + (n-2)c
= T(1) + (n-1)c
≤ c + (n-1)c = c + cn - c = cn --> O(n)[ 팩토리얼의 재귀/반복문 손코딩 ]
private static int recursiveFactorial(int num) {
if(num > 1) {
return recursiveFactorial(num - 1) * num;
}
return 1;
}
private static int loopFactorial(int num) {
int answer = 1;
for (int i = 2; i <= num; i++) {
answer *= i;
}
return answer;
}[ 피보나치 수열 재귀/반복문 손코딩 ]
private static int recursiveFibonacci(int index) {
if (index <= 2){
return 1;
}
return recursiveFibonacci(index - 1) + recursiveFibonacci(index - 2);
}
private static int loopFibonacci(int index) {
int answer = 1;
int before = 1;
int temp;
for (int i = 2; i < index; i++) {
temp = answer;
answer += before;
before = temp;
}
return answer;
}3. 알고리즘 - 고급
[ n개의 배열에서 k(k<=n) 번째로 큰수를 찾는 알고리즘 ]
이러한 문제를 해결하기 위해 일반적으로 퀵정렬을 사용합니다. 하지만 퀵정렬을 사용하면 정렬이 불필요한 부분들을 정렬하면서 효율적이지 못하게 됩니다. 퀵선택 알고리즘은 퀵정렬을 한 후에 피봇과 K를 비교하여 아래와 같이 수행합니다.
- pivot의 인덱스가 k와 같은 경우 : 그대로 그 인덱스의 값을 리턴하면 된다.
- pivot의 인덱스가 k보다 작은 경우 : pivot의 인덱스+1부터 마지막 인덱스까지 다시 Partition함수에 넘겨준다.
- pivot의 인덱스가 k보다 큰 경우 : 첫번째 인덱스부터 pivot의 인덱스-1까지 다시 Partition함수에 넘겨준다.
퀵정렬 알고리즘과의 다른 점은 예를 들어 Pivot의 인덱스가 7이고 K가 5인 경우에, 피봇의 오른쪽 부분은 재귀 함수를 돌지 않아 한 쪽만으로 재귀를 진행하는 것입니다.
[ 허프만 코딩이란 ]
허프만 코딩은 문자의 빈도를 이용해 압축하는 방법으로 빈도가 높은 문자에 짧은 코드를 부여합니다. 허프만 코드는 접두부 코드와 최적 코드를 사용합니다.
- 접두부 코드: 문자에 부여된 코드가 다른 이진 코드의 접두부가 되지 않는 코드
- 최적코드: 인코딩된 메세지의 길이가 가장 짧은 코드
[ 특정 수 이하의 3과 5의 배수의 합 구하기 손코딩 ]
private static int addMultipleOf3And5(int maxNum) {
int div = maxNum / 3;
int sum3 = (1 + div) * div * 3 / 2 ;
div = maxNum / 5;
int sum5 = (1 + div) * div * 5 / 2 ;
div = maxNum / 15;
int sum15 = (1 + div) * div * 15 / 2 ;
return sum3 + sum5 - sum15;
}