자료구조
-
자료구조를 배우는 이유?
특정문제를 해결하는데에 상황에 가장 적합한 자료구조를 빠르게 찾아 데이터를 정리하고 활용하면 문제를 빠르고 정확하게 해결할 수 있기 때문입니다. 만약 전화번호부가 있는데 번호 없이 이름만 사용해서 전화를 걸려면 해쉬 자료구조를쓰면 됩니다. -
시간복잡도 : 어떠한 알고리즘의 로직이 얼마나 오랜시간이 걸리는지 나타는데 쓰이며, 보통 빅오 표기법으로 나타냅니다. n을 입력했을때 필요한 시간이 10n^n+n이라고 시간복잡도는 O(n^2)입니다.
-
공간복잡도: 공간복잡도는 프로그램을 실행시켰을때 필요로하는 자원 공간의 양을 말합니다. 동적으로 재귀적인 함수로 인해 공간을 계속 필요로 할 경우도 포함합니다.
배열과 연결리스트
- 배열: 같은 타입들의 변수들로 이루어져있고, 크기가 정해져있으며, 인접한 메모리 위치에 데이터를 모아놓은 집합입니다. 중복을 허용하고 순서가 있습니다. 탐색은 O(1)이 되어 랜덤 접근이 가능합니다. 삽입과 삭제에는 O(n)이 걸립니다. 따라서 탐색을 많이 할 경우 배열로 하는것이 좋습니다.
- 연결리스트: 각각 데이터는 자신의 다음원소가 무엇인지만 기억하고있습니다. 데이터 추가 및 삭제는 연결리스트가 빠르고 배열은 느립니다. 탐색은 일일히 앞에서부터 찾아가면서 탐색하기 때문에 O(n)로 배열보다 느리고 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만 연결리스트는 선을 바꿔서 연결해주기 때문에 추가 및 삭제가 O(1)로 더 빠릅니다.
-
벡터 : 동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에 갯수를 모른다면 벡터를 씁니다. 탐색과 맨뒤에 요소를 삭제하거나 삽입하는데 O(1)이 걸립니다.
-
스택 : 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질을 가진 자료구조 입니다. 삽입 삭제에 O(n) 탐색에 O(n)이 걸립니다.
-
큐: 먼저 집어 넣은 데이터가 먼저 나오는 성질을 지닌 자료구조이며, 삽입 삭제에 O(1), 탐색에 O(n)이 걸립니다.
-
그래프: 정점과 간선으로 이루어진 집합을 트리라 그런다. 간선과 정점 사이에 드는 비용을 가중치라고 한다.
-
트리: 그래프의 특징처럼 정점과 간선으로 이루어져있고, 계층적 관계를 표현하는 자료구조입니다. 루트 노드 : 최상위에 있는 노드
단말 노드 : 하위에 다른 노드가 연결되어 있지 않은 노드
내부노드 : 단말 노드를 제외한 모든 노드 -
이진트리: 자식 노드가 두개 이하인 트리를 의미합니다.
-
정이진트리 : 자식 노드가 0개 아니면 2개
-
완전 이진 트리 : 왼쪽 부터 채워져있는 이진 트리
-
균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차가 1이하인 이진트리
-
이진 탐색 트리 : 오른쪽 하위 트리에는 노드값 보다 큰 값만 포함되고 왼쪽 하위 트리에는 노드값보다 작은값이 들어있는 트리 요소를 찾을대 O(logn)이 걸리고 최악의 경우 O(n)
-
레드 블랙 트리 : 균형 이진 트리로 탐색 삽입 삭제 시간복잡도가 O(logn)이다. 각노드는 색상을 나타내는 추가비트를 저장하며, 삽입 및 삭제중에 트리가 균형을 유지하도록 하는데 사용합니다.
-
힙:최솟값 최댓값을 빠르게 찾아내기 위해 완전이진트리로 만들어진 자료구조입니다.
최대힙 : 루트노드는 모든 자식보다 가장 커야 합니다. -
우선순위큐 : 우선순위가 제일 높은것들을 제일먼저 삭제하는 자료구조,힙을기반으로 구현된다.
-
맵 : 특정 순서에 따라 키와 매핑된 값의 조합으로 이루어진 자료구조, 레드 블랙 트리 자료구조를 기반으로 형성되고, 삽입하면 자동으로 정렬됩니다.
-
셋 : 중복되는 요소는 없고 순서도 없다.
-
해쉬테이블 : 무한의 가까운 데이터들을 유한의 개수의 해시 값으로 매핑한 테이블이다. O(1)의 시간 복잡도
알고리즘
-
선택정렬 -> 기준값을 정하고 기준값 뒤 배열중에서 제일 작은값을 기준값과 교체한다 이걸 반복
즉, 시간 복잡도는 O(N^2)이 된다. 최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도는 O(N^2)이 된다. 공간 복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다. -
거품정렬 -> 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 마지막 - 1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다. O(N^2)이다.
-
합병정렬 : 연결리스트로 구현 쪼개고 다시 합병하는 식으로
-
퀵정렬 : 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소는 피벗(pivot)이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.분할 된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다. 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다. -
이분탐색 : 탐색 범위를 두 부분으로 분할하면서 찾는 방식 O(N) O(logN)
-
동적 계획법 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
-
dp를 이용한 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘
