프로그래밍 잡동사니

탐색 트리 탐색 트리란 탐색을 위한 트리 기반의 자료구조이다 삭제 연산의 3가지 경우 삭제하려는 노드가 단말(가장 마지막) 노드인 경우 삭제하려는 노드가 왼쪽이나 오른쪽 중 하나의 서브트리를 가지는 경우 (자식이 하나) 삭제하려는 노드가 2개의 서브트리를 모두 가지고 있는 경우 (자식이 둘) 이진탐색트리를 활용해 맵 클래스를 구현해보자 균형이진탐색(AVL)트리 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색트리 * 평균, 최선, 최악의 경우 모두 시간 복잡도 O(logn)을 보장 탐색 연산은 기존 방식과 동일하지만 삽입/삭제 연산의 경우 균형 상태가 깨진다면 불균형 상태의 조상 노드(균형 인수 +-2)의 서브 트리들이 다시 재균형 (회전) + Red-Bl..

트리(Tree) 계층적인 자료의 표현에 적합한 자료 구조 ex) 조직도, 가계도 지금까지 배운 선형 자료 구조들과 다르게 비선형 자료 구조 노드의 ‘부모/자식/형제’ 관계와 ‘조상(부모 이상)/자손’ 관계가 정의된다 계층에 따라 위부터 레벨이 나눠지며 트리의 높이는 최고 레벨 값이다 더 이상 자식이 없는 노드는 단말 노드이며 그렇지 않은 노드는 비단말 노드이다 자식 노드의 수가 해당 노드의 차수이며 트리의 차수는 노드 차수들 중 최대 차수이다 이러한 노드 구조들을 통틀어 포레스트(forest)라고 한다 이진 트리 서브트리는 공집합일 수 있으며 이진 트리는 순환적으로 정의된다 트리의 각 레벨에 노드가 꽉 차있다면 포화 이진 트리이다 * 단, 완전 이진트리의 경우 마지막 레벨 h에서는 노드가 좌측부터 순서대..

정렬(sort) 정렬이란 데이터를 순서대로 재배열하는 것으로 비교가 가능한 모든 속성들이 정렬의 기준이 될 수 있으며 오름차순(ascending order)/내림차순(descending order)이 있다 여러 개의 필드로 구성되는 레코드는 정렬의 대상이며 정렬 키를 기준으로 정렬된다 정렬 알고리즘은 1차적으로 내부 정렬(메인 메모리), 외부 정렬(+외부 기억 장치)로 나뉘며, 단순하지만 비효율적 방법: 삽입, 선택, 버블 정렬 등 복잡하지만 효율적 방법: 퀵, 힘, 병합, 기수 정렬, 팀 등으로 세분화된다 1. 선택 정렬(selection sort) 2. 삽입 정렬(insertion sort) 3. 버블 정렬 +++ 3장의 집합 자료구조를 항상 정렬하도록 수정해보자 탐색과 맵 구조 탐색이란 테이블에서 ..

연결 리스트 그동안 배열에 index를 넣는 구조로 자료 구조를 구현했었는데,, 연결 리스트는 물리적으로 흩어진 데이터들의 노드를 링크로 연결해 사용한다! 연결된 스택 단순 연결 리스트 연결된 큐 이중 연결 리스트

큐(Queue) 후입선출인 스택과 달리 선입선출(FIFO) 구조의 자료구조이다 큐는 일상생활에서 광범위하게 사용된다 ex) 서비스센터 콜, 프린터 인쇄 작업, 실시간 스트리밍 버퍼링, 각종 대기열 등 큐의 구현 앞서 본 직선 형태의 큐가 선형 큐이다 배열을 원형으로 사용하는 원형 큐는 front와 rear가 시계방향으로 돌아간다 클래스 형태 파이썬 리스트로 원형 큐를 구현해보자! 큐를 응용해 너비우선탐색을 해보자 파이썬은 queue모듈로 큐와 스택 클래스를 제공한다! 덱(Deque) 덱(double-ended queue)은 전단과 후단에서 모두 삽입/삭제가 가능하다! 즉, 만들어 둔 원형 큐를 상속받아 일부 기능을 추가해 덱을 구현할 수 있다! 우선순위 큐 선출선입 개념을 가진 큐에 실생활의 우선순위의 ..

스택(Stack) 괄호 검사 같은 종류, 맞는 쌍의 괄호를 순서를 지켜 잘 넣었는지 검사하는 것이다 [ ] { } ( ) 스택을 활용해 괄호 규칙을 검사하는 알고리즘을 작성해보자! 수식의 계산 다음으로는 입력된 중위 표기를 후위 표기로 변환해주는 알고리즘을 짜보자

리스트(list) / 선형 리스트(linear list) 집합과 달리 순서를 가진 항목들의 모임이다 파이썬 리스트 일반적으로 사용하던 파이썬에서의 리스트 개념이다 함수 배열로 구현한 리스트 클래스 배열로 구현한 리스트 라인 편집기 class ArrayList: def __init__( self ): self.items = [] def insert(self, pos, elem) : self.items.insert(pos, elem) def delete(self, pos) : self.items.pop(pos) def isEmpty( self ): return self.size() == 0 def getEntry(self, pos) : return self.items[pos] def size( self ):..

파이썬 리뷰 파이썬은 AI와 빅데이터의 부상과 함께 떠오른 언어로 문법이 직관적이고 쉽다 코드를 한 줄 씩 해석해 실행하는 인터프리터 방식의 언어이다 * 편리하지만 실행 파일이 생성되지 않아 컴파일 방식보다 속도가 조금 느리다 파이썬 자료형(data type) 함수 모듈 객체지향 프로그래밍

자료구조란? 다양한 자료를 효율적인 규칙에 따라 정리한 구조이다. 알고리즘을 어떠한 자료구조로 구성할 것인지 선택할 수 있어야 한다 선형 자료구조: 연속적으로 붙는 연결관계를 가진 자료구조 비선형 자료구조: 복잡하고 계층관계를 가진 자료구조 알고리즘이란? 알고리즘 기술 순서는.. 자연어로 표현 -> 흐름도로 표현 -> 유사 코드로 표현 -> 프로그래밍 언어로 표현 추상 자료형(ADT – Abstract Data Structure) 프로그래머가 추상적(수학적)으로 정의한 자료형 ~ 데이터와 연산이 무엇(what)인지는 정의하지만 어떻게(how) 할지는 모르는 상태 알고리즘의 성능 분석 1. 알고리즘의 실행 시간을 측정하는 방법 ~정확한 측정을 위해 동일한 하드웨어에 실제로 구현해야 하기 때문에 현실적으로 ..