Hello World!

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 12.1 이진 탐색 트리 (binary search tree) 1) 이진 탐색 트리 - 이진 탐색 알고리즘을 적용하여 원소들을 저장한 이진 트리 - 다음의 조건을 만족해야 한다. 트리 내의 모든 원소는 유일해야 한다. 루트는 자신의왼쪽 서브트리에존재하는 모든 노드보다 크고, 오른쪽 서브 트리의 모든 노드보다 작다. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. - 평균 탐색 시간(h = 트리의 높이) : O(h) 2) 이진 탐색 트리의 노드 탐색 - 탐색 키와 중간 값을 비교한 후 결과에 따라 탐색 성공, 왼쪽 서브 트리 탐색, 오른쪽 서브트리 탐색 중 하나이다. - 재귀적 이진 탐색 트리 def rbst(root, it..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 11.1 순차 탐색 1) 탐색 (search) - 주어진 레코드 집합에서 특정 키(key)와 일치하는 원소를 찾는 작업 - 키 필드 (key field) : 레코드의 여러가지 속성(attribute) 중 탐색 기준이 되는 속성 - 레코드들이 미리 정렬되어 있는 경우 탐색 효율이 높아진다. - 탐색 알고리즘의 종류 : 순차 탐색, 이진 탐색, 보간 탐색, 해싱 탐색 등 2) 순차 탐색 (sequential search) - 탐색 대상에 아무 조건이 없으며 탐색 키를 찾을 때까지 순차적으로 반복 비교하는 방법 - 원소들이 미리 정렬될 필요는 없지만 탐색 성능에 큰 편차가 발생한다. - 시간 복잡도 : O(n) - 코드 def seq_se..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 10.1 최단 경로 탐색 (shortest path finding) 1) 최단 경로 탐색 - 그래프의대표적인 문제 중 하나 - 탐욕 알고리즘, 다익스트라 알고리즘, 플로이드-와샬 알고리즘 등이 있음. 2) 탐욕 알고리즘 (Greedy algorithm) - 출발지에서 최소 비용 간선만을 포함하여 미 방문 노드로 이동하는 경로 탐색 방법 - 목적지에 도달할 때까지 위 과정을 반복한다. - 매 순간 최적이라고 판단하는 것을 반복적으로 선택한다. - 지역적인 해(local solution)를 제공해줄 수 있지만, 전역적인 해(global solution)를 보장하지는 않는다. 3) 다익스트라 알고리즘 (Dijkstra) - 노드 간의 최단..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 9.1 그래프의 개념 1) 오일러 회로 (Eulerian circuit) - 모든 간선을 한 번씩만 이용해 출발 위치로 돌아온다. - 각 정점의 차수가 짝수여야 한다. 2) 오일러 경로 (Eulerian trail) - 모든 정점을 한 번씩만 방문하고 출발 위치오 종착 위치가 다르다. - 출발점과 종착점을 제외한 정점의 개수가 짝수여야 한다. 3) 그래프 - 통신망이나 도로망의 관리, 최단거리 경로 탐색,소셜 네트워크 분석 등 다양한 분야에 활용된다. - 그래프로 해결 가능한 통신망 문제의 예 네트워크의 연결성 확인 네트워크에서 컴포넌트 탐색 연결 네트워크를 유지하는 데 필요한 최소 간선 수 9.2 그래프의 용어 1) 정점과 간선 -..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 8.1 정렬의 종류 1) 정렬 - 주어진 원소(레코드)들을 원하는 기준에 의해 나열하는 작업 - 내부 정렬(internal sort) : 정렬 작업을 주 메모리에서 처리한다. - 외부 정렬(external sort) : 정렬 작업을 외부 기억장치에서 처리한다. 2) 외부 정렬 - 정렬한 원소 개수가 메모리 개수보다 큰 경우 수행한다. - 정렬 과정 (전체 원소의 수 : n, 메모리의 크기 : m) n개의 원소를 m으로 나누어 n/m개의 세그먼트로 분할한다. 각 세그먼트를 주 메모리에 로드하여 내부 정렬 알고리즘으로 정렬한 후 다시언래의 하드 디스크 위치에 저장한다. 정렬된 2개의 세그먼트 쌍에 대해서 합병 정렬을 수행한다. 하나의 정..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 7.1 최대 최소힙 1) 최대 힙 (max heap) - 최대 트리 (max tree) : 이진 트리에서 각 노드의 키 값이 그 자식 노드보다 큰 트리 - 최대 힙: 최대 트리의 조건을 만족하는 완전 이진 트리 - 루트에 전체 노드의 최댓값이 저장되므로 최대값을 탐색하는 데 유용하다. 2) 최소 힙 (min heap) - 최소 트리 (min tree) : 각 노드 값이 그 자식 느도보다 작은 트리 - 최소 힙 : 최 소 트리이면서 완전 이진 트리 조건을 만족하는 경우 - 루트에 전체 노드의 최솟값이 저장된다. 3) 최대 힙에 노드 추가 - 최대 트리와 완전 이진 트리의 조건을 모두 만족해야 한다. 완전 이진 트리의 조건을 만족하기 위..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 6.1 이진 트리의 정의1) 트리(tree)- 루트(root)와 루트의 서브트리(sub-tree)로 구성된 계층형(hierarchical) 자료구조 - 최소 하나 이상의 노드가 있어야 한다. - 서브 트리는 부모 노드를 제거한 후 남은 부분 트리 - 계통도, 조직도, 폴더의 구조 등 계층적 구조를 갖는 영역에서 활용된다. 2) 이진 트리(binary tree)- 각 노드가 최소 2개의 자식 노드를 갖도록 제한하는 트리 - ex) 허프만 코딩 트리 (Huffman coding tree) 허프만 코딩 : 가변 길이 부호화를 사용하여 텍스트 문서를 압축하는 방법 각 문자를 출현 빈도에 따라 나열한다. 출현 빈도를 순서대로 트리(tree)의..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 5.1 연결 리스트 개요 1) 연결 리스트의 종류 - 연결리스트 (linked list) : 노드들이 링크에 의해 순차적으로 연결된 자료구조 - 노드는 값을 저장하는 공간과 노드를 연결하는 링크(link)로 구성된다. - 단일 연결 리스트 (singly linked list) : 노드들이 한 방향으로만 연결된 구조 - 이중 연결 리스트 (doubly linked llist) : 앞 뒤 양방향으로 연결된 구조 - 체인(chain) : 연결 리스트가 마지막 노드(마지막 노드 링크에 None이 저장됨.)에서 끝나는 구조 - 순환 연결 리스트 (circular linked list) : 마지막 노드가 첫 노드와 연결되는 구조 2) 연결 리스..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 4.1 스택 (stack) 1) 스택 - 선형 리스트의 특별한 형태 - 나중에 들어가는 원소가 가장 먼저 나오는 후입선출(LIFO; Last In First Out) 구조 - 함수 호출 관리, 문법 검사(syntax checking), 수식 평가(expression evalution) 등에 많이 사용한다. - top : 마지막으로 추가된 원소를 가리키는 변수 - push : 스택에 원소를 추가하는 연산 - pop : 스택에서 원소를 삭제하는 연산 - 정적 배열로 스택을 구현할 경우, push 함수는 스택에 원소를 추가하기 전에 'stack full' 상태인지, pop 함수는 스택에서 원소를 꺼내기 전에 스택이 빈 상태(top이 -1)..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 3.1 재귀호출의 개념 - 재귀호출(recursion) : 함수의 실행 중에 자기 자신을 다시 호출하는 상황 - 함수가 실행되면 함수의 실행 환경 정보(지역변수, 복귀주소 등)가 저장된 활성 레코드가 생성되어 시스템 스택에 추가된다. -> 재귀함수는 호출되는 횟수만큼 활성 레코드가 스택에 쌓임. - 재귀 호출을 멈추는 조건인 종결 조건(exit condition)을 잘못 설정하면 무한 루프에 빠지게 된다. 3.2 이진 탐색 1) 이진탐색 - 순차 탐색(sequential search) 원하는 원소를 찾을 때까지 순서대로 반복 비교를 수행한다. 정렬 과정 없이 바로 탐색을 수행할 수 있지만 탐색 성능 편차가 큰 편이다. - 이진 탐색(..