힙
2021. 8. 16. 11:24
🕶 Algorithm/자료구조
힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 힙 (Heap) 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 가장 높은 값이 루트인 힙 = 최대 힙 가장 낮은 값이 ..
그래프
2021. 8. 8. 12:40
🕶 Algorithm/자료구조
그래프 (Graph) 란? 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 예제 집에서 회사로 가는 경로를 그래프로 표현한 예 그래프 (Graph) 관련 용어 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그..
공간복잡도
2021. 7. 22. 16:33
🕶 Algorithm/자료구조
알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요한지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 통상 둘 다를 만족시키기는 어려움 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서! 알고리즘은 시간 복잡도가 중심 공간 복잡도 대략적인 계산은 필요함 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도 있음 아래와 같은 ..
트리
2021. 7. 20. 15:34
🕶 Algorithm/자료구조
트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node) : Child No..
해쉬 테이블
2021. 7. 19. 17:20
🕶 Algorithm/자료구조
해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 알아둘 용어 해쉬(Hash) : 임의 값(방대한 데이터)을 고정 길이(ex. 256)로 변환하는 것 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function) : Key(키를 ..
시간복잡도
2021. 7. 16. 18:55
🕶 Algorithm/자료구조
알고리즘 복잡도 계산이 필요한 이유 시간복잡도 : 알고리즘의 풀이 시간을 정략적으로 표기하는 방법 하나의 문제를 푸는 알고리즘은 다양할 수 있음. 즉, 풀이가 다양하다. 정수의 절대값 구하기 1, -1 ->> 1 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소 반복문을 가지고 시간복잡도를 계산한다. 시간이 어디에서 제일 많이 걸리느냐를 보면 반복문이다..
연결 리스트 (Linked List)
2021. 7. 16. 11:31
🕶 Algorithm/자료구조
연결 리스트(Linked List) Linked List 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 연결 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 미리 데이터 크기를 예약해 놓지 않고, 필요할 때마다 추가추가 하는 것 : 배열의 단점을 극복한 구조 Linked List 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 * 일반적인 링크드 리스트 형태 파이썬에서 링크드 리스트 구현시 class..
자료구조, 알고리즘, 배열, 스택, 큐
2021. 7. 15. 11:31
🕶 Algorithm/자료구조
자료구조 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 대표적인 자료구조 : 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등 알고리즘 어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍 얼마나 시간이 걸리느냐, 얼마나 메모리를 차지하느냐가 주 요소 따라서 코드를 짰을 때 얼마나 메모리를 차지하고 얼마나 시간이 걸렸는지 알고 있어야 한다. 자료구조와 알고리즘이 중요한 이유 어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 천지차이이다. 배열(Array) 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 유사한 데이터를 연결된 데이터 공간에 넣을 수 있다. 파이썬에서는 리스트 타입이 배열의 기능을 제공한다. 배열이..