sik13579 님의 블로그

이진탐색트리의 핵심은 정렬된 상태를 유지하면서 빠르게 탐색하는것 입니다.배열은 정렬하면 탐색은 빠르지만 삽입/삭제가 느리고, 리스트는 삽입은 빠르지만 탐색이 느립니다. 이 이진탐색트리는 그 중간을 노린 구조입니다. 대표적인 활용케이스는1. 검색 시스템값 찾기 : O(log n)예 : 사용자 ID, 세션, 키-값 조회내부적으로는 Redis 같은 시스템도 트리/해시 기반 구조를 섞여 사용합니다.2. 정렬된 데이터 유지항상 왼쪽중위 순회(inorder)하면 자동 정렬예:로그 시간순 정렬점수 랭킹 시스템3. 범위 검색(Range Query)10이상 50이하 데이터만 뽑고싶을때BST는 이런 범위 탐색이 효율적DB 인덱스에서 핵심 개념즉, 삽입/삭제/탐색을 모두 적당히 빠르게 처리하면서 정렬 상태를 유지해야 할 때..

1. 힙 이란?(다시 한 번 짚고 넘어가자)힙은 완전이진트리 형태를 가지면서, 동시에 부모와 자식 사이의 대소관계를 만족하는 자료구조 이다.따라서, 부모가 자식보다 크기만 하다고 해서 다 힙은 아니다.예를 들어보자. 10 / \ 8 9 / 7이건 완전이진트리라서 힙이 될 수 있다. 10 / \ 8 9 \ 7이건 부모-자식 크기 관계는 맞아도, 완전이진트리 모양이 아니므로 힙이 아니다.왜냐하면, 왼쪽 자식의 왼쪽이 비었는데 오른쪽이 차 있으므로, 힙이 아니다. 2. insert 연산 과정step1. 초기 상태 array = [ 5, 7, 9, 10, 8, 6 ]에서 make_heap()으로 정렬한다. step2. 마지막 위치..

1. 트리(Tree)여태까지 봤던 배열, 스택, 큐, 연결 리스트는 대부분 선형 구조이다. 즉 "앞 - 뒤"로 이어지는 구조였음 그런데 트리는 다르게, 계층적 관계를 표현하는 비선형 자료구조이다. 예를 들면 폴더 구조, 조직도, 가족관계, HTML DOM 구조 같은 것을 표현할 때 트리가 잘 맞는다. 트리는 노드와 간선으로 이루어지고, 보통 하나의 루트에서 아래로 가지가 뻗는 형태로 설명된다. 2. 트리는 왜 필요할까?학생 명단을 저장하는 건 배열로도 가능하다. 하지만 "학과장 아래 교수들, 교수 아래 조교들, 조교 아래 학생들" 처럼 상하관계가 있으면 배열은 불편하다. 연결 리스트도 한 줄로만 이어지기 때문에 "누가 누구 밑에 있는가"를 표현하기엔 한계가 있다. 트리는 바로 이런 부모-자식 관계, 즉..

1.make_heap이 무엇인가? make_heap은 힙이 아닌 배열(또는 완전이진트리 형태의 데이터)을 힙 성질을 만족하도록 바꾸는 연산이다. 이 과정을 부모-자식 비교를 통해 재배치하는것. 보통 heapify_down을 반복해서 수행한다A = [3, 8, 2, 5, 1, 7, 6] 이런 형태의 배열이 있다고 해보자. 이건 그냥 배열이지, 아직 힙이라는 보장은 없다. 이걸 최대 힙 또는 최소 힙 조건에 맞게 다시 정리하는게 make_heap이다. 2. 왜 make_heap이 필요할까?힙은 보통 우선순위 큐에 쓰이는데, 처음부터 데이터가 힙 상태로 들어오는게 아니라 그냥 막 들어온 배열인 경우가 많다. 그럴 때 이 전체 데이터를 한 번에 힙 구조로 바꿔야 이후 find_max, delete_max, in..

보호되어 있는 글입니다.

