알고리즘 문제를 풀다보면 적절한 로직을 활용해서 Time Complexity를 만족해야하는 경우가 많다.
Time Complexity(시간복잡도)
최악의 경우 연산이 수행되는 시간을 나타내기 위해 Big-O로 나타내며, 이는 적어도 이만큼은 걸린다로 이해하면 된다.
그 외에도 Big-Omega와 Big-Theta가 있고 이들은 각각 아무리 많아도 이만큼 걸린다, 정확히 이만큼 걸린다로 해석할 수 있다.
1초는 대략 1억번의 연산이 수행될 수 있다.
시간 복잡도를 결정짓는 가장 큰 요인인 입력 크기(Input Size)와 연산(Operation)을 가지고서 계산하며, 이를 기준으로 현재 설계한 알고리즘으로 문제가 해결 될 수 있는지를 판단하면 된다.
- 10! = 360만, 11! = 4000만
- 2^20 = 100만, 2^26 = 6400만
- 3^16 = 4300만
- 10^9 = 10억
메모리 제한은 공간 복잡도를 나타낸다.
시간 제한과 함께 메모리 제한도 주어지는데 이는 자료구조를 활용하여 데이터를 저장하는 공간의 크기로 계산하면 된다.
Java : Byte < Short,Char < Int,Long < Float,Double
배열은 동형 타입의 연속된 메모리 공간이다.
배열은 물리적으로 연속된 공간을 할당 받아서, 같은 타입을 저장하는 자료구조이다.
- 한번 선언된 배열은 크기를 변경할 수 없다.
- 특정 값을 찾는 탐색은 O(N)
- 인덱스 기반 탐색은 O(1)
- 새로운 데이터의 삽입이나 삭제는 O(N)이며, 데이터의 재배치와 배열의 재할당이 수반된다.
배열은 가변적이지 못하다는 단점으로 인해 동적 배열인 ArrayList를 활용한다.
- 크기를 자유롭게 조절할 수 있으므로, 공간복잡도 측면에서 효율적으로 사용할 수 있다.
- 내부적으로 Object Array를 사용하므로, 모든 연산의 시간복잡도는 기존 배열과 동일하다.
따라서 배열은 데이터의 삽입,삭제는 빈번하지 않으면서 인덱스 기반 탐색 시 유리하다.
연결리스트는 논리적으로 연속성을 부여받은 자료구조이다.
앞서 배열과 ArrayList 모두 연속된 메모리 공간을 사용하기 때문에, 새로운 데이터를 추가하거나 삭제할 때 모든 데이터가 영향을 받는다고 정리했다.
이러한 단점을 개선하기 위해 데이터와 링크로 구성된 노드를 활용해서 논리적인 연결관계를 표현한 LinkedList가 탄생했다.
- 방향성에 의한 탐색만 가능하므로 O(N)
- 인덱스 같은건 존재하지 않는다. 오직 Head,Tail만 존재할 뿐
- 새로운 데이터의 삽입이나 기존 데이터의 삭제는 타겟 노드의 앞뒤 관계만 변경해주면 되므로 O(1)
방향성의 갯수와 Head,Tail의 관계에 따라 Singly,Doubly,Circular LinkedList가 존재한다.
다만, 데이터의 삽입,삭제할 타겟 노드를 찾는 과정이 O(N)인데, 이를 기억해두고 있는 Iterator를 활용하면 최초에만 O(N)이고 그 이후에는 O(1)에 해결할 수 있다.
이처럼 LinkedList는 데이터의 삽입 삭제가 빈번한 경우에 유리하다.
Stack - LIFO
스택은 후입선출의 특징을 갖는 자료구조이며, 데이터의 삽입 삭제는 한 공간에서만 발생한다.
- 데이터의 삽입과 삭제 O(1)
- 데이터의 탐색은 Top에서만 가능하다.(배열로 구현할 수도 있다)
- peek , push, pop
- 실제 구현은 Deque을 구현한 ArrayDeque을 사용하자.
Queue - FIFO
큐는 선입선출의 특징을 갖는 자료구조이며, 데이터의 삽입 삭제는 상황에 따라 서로 다른 공간에서 발생할 수 있다.
- 데이터의 삽입과 삭제 O(1)
- 데이터의 탐색은 front 혹은 rear에서만 가능하다.(연결리스트로 구현할 수도 있다)
- poll,offer,peek,isEmpty
- Queue를 구현한 LinkedList나 Deque을 구현한 ArrayDeque을 사용하자.
Deque is Doubly Ended Queue
기존의 큐는 삽입과 삭제가 각각 한방향에서만 가능했다면 Deque은 그것이 양방향에서 가능하도록 구현하였다.
따라서 덱을 활용하면 Stack,Queue 처럼 사용할 수 있다.
Tree는 1:N의 관계를 갖는 비선형 자료구조
- Node : 트리의 각 정점(Vertex)
- Edge : 정점을 연결하는 간선
- Root : 트리의 최상단 노드
- Parent,Child : 부모 자식 노드의 관계 (자식은 여럿일 수 있으나, 부모는 오직 하나)
- Degree : 특정 노드의 자식 노드의 수
- Depth : 루트노드와의 거리
- Height : Max(Depth)
- Leaf : 자식 노드가 없는 노드
Tree is Directed Acyclic Graph : 방향성(부모->자식), 사이클 없는 그래프
자식 노드의 수가 최대 2개인 조건이 붙으면 이진 트리(Binary Tree)
위에서 소개한 트리에서 자식 노드의 수를 최대 2개로 제한하면 우리는 이진 트리라 한다.
이진 트리는 배열로도 구현이 가능한데, 1번 인덱스부터 사용하게 되면 다음과 같은 특징을 갖는다.
- 부모 노드 : i/2
- 왼쪽 자식 : i*2
- 오른쪽 자식 : i*2+1
트리의 순회 방법 (Pre-Order,In-Order,Post-Order)
루트 노드를 탐색하는 시점에 따라 전위,중위,후위순회로 나뉜다.
재귀 함수로 구현한다
다른 두 순회를 안다면 트리의 모습을 추측할 수 있다
이진트리 + 부모의 값이 항상 왼쪽 자식보다 크고, 오른쪽 자식보다 작다 = 이진 탐색 트리(BST)
- 값의 탐색은 현재 비교 노드보다 크냐,작냐에 따라 왼쪽,오른쪽으로 이동
- 값의 삽입은 들어갈 위치를 찾고, 해당 위치의 부모 노드와 값을 비교한다.
- 부모가 루트라면 루트에 삽입- 부모가 값이 크다면 부모의 왼쪽 자식으로 삽입
- 부모가 값이 작다면 부모의 오른쪽 자식으로 삽입
- 값의 삭제는 탐색이 먼저 이루어지고, 해당 노드의 자식의 상태에 따라 달라진다.
- 자식이 없으면 그냥 삭제- 왼쪽 자식만 있으면 왼쪽 자식을 끌어올린다.
- 오른쪽 자식만 있으면 오른쪽 자식을 끌어올린다.
- 자식이 모두 존재하면, 삭제값 바로 다음값을 찾고 해당 값으로 바꾼다.
- 다음 값의 오른쪽 자식을 다음 값의 위치로 끌어올린다.
- 이진 탐색 트리의 중위 순회의 결과는 오름차순이다.
이진 탐색 트리의 연산의 최악은 O(N), 이를 극복하기 위해 Balanced Binary Search Tree로 O(logN)에 해결할 수 있다.
Heap is 완전 이진 트리
객체가 생성되는 메모리 공간을 뜻하는 Heap이 아니라 최댓값 최솟값을 빠르게 찾는 자료구조 Heap은 완전 이진트리로 구현되어 있다.
- Heap을 구성하는데 소요 되는 시간 O(N)
- 최댓값 혹은 최솟값은 항상 루트 노드에 존재하며 탐색 O(1)
- 데이터 삽입,삭제 O(logN)
힙의 생성은 n/2 노드부터 루트 노드까지 heapify를 수행한다.(logN * N)
- 현재 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 중 최댓값을 찾는다.
- 현재 노드가 최댓값이 아니라면 위치를 바꾸고, 바꾼 위치에서 다시 heapify를 수행한다.
힙의 삽입은 완전 이진 트리를 유지해야하므로 가장 마지막 위치에 삽입하고, 위치를 찾아간다.
힙의 삭제는 루트에서만 일어나며, 완전 이진 트리를 유지해야 하므로, 가장 마지값 위치의 값을 루트로 올리고, 위치를 찾아간다.
삽입과 삭제는 부모와 그리고 자식과의 비교를 통해 이루어진다 O(logN)
