동삼이의 노트북

다이나믹 프로그래밍(Dynamic programming)은 컴퓨터의 연산 속도를 비약적으로 향상시킬 수 있는 방법 중의 하나이다. 이런 다이나믹 프로그래밍으로 해결할 수 있는 가장 대표적인 예는 피보나치 수열이 있다. 피보나치 수열은 1202년 레오나르도 피보나치의 토끼 번식에 관한 문제를 통해 언급되었다. 이 전에도 이 수열에 대한 연구가 진행된 흔적이 발견되었지만, 체계화된 수열 연구를 진행한 레오나르도 피보나치의 이름을 따서 피보나치 수열이라는 이름으로 널리 알려져있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 하는 수열이다. 피보나치 수열의 특징은 아래와 같다. n번째 피보나치 수 = (n - 1) 피보나치수 + (n - 2) 피보나치수 1번째 피보나치수와 2번째 피보나치수는 1임 이러한..

순차 탐색 보통 코딩을 배우다 보면 흔치 않게 탐색 알고리즘을 작성할 때가 많다. 어느 한 리스트에서 특정 값을 찾을 때나 아니면 그 리스트 안에 원소의 개수를 세는 count() 메소드와 같은 방식으로 작성한다. 우리가 흔히 작성하는 탐색 알고리즘은 순차 탐색 알고리즘으로, 리스트안에 원소를 앞에서 부터 하나씩 확인해 가면서 탐색하는 방식이다. 간단히 예를 들어서, 원소 A B C D E가 포함되어 있는 리스트가 있다고 가정할 때, 리스트에서 C 값을 탐색하고자 한다면 앞에서부터 순차적으로 탐색을 시작한다. 첫 번째 원소 A를 비교했을 때, 찾고자 하는 문자열인 C와 다르기 때문에 넘어간다. 두 번째 원소 B를 비교했을 때도 찾고자 하는 문자열인 C와 다르기 때문에 넘어간다. 세 번째 원소 C를 비교할..

정렬(sorting)은 데이터를 특정한 기준에 맞춰 순서대로 나열하는 것을 의미한다. 가령 5, 3, 1, 2, 4 라는 숫자 배열이 있다고 가정할 때, 오름차순으로 정렬을 수행하면 1, 2, 3, 4, 5가 되는 것이다. 이처럼 정렬은 우리 인간의 뇌로 생각하면 간단한 문제다. 눈으로 빠르게 숫자를 읽고 규칙성을 찾아 작은 것 부터 앞에서 순서대로 배치하면 끝이다. 하지만 컴퓨터는 그렇지 않다. 어떤 규칙성을 직관적으로 찾을 수 없으며 정렬의 과정을 구체적으로 명시해야 한다. 내림차순의 경우 파이썬 메소드를 통해 리스트의 원소를 뒤집는 기능이 있기 때문에 이번 정렬에 관한 포스팅에서는 오름차순의 경우만 다루려고 한다. 위와 같은 카드 뭉치가 일렬로 9장이 있다. 이 카드들을 다양한 정렬 알고리즘을 통해..

이전 포스팅에서 탐색 알고리즘을 이해하기 위해 스택과 큐, 재귀함수에 대한 내용을 다뤘다. 이번 포스팅에서는 탐색 알고리즘 종류 중 하나인 DFS(Depth-First Search)에 대해 알아보고자 한다. DFS는 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며, 노드는 정점(Vertex)이라고도 부른다. 그래프를 탐색한다는 것은, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 의미하며 이 때 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다. 그래프를 프로그래밍에서는 두가지 방법으로 표현할 수 있는데. 하나는 인접 행렬 방식이고 하나는 인접 리스트 방식이다. 인접 행렬(Adjac..

탐색 알고리즘 문제 중에서 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데, 이를 이해하기 위해서는 스택과 큐에 대한 이해가 필요하다. 스택과 큐에 대해 설명하기에 앞서, 자료 구조(Data Structure)란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그 중 스택과 큐는 자료 구조의 기초 개념으로 다음 두 핵심적인 함수로 구성된다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 이 외에도 스택과 큐를 사용할 때 오버플로와 언더플로를 고민해야 한다. 오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘긴 상태에서 삽입 연산을 수행할 때 발생하고, 언더플로는 특정한 자료구조에 데이터가 들어있지 않은 상태에서 삭제연산을 수행할때 발생한다..