환형 연결 리스트의 경우에는 노드 하나가 head와 tail을 동시에 갖고 있는 구조입니다. class Node: # 환형 연결 리스트의 노드 정의 노드가 head와 tail이 동시에 존재함 def __init__(self, data=None): self.data = data self.next = self self.prev = self따라서, 위와 같이 노드를 정의해줍니다. 환형 연결 리스트에서는 제일 중요한 파트가 splice 연산입니다.조건은 아래와 같습니다.조건 1. a ->... -> b a와 b사이에 값이 존재해야 함조건 2. a와 b사이에 head 노드가 없어야 함, 마찬가지로 a와 b사이에 x노드가 있으면 안 된다.a와 b사이에 있는 만큼을 cu..

1. 한방향 연결 리스트배열은 메모리상에 줄줄이 붙어 있는 느낌이다. 연결 리스트는 노드들이 주소로 이어진 체인이라고 보면 된다. 예를 들어: [10 | • ] -> [20 | • ] -> [30 | None] 여기서 각 [] 칸이 노드(Node)이다. 앞칸 : 데이터 뒤칸 : 다음 노드를 가리키는 주소(next) 즉, 한방향 연결 리스트는 앞에서 뒤로만 따라갈 수 있는 줄줄이 연결된 구조이다. 2. 왜 연결 리스트를 쓸까?배열은 중간에 삽입/삭제할 때 뒤 원소들을 밀거나 당겨야한다. 그런데 연결 리스트는 그게 아니라 앞 노드의 next, 새 노드의 next 이 두 개만 잘 바꾸면 된다. 따라서 연결 리스트는 삽입/삭제에 강하다3. 삽입 연산 : 노드를 끼워 넣는다는 건 무슨 뜻인가?예를 들어: 10..

Queue를 이용한 Josephus 문제 풀이입니다. 1. Queue는 FIFO다.따라서, 선입 선출 형태가 되어야 한다.2. enqueueitems 라는 빈 리스트에 enqueue 메서드는 value를 append한다. 3. dequeue비어있는지 확인하고, 데이터를 추출하여, 위치이동을 시킨다. 그리고 결과 반환 4. Josephus 문제 4-1. Josephus를 원형으로 이해해보자한 바퀴 돌면 제거k 번째 사람 제거제거 안 된 사람은 뒤로 다시 감마지막 1명 남으면 winner4-2. Queue의 FIFO 개념을 연결하자앞에서 꺼내고제거 대상 아니면 뒤로 넣고제거 대상이면 버린다.4-3. front_index 방식으로 queue 구현하자pop(0) 안쓰고front_index를 하나씩 증가시키는 방..

stack을 이용한 계산기 만들기입니다. 반드시 이해해야 할 5개를 나열하고, 그다음 그림을 그려보면서 재차 이해해 봤습니다.1. 스택은 LIFO다. 따라서 최근 것이 먼저 나온다.2. 계산기에서 스택은 연산 순서를 보류하는 용도다.당장 계산 못 하면 쌓아둔다. 3. 연산자 우선순위가 핵심이다.*,/ 가 +, - 보다 먼저이다. 4. 괄호는 우선 계산 범위를 강제로 지정한다.' ( ' 만나면 특별 취급 해준다. 5. 후위표기식(Postfix Expression)은 계산이 엄청 쉽다.숫자는 push, 연산자는 pop 2번 후 계산. 이때, push는 Python에는 없으므로 append로 입력그림으로 이해해 보자.우선 infix에서는 2개의 list를 만든다 하나는 출력될 OUTSTACK와, 하나는 연산자..

자료구조가 왜 필요하나요? -데이터가 몇 개 없으면 아무렇게나 저장해도 돼. 하지만 데이터가 많아지면 문제가 생김 -예를 들어 - 맨 뒤에 추가는 쉬운데 찾기가 느릴 수도 있고 - 찾기는 빠른데 중간 삽입이 어려울 수도 있고 - 순서대로 처리해야 하는 경우도 있고 - 부모-자식 관계처럼 연결해서 표현해야 할 때도 있음 따라서, 상황에 맞는 자료구조를 써야한다. 즉, 자료구조 = 데이터를 효율적으로 저장하고 다루기 위한 구조 ***배열/리스트*** 줄 세워 놓은 칸 예: [ 10, 20, 30, 40 ] 몇 번째 있는지 바로 찾기 쉬움 중간에 끼워 넣거나 빼는 건 번거로울 수 있음 비유 : 아파트 호수처럼 번호가 붙어 있는 칸 ***스택*** 마지막에 넣은 걸 먼저 꺼내는 구조 예: 접시 쌓기 접시를 위..