|
|
| 1번째 줄: |
1번째 줄: |
| == 자료구조 ==
| |
|
| |
|
| > data structure는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.
| | === 복잡도 === |
|
| |
|
| 
| |
|
| |
|
| === 💡 빅오 표기법 === | | ==== 시간 복잡도 ==== |
|
| |
|
| * '''불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적'''으로 사용
| | 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 말한다 |
| * 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
| |
| * Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다.
| |
| - '''시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수'''를 나타낸다.
| |
| - '''공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양'''을 나타낸다.요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.
| |
| * Big-O의 복잡도를 나타내는 표
| |
|
| |
|
| 
| | 어떠한 알고리즘의 로직이 얼만큼 걸리는지 시간을 나타내는데 쓰이며, 보통 빅오 표기법으로 나타낸다 |
|
| |
|
| === 💡 시간 복잡도 ===
| | 빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다 |
|
| |
|
| * 알고리즘의 성능을 설명하는 것
| | 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 없앤다 |
| * 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것
| |
|
| |
|
| '''시간복잡도에서 가장 큰 영향을 미치는 n의 단위'''
| | n^2 + 3 -> n^2 |
|
| |
|
| <syntaxhighlight>
| | 시간 복잡도의 속도는 다음과 같다 |
| 1 O(1) --> 상수
| |
| 2n + 20 O(n) --> n이 가장 큰영향을 미친다.
| |
| 3n^2 O(n^2) --> n^2이 가장 큰영향을 미친다.
| |
| </syntaxhighlight>
| |
|
| |
|
| '''시간복잡도의 문제해결 단계'''
| | O(n^2) > O(n) > O(logn) > O(1) |
|
| |
|
| <syntaxhighlight>
| |
| O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
| |
| O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
| |
| O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
| |
| O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
| |
| O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
| |
| O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
| |
| </syntaxhighlight>
| |
|
| |
|
| === 💡 공간 복잡도 === | | ==== 공간 복잡도 ==== |
|
| |
|
| * 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
| | 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다 |
| * `총 공간 요구 = 고정 공간 요구 + 가변 공간 요구`
| |
| * '''고정 공간'''은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
| |
| * '''가변 공간'''은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간
| |
|
| |
|
| <syntaxhighlight>bash
| | 정적 변수, 재귀 함수 등 동적으로 공간을 필요로 하는 경우도 포함한다 |
| int a[1004];// a 배열은 1004 x 4 바이트의 크기를 가지게 된다.
| |
| </syntaxhighlight>
| |
|
| |
|
| === 💡 자료구조의 시간 복잡도 === | | === 선형 자료구조 === |
|
| |
|
| 
| | 자료 구조의 요소가 순차적으로 나열되어 있는 구조이다 |
|
| |
|
| == 선형 자료 구조 == | | ==== 연결 리스트 ==== |
|
| |
|
| > 요소가 일렬로 나열되어 있는 자료 구조
| | 시간 복잡도 |
|
| |
|
| === 💡 Array vs Linked List ===
| | * 삽입, 삭제 : O(1) |
| | * 탐색 : O(n) |
|
| |
|
| ==== 💡 Array ====
| | 데이터와 노드에 대한 주소를 담고 있는 노드 단위로 요소를 가지고 있다 |
|
| |
|
| * 가장 기본적인 자료구조
| | 주소를 어떻게 가지고 있는지에 따라 연결 리스트의 종류가 결정된다 |
|
| |
|
| * 논리적 저장 순서와 물리적 저장 순서가 일치
| | 싱글 연결 리스트 : 다음 노드의 주소만 가지고 있는 연결 리스트 |
|
| |
|
| * 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
| | 이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있는 연결 리스트 |
|
| |
|
| → 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-'''O(1)'''에 해당 원소로 '''접근'''할 수 있다.
| | 원형 이중 연결 리스트 : 이중 연결리스트이면서 마지막 노드가 첫 번째 노드의 주소를 가지고 있는 연결 리스트 |
|
| |
|
| → 즉 '''random access''' 가 가능하다는 장점
| | ==== 배열 ==== |
|
| |
|
| '''BUT'''
| | 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다 |
|
| |
|
| * '''삭제''' 또는 '''삽입'''의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다.
| | 정적 배열 기준 시간 복잡도 |
|
| |
|
| * 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생긴다. | | * 삽입, 삭제 : O(n) |
| | * 탐색 : O(1) |
|
| |
|
| * 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 '''O(n)'''가 된다.
| | 보통 데이터 추가와 삭제를 많이 하는 것은 연결 리스트를 사용하고, 탐색을 많이 하는 것은 배열을 쓴다 |
|
| |
|
| * 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 '''O(n)'''이 된다.
| | ==== 벡터 ==== |
|
| |
|
| * 삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 '''O(n)'''의 시간을 요구하게 된다.
| | 동적으로 요소를 할당할 수 있는 동적 배열이다 |
|
| |
|
| ==== 💡 '''Linked List''' ====
| | 컴파일 시점에 배열의 크기를 지정할 수 없다면 벡터를 사용해야 한다 |
|
| |
|
| * 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
| | 시간 복잡도 |
|
| |
|
| 
| | * 탐색, 맨 뒤 요소 삭제, 삽입 : O(1) |
| | * 맨 뒤나 앞이 아닌 요소 삽입, 삭제 : O(n) |
|
| |
|
| * prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것
| | ==== 스택 ==== |
| * 단순 연결 리스트 : next 포인터만 가진다.
| |
| * 원형 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.
| |
| * 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
| |
|
| |
|
| ---
| | LIFO 성질을 가진다 |
|
| |
|
| * 배열의 문제점을 해결하기 위한 자료구조가 linked list
| | 시간복잡도 |
|
| |
|
| * 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. | | * 삽입, 삭제 : O(1) |
| | * 탐색 : O(n) |
|
| |
|
| * 따라서 이 부분만 다른 값으로 바꿔주면 '''삭제와 삽입'''을 '''O(1)''' 만에 해결할 수 있는 것이다.
| | ==== 큐 ==== |
|
| |
|
| '''BUT'''
| | FIFO 성질을 가진다 |
|
| |
|
| * 하지만 Linked List 역시 한 가지 문제가 있다.
| | 시간복잡도 |
|
| |
|
| * 원하는 위치에 삽입을 하고자 하면 '''원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인'''해봐야 한다는 것이다. '''Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문'''이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. | | * 삽입, 삭제 : O(1) |
| | | * 탐색 : O(n) |
| * 이 과정 때문에, '''어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서(탐색) O(n)의 시간이 추가적으로 발생'''하게 된다.
| |
| | |
| * 결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다.
| |
| | |
| → 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.
| |
| 
| |
| | |
| '''<배열과 연결 리스트 비교>'''
| |
| | |
| <aside>
| |
| | |
| '''배열''' '''→''' '''탐색 O(1) | 삽입, 삭제 O(n)'''
| |
| '''연결 리스트 →''' '''탐색 O(n) | 삽입, 삭제 O(1)'''
| |
| | |
| </aside>
| |
| | |
| _배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다._
| |
| | |
| _연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다._
| |
| | |
| _탐색은 배열이 빠르고 연결 리스트는 느리다. 배열의 경우 그저 상자 위에 있는 요소를 탐색하면 되는 반면에, 연결 리스트는 상자를 열어야 하고 주어진 선을 기반으로 순차적으로 열어야 한다._
| |
| | |
| _하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느리다. 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문이다._
| |
| | |
| _따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다._
| |
| | |
| === 💡Vector ===
| |
| | |
| * 동적으로 요소를 할당할 수 있는 동적 배열
| |
| * 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.
| |
| * 또한, 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
| |
| * 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸린다.
| |
| | |
| === 💡 Stack and Queue ===
| |
| | |
| 
| |
| | |
| ==== 💡 Stack ====
| |
| | |
| * 선형 자료구조의 일종으로 `Last In First Out (LIFO)` . 즉, 나중에 들어간 원소가 먼저 나온다.
| |
| * 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다.
| |
| * 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.
| |
| * 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조이다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
| |
| | |
| ==== 💡 Queue ====
| |
| | |
| * 선형 자료구조의 일종으로 `First In First Out (FIFO)`. 즉, 먼저 들어간 놈이 먼저 나온다.
| |
| * Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다.
| |
| * 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 `Priority queue`등을 사용할 수 있다.
| |
| * 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료 구조이며, 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
| |
| | |
| > [참고자료](https://blog.chulgil.me/algorithm/) > [참고자료](https://madplay.github.io/post/time-complexity-space-complexity) > [참고자료](https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list) > [참고자료](https://osy0907.tistory.com/82?category=911997)
| |
