Algorithms & Data Structure
-
[자료구조] HeapAlgorithms & Data Structure 2022. 1. 21. 19:00
힙 (Heap) 특정 목적을 위해 변형된 트리 구조. 최대값과 최소값을 빠르게 구하기 위한 완전 이진 트리 (완전 이진 트리는 데이터를 삽입할 때 최하단 왼쪽 노드에서 부터 차례대로 시작하는 트리) 배열의 경우, 최대값과 최소값을 찾으면 O(n) 이 걸림 힙의 경우, 최대값과 최소값을 찾으면, 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 힙 (Heap) 구조 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 분류 가능하다. 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. 최소 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다. 완전 이진 트리 형태이..
-
[자료구조] 트리Algorithms & Data Structure 2022. 1. 20. 19:44
트리 (Tree) 1. 트리 구조 트리: Node, Branch로 이루어진 그래프로 사이클을 이루지 않도록 구성한 데이터 구조이다. 트리는 탐색(검색) 알고리즘 구현을 위해 많이 사용된다. Node: 트리에서 데이터를 저장하는 기본 요소. Root Node: 트리 맨 위에 있는 노드 이다. Level: 최상위 노드를 Level 0이며, 하위 Branch로 연결된 노드의 깊이를 나타낸다. Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 자식 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 (가장 맨 끝의 노드) Sibling (Brother Node): 동일한 Parent Node를 가진 노드 Depth: 트리에서 ..
-
[자료구조] 해시 테이블 (Hash Table)Algorithms & Data Structure 2022. 1. 19. 18:31
1. 해시 구조 Key에 Value 값을 저장하는 데이터 구조이다. key만 알면 바로 해당 데이터를 가져올 수 있으므로 속도가 굉장히 빠르다. 파이썬에서는 굳이 해쉬 테이블을 구현하지 않고 딕셔너리 타입을 사용한다. 장점 : 데이터를 읽고 쓰는 속도가 빠르다. 키에 해당하는 데이터가 있는지 확인하기 용이하다. 단점 : 저장 공간이 많이 필요하다. 여러 키가 하나의 주소를 갖고 있는 경우 충돌이 일어 난다. 주요 용도 : 검색이 많이 필요한 경우. 데이터 저장/삭제/읽기를 자주 하는 경우. 2. 해시 테이블 관련 용어 Hash : 임의의 값을 고정 길이로 변환하는 것을 의미한다. Hash Table 또는 Hash Map : 키를 이용하여 value 값을 매핑하는 자료 구조이다. Hashing Functi..
-
[시간 복잡도] 알고리즘 복잡도 표현 방법Algorithms & Data Structure 2022. 1. 18. 15:20
복잡도가 필요한 이유 하나의 문제를 푸는 다양한 방법이 있는데, 어떤 방법이 더 효율적인지 확인하기 위해 필요하다. 알고리즘 복잡도 계산 항목 시간 복잡도 : 알고리즘 실행 속도 공간 복잡도 : 알고리즘이 사용하는 메모리 공간 사이즈 공간 복잡도는 요즘 거의 사용하지 않는다. Big O 표기법 최악의 실행 시간을 표기. 가장 많이 사용하는 표기 방법이다. 최악의 상황이여도 이 정도 성능은 보장한다는 의미이다. 제일 큰 차원수만 표기한다. # O(1) : 무조건 상수만큼 실행 if n > 10: print(n) # O(n) variable = 1 for num in range(3): for index in range(n): print(index) # O( 𝑛2 ) : 300𝑛2 + 1도 결국 𝑛2 vari..
-
[자료구조] 연결 리스트 (Linked List)Algorithms & Data Structure 2022. 1. 14. 22:05
연결 리스트란 데이터를 구조체로 묶어서 포인터로 연결하는 개념을 의미한다. 데이터의 순서가 메모리에 물리적인 순서대로 저장되는 것은 아니다. 즉, 개념 상으로는 1번 그림과 같지만 실제로 저장될 때는 2번 그림과 같다. 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편 특정 인덱스에 접근하기 위해서는 순서대로 읽어야 한다. 즉 탐색을 위해서 O(n) 시간이 소요된다. 데이터를 추가하거나 삭제, 추출할 때는 O(1)에 가능하다. 노드 (Node) : 데이터 저장 단위로 데이터값과 포인터로 구성되어 있다. 포인터 (Pointer) : 노드 내에서 다른 노드와 연결 정보를 갖고 있는 공간을 의미한다. 장점 : 미리 데이터 공간을 할당할 필요가 없다. 단점 : 저장 공간 효율성이 좋지 않다 (연결을 하려면 데이..
-
[자료구조] 큐 (Queue)Algorithms & Data Structure 2022. 1. 13. 21:57
Queue란 무엇인가? 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 데이터 구조이다. FIFO 또는 LILO 정책. 즉, 스택 과는 반대이다. Enqueue : 데이터 넣기 Dequeue : 데이터 빼기 Queue()로 큐 만들기 import queue data_queue = queue.Queue() #데이터 입력 data_queue.put("Good day") data_queue.put(1) #큐 크기 출력 data_queue.qsize() #큐에 입력된 데이터 출력 data_queue.get() LIFO Queue() 마지막 넣은 데이터가 먼저 출력되는 구조. import queue data_queue = queue.LifoQueue() data_queue.put("Good") data_q..
-
[자료구조] 스택 (Stack)Algorithms & Data Structure 2022. 1. 13. 21:06
스택이란? 나중에 들어간 데이터를 가장 먼저 출력하는 구조이다. 쉽게 설명하자면, 뷔페에서 쌓아둔 접시들을 예시로 들 수 있다. 층층이 쌓인 접시들 중에서 가장 마지막으로 쌓은 접시를 손님들은 가장 먼저 가져간다. 스택에 무언가를 삽입하고자 했는데 이 스택이 이미 꽉 찬 상태여서 나타나는 에러를 Stack Buffer Overflow 스택 버퍼 오버플로우라고 한다. 개발자들의 빛과 희망과 같은 스택 오버플로우 웹사이트 이름도 여기에서 유래했다! 깔깔깔. 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 파이썬에서는 스택 자료형을 따로 지원하지는 않지만, 리스트로 만들 수 있다. 스택 : LIFO , FILO LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다. FIFO (Firs..
-
[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)Algorithms & Data Structure 2021. 8. 22. 14:41
탐욕 알고리즘 최적의 값에 가장 가까운 값을 구하는 알고리즘이다. 알고리즘 예시: 동전 문제 4720원을 1원, 50원, 100원, 500원 동전으로 지불 할때, 가장 적은 동전의 개수로 지불하라. coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse = True) for coin in coin_list: coin_num = value // coin total_coin_count += coin_num value -= coin_num * coin details.append([coin, coin_num]) return total_co..