TIL/Data Structures and Algorithms (16) 썸네일형 리스트형 공간복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요한지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 통상 둘 다를 만족시키기는 어려움 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서! 알고리즘은 시간 복잡도가 중심 1. 공간 복잡도 (Space Complexity) 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛)S(P).. (자료구조) 힙 1. 힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리. 무조건 왼쪽부터. (아래 힙 기본동작 그림 참조) 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 최대 힙과 최소 힙 존재 각 노드의 값은 해당 노드의 자식 노드 값보다 크거나 같다(최대 힙) 완전 이진 트리의 형태를 가짐 3. 힙과 이.. (자료구조) 트리구조 (Tree) 1. 정렬된 배열과 해시 테이블의 단점 - 정렬된 배열은 삽입과 삭제가 느리다. 최악의 시나리오(배열 앞에 값 삽입, 배열 첫번째 값 삭제)의 경우 O(N) 시간복잡도 - 해시 테이블은 순서 유지가 안된다. - 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료구조 -> 이진 트리 - 이진 트리와 정렬된 배열의 탐색 비교 2. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용 브랜치가 최대 2개인 트리구조가 이진 트리이다. 3. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 .. (자료구조) 해쉬테이블 1. 해쉬테이블 소개 - 엄청난 룩업 속도를 자랑한다. - 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시맵, 딕셔너리 등이다. - 해쉬테이블의 값 룩업은 평균적으로 O(1)이다. - 원래 해쉬의 뜻은 임의 값을 어떤 고정된 길이의 값으로 변환하는 것을 말한다 - 해쉬함수가 유효하려면 딱 한가지 기준을 충족해야한다. 해쉬 함수는 동일한 문자열을 해쉬 함수에 적용할 때마다 항상 동일한 숫자로 변환해야한다. 2. 해쉬 구조 - Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를.. 알고리즘 복잡도 1. 알고리즘 복잡도 계산이 필요한 이유 - 하나의 문제를 푸는 알고리즘은 무수히 많다. 이를 정량적으로 비교할 수 있어야 어떤 알고리즘이 효율적인지 알 수 있다. 이때 사용하는 것이 바로 알고리즘 복잡도 이다. 2. 알고리즘 복잡도 종류 - 시간복잡도 : 알고리즘 실행 속도, 반복문에 가장 큰 영향을 받는다. - 공간복잡도 : 알고리즘이 사용하는 메모리 용량 - 시간복잡도가 가장 많이 쓰인다. 3. 알고리즘 성능 표기법 - Big 0 표기법: O(N) - 입력 n에 따라 결정되는 시간복잡도 함수 - O(1), O(log n), O(n), O(nlog n), O(n2), O(2n), O(n!)등으로 표기함 - O(1) 반복문이 없는 알고리즘. 아래에서는 n이 100이든, 1000이든 무조건 2회만 실행.. (자료구조) 링크드리스트 (Linked List) 1. 링크드리스트란 - 일반적인 배열이 순차적으로 연결된 공간에 데이터를 나열하는 구조라면, 링크드 리스트(혹은 연결 리스트)는 떨어진 곳에 존재하는 데이터를 포인터로 연결하여 관리하는 데이터 구조이다. - 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마 배열 대신 링크드 리스트를 쓰고 있을 가능성이 크다. 기본구조는 아래와 같다. - Node : 데이터 저장 단위. 실제 데이터값과 포인터로 구성되어있다. 아래 그림 왼쪽이 데이터값, 오른쪽이 포인터이다. - Pointer : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간이다. 아래 그림에서는 다음 노드의 정보만 들어가나 만약 이전, 다음 노드정보가 들어간다면 이를 더블링크드리스트라 부른다. 1. 아래는 파이썬으로 구현한 .. 이전 1 2 다음
