Priv's Blog

1. 리스트 (List) 순서가 존재하는 데이터를 늘어놓은 형식의 자료구조. 구조가 단순한 리스트로 선형 리스트(Liner List) 또는 연결 리스트(Linked List)가 있다. 스택(Stack), 큐(Queue)도 리스트의 일종이다. 한 가지 주의할 점은, python의 리스트 자료형은 다른 언어의 리스트 자료형과 차이점이 있다는 것이다. 2. 연결 리스트 (Linked List) 여러 개의 노드(Node)가 주소를 참조하는 형식으로 연결되어 있는 구조의 리스트. 노드란, 연결 리스트를 이루는 각각의 원소(Elemet)들이다. 데이터와 뒤쪽 노드를 참조하는 포인터로 구성되어 있다. 노드의 종류로는 다음과 같다. 머리 노드 (Head Node): 연결 리스트 맨 앞의 노드 꼬리 노드 (Tail No..

1. 정렬이란? 데이터의 집합을 일정한 순서로 바꿔 늘어놓는 작업. 정렬된 데이터 집합의 순서에 따라 오름차순 정렬과 내림차순 정렬로 구분된다. 정렬 알고리즘의 핵심은 교환, 선택, 삽입이다. 대부분의 정렬 알고리즘들이 이 3가지 핵심 요소들을 다양한 방법으로 응용하고 있다. 2. 안정적인 정렬 알고리즘 (Stable Sorting Algorithm) 정렬되기 전 데이터 집합에서 값이 동일한 데이터가 2개 이상일 때, 정렬을 수행한 이후에도 정렬 이전의 순서가 유지되는 알고리즘을 안정적인 정렬 알고리즘이라고 부른다. 안정적이지 않은 정렬 알고리즘도 존재한다. 이는 정렬을 수행한 이후에도 정렬 이전의 순서가 유지될 것이라는 보장이 없는 알고리즘이다. 3. 내부 정렬과 외부 정렬 뒤섞인 카드가 30장이 있고..

1. 하노이의 탑 (Towers of Hanoi) 1883년 프랑수아 E. A. 뤼카가 개발한 게임 퍼즐. 기둥 3개를 이용해서 원반을 옮겨 쌓은 문제로, 규칙은 다음과 같다. 1번째 기둥에 크기가 모두 다른 원반이 크기 순으로 쌓여 있다. 원반은 1개씩 옮겨 쌓을 수 있다. 큰 원반은 작은 원반 위에 쌓을 수 없다. 1.1) 원반이 3개일 경우 원반 1과 원반 2를 그룹으로 묶어서 중간 기둥으로 이동시킨다. 원반 3을 목표 기둥으로 이동시킨다. 그룹(원반 1, 2)을 목표 기둥으로 이동시킨다. 1.2) 원반이 2개인 경우 원반 1을 중간 기둥으로 이동시킨다. 원반 2를 목표 기둥으로 이동시킨다. 원반 1을 목표 기둥으로 이동시킨다. 1.3) 원반이 4개인 경우 원반 1, 2, 3을 그룹으로 묶어 중간 ..

1. 재귀 (Recursion) 재귀란, 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 말한다. 어떤 문제를 해결하는 과정에서 자신과 같지만, 크기가 다른 문제를 발견하고 이들 간의 관계를 파악하여 간명하게 문제를 해결하는 방식이다. 재귀를 사용하면 프로그램을 간결하고 효율적으로 작성할 수 있다. 병합 정렬, 퀵 정렬, 이진 검색 트리 알고리즘에 활용된다. 1.1) 자연수의 재귀적 정의 (Recursive Definition) 1은 자연수다. 1 다음의 자연수는 자연수다. 1 다음의 자연수의 다음의 자연수는 자연수다. 즉, 어떤 자연수의 바로 다음 수도 자연수다. 1.2) 재귀적 구조 (Recursive Structure) 어떤 문제 안에 크기만 다를 뿐, 성격이 다른 ..

1. 큐 (Queue) 큐는 스택과 같이 데이터를 임시 저장할 때 사용하는 대표적인 자료구조이다. 선입선출(FIFO) 방식에 따라 데이터를 입출력한다. 인큐(Enqueue): 큐에 데이터를 추가하는 작업 디큐(Dequeue): 큐에서 데이터를 꺼내는 작업 프런트(Front): 큐의 맨 앞 원소 (데이터를 꺼내는 쪽) 리어(Rear): 큐의 맨 뒤 원소 (데이터를 추가하는 쪽) 2. 배열을 큐로 구현한다면? 크기가 8인 배열 객체 que[ ]를 구현한다고 가정해보자. 2.1) 24를 인큐 맨 끝 데이터 que[3] 다음 원소인 que[4]에 24를 저장한다. 시간 복잡도는 O(1)으로, 비교적 적은 비용이 발생한다. 2.2) 19를 디큐 맨 앞 데이터 que[0]을 꺼내고, 모든 원소를 앞으로 이동시킨다...

1. 스택 (Stack) 스택은 데이터를 임시 저장할 때 사용하는 대표적인 자료구조이다. '마른 풀을 쌓은 더미' 또는 '겹겹이 쌓아놓은 책'의 모습을 연상하면 된다. 후입 선출(LIFO: Last In First Out) 방식에 따라 데이터를 입출력한다. 푸시(Push): 스택에 데이터를 넣음 팝(Pop): 스택에서 데이터를 꺼냄 꼭대기(Top): 스택에 데이터를 푸시하고 팝 하는 윗부분 바닥(Bottom): 스택의 맨 아랫부분 2. FixedStack 클래스 구현하기 이제 스택 자료구조를 직접 코드로 구현해보자. 여기서는 크기가 고정된 스택 클래스를 구현한다. from typing import Any class FixedStack : class Empty(Exception) : pass class F..

1. 정렬된 배열에 원소를 추가하는 알고리즘 이진 검색으로 원소가 추가될 위치를 확인한다. 검색 실패 시, 중앙에 위치한다. 원소가 이동하는 데 필요한 시간 복잡도는 O(n)이다. 원소 삭제 시에도 동일한 비용이 발생한다. 2. 해시법 (Hashing) 해시법이란, 간단한 연산을 통해 데이터를 저장할 위치를 구하는 방법이다. 원소의 검색 외에 추가 및 삭제 작업도 효율적으로 구현할 수 있다. 데이터의 저장과 검색에 극단적인 효율을 가지고 있어 빠른 응답을 요구하는 프로그램에 활용된다. 해시값 (Hash Value)이란, 해시법을 통해 계산된 데이터 저장 위치(인덱스)를 말한다. 해시 테이블 (Hash Table)이란, 해시값을 인덱스로 하는 배열을 말한다. 버킷 (Bucket)이란, 해시 테이블에서 원소..

1. 이진 검색 (Binary Search) 이진 검색 알고리즘이란, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘이다. 이진 검색 트리를 기반으로 동작하며, 주목한 원소보다 값이 크면 우측으로, 값이 작으면 좌측으로 움직이면서 검색을 진행한다. 주목한 원소가 이동할 때마다 검색 범위가 1/2로 줄어든다. 정렬된 배열에 대해서 선형 검색보다 매우 빠르게 검색이 가능하다. 이진 검색의 종료 조건은 다음과 같다. 중앙 원소가 키 값과 일치하는 경우, 검색 성공 검색 범위가 더 이상 없는 경우, 검색 실패 from typing import Any, Sequence def bin_search(a: Sequence, key: Any) -> int : pl = 0 pr = le..