Hello World!

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

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

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 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) 정점과 간선- 정점(vertex)..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 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)의 단말노드(t..

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스) 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) 원하는 원소를 찾을 때까지 순서대로 반복 비교를 수행한다.정렬 과정 없이 바로 탐색을 수행할 수 있지만 탐색 성능 편차가 큰 편이다.- 이진 탐색(binary..