Per ardua ad astra.

큐(Queue) 큐(Queue) 선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조 큐는 양쪽이 뚫려 있는 구조이다. 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다. 큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다. 큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다. 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다. 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다. 첫 번째 데이터 앞을 front가 가리켜야 한다. 데이터 삽입 : enQueue 데이터 추출 : deQueue 구현 ① 큐의 초기화 SIZE = 5 queue = [None for _ in range(SIZE)] fr..

스택(Stack) 스택(Stack) 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다. 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다. 구현 ① 스택의 초기화 SIZE = 5 # 스택의 크기 stack = [None for _ in range(SIZE)] top = -1 ② 데이터 삽입 스택이 꽉 찼는지 확인하는 함수 먼저 스택이 꽉 찼는지 확인한 후 스택에 여유 공간이 있..

이진 탐색(Binary Search) 이진 탐색 원리 정렬된 데이터 집합을 검색하는 경우에는 이진 탐색(Binary Search)을 주로 사용하는데, 순차 탐색에 비해서 엄청난 성능으로 데이터를 검색할 수 있다. 이진 탐색은 전체를 반씩 잘라내서 한쪽을 버리는 방식을 사용한다. 데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다. 찾는 값을 검색하고자 1단계에서 중앙 위치를 기준으로 잡는다. 찾는 값이 왼쪽 구역에 있을 경우, 오른쪽 구역을 버린다. 이 과정을 찾을 값을 찾을 때까지 반복한다. 구현 이진 탐색 구현은 키를 찾기 위해 계속 시작, 중앙, 끝을 반복적으로 1/2씩 줄여 가면서 계산하는 방식이다. 검색할 범위를 1/2씩 반복해서 분할하는 기법을 분할 정복(Divide ..

순차 탐색(Sequential Search) 순차 탐색 어떤 데이터는 정렬되지 않은 상태로 존재하고, 어떤 데이터는 정렬된 상태로 존재한다. 이 두 경우에 데이터를 찾는 방법은 조금 다르다. ① 정렬되지 않은 집합에서의 순차 탐색 검색 성공 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다. 검색 실패 첫 번째 데이터부터 차례로 비교해서 찾지 못할 경우, -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다. def seqSearch(ary, fData) : pos = -1 size = len(ary) print('## 비교한 데이터 ==> ', end = '') for i in range(size) : print(ary[i], end = ' ') if ary[i] == fData..

알고리즘이란? 알고리즘의 개념 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(Procedure) 각 단계는 기본적인 연산(Operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(Subproblem)에 대한 알고리즘일 수는 있지만 충분히 구체적이어야 한다. 알고리즘의 조건 일반적으로 알고리즘은 다음의 두 조건을 반드시 만족해야 한다. 종료(termination) : 모든 가능한 입력 사례에 대하여 반드시 끝난다. 정확성(correctness) : 모든 가능한 입력 사례에 대하여 옳은 답을 출력한다. 좋은 알고리즘 자원(Resource)을 적게 쓰는 알고리즘이 좋은 알고리즘이라고 할 수 있다. 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시..

원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 개념 단순 연결 리스트(Singly Linked List) 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다. 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다. 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다. 원형 연결 리스트의 원리 원형 연결 리스트의 원리 및 구조도 단순 연결 리스트와 많은 부분이 비슷하다...

단순 연결 리스트(Singly Linked List) 단순 연결 리스트의 개념 선형 리스트(Linear List) 장점 배열에 구성하였기 때문에 단순하다. 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다. 프로그램으로 구현하기 비교적 쉽다. 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다. 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생) 단순 연결 리스트(Singly Linked List) 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다. 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다. 데이터와 링크로 구..

선형 리스트(Linear Linked List) 선형 리스트의 기본 개념 데이터를 일정한 순서로 나열한 구조 순차 리스트(Ordered List)라고도 한다. 입력 순서대로 저장하는 데이터에 해당한다. 선형 리스트는 다양한 방법으로 구현할 수 있지만, 가장 기본적인 방법은 배열 을 이용하는 것이다. 선형 리스트는 메모리에서도 차례로 저장된다. 원리 데이터 삽입 1단계 : 맨 끝에 빈칸을 확보한다. 2단계 : 삽입하고자 하는 공간에 빈칸이 없으므로, 삽입하고자 하는 공간 뒤에 있는 요소들을 한칸씩 뒤로 옮긴다. 3단계 : 빈자리에 요소를 삽입한다. 데이터 삭제 원하는 요소가 삭제된 후 빈칸을 그대로 두지 않고 뒤의 요소들을 앞으로 한칸씩 이동시킨다. 선형 리스트의 구현 사용자가 입력하는 데이터가 가변적으로..