Araina’s Blog

1. 배낭 문제 (Knapsack Problem) 무게와 가격이 다른 여러 물건 중, 가장 효율적으로 배낭을 채우는 방법을 찾아내는 문제. 2. 브루트 포스 검색법 (Brute Force Search) 모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법이다. 확실하게 가장 좋은 방법을 찾아낼 수 있지만 시간이 매우 오래 걸린다. 2.1) 브루트 포스 검색법으로 배낭 문제 해결하기 아무것도 넣지 않은 경우, 무게에는 문제가 없지만 이득도 없다. 보석을 1개씩 넣은 경우, 모든 경우가 최대 무게를 넘지 않으며, 금괴를 넣었을 때 이득이 가장 크다. 보석을 2개씩 넣은 경우, 수정 + 루비 조합을 제외하고는 모두 최대 무게를 초과하며, 가격은 14억으로 금괴 1개만 넣을 때보다 이득이 크다. 보..

1. 트리 (Tree) 데이터 사이의 계층 관계를 표현하는 자료구조. 노드(Node)와 가지(Edge)로 구성되며, 트리의 각 노드는 가지를 통해 다른 노드와 연결된다. 2. 트리 관련 용어 루트 (Root): 트리의 가장 위쪽에 있는 노드. 트리마다 1개만 존재한다. 리프 (Leaf): 가지가 더 이상 뻗어나갈 수 없는 노드. 단말 노드 (Terminal Node) 또는 외부 노드 (Internal Node)라고도 부른다. 비단말 노드 (Non-Terminal Node): 루트 노드를 포함하여 리프를 제외한 모든 노드. 내부 노드(Internal Node)라고도 부른다. 부모 노드 (Parent Node): 특정 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드. 노드의 부모는 1개이다. 루트 노드는..

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..