Algorithm

재귀 함수로 구현할 수 있는 대표적인 문제는 바로 팩토리얼 (Factorial) 문제이다. 팩토리얼이란 수학에서 그 수보다 작거나 같은 모든 자연수의 곱이다. n이 하나의 자연수일 때, 1부터 n 까지의 모든 자연수의 곱을 n! (n 팩토리얼) 로 표현하는 것이다. 팩토리얼을 구하는 방식은 두 가지로 떠올릴 수 있다. 반복문을 통하여 자연수의 곱을 구하는 방식 재귀 함수를 통하여 자연수의 곱을 구하는 방식 재귀 함수로 이 문제를 해결하였을 때의 장점은 무엇일까? 바로 소스코드가 간결해진다는 것이다. 그러한 이유는 재귀 함수가 수학의 점화식 (재귀식)을 그대로 소스코드로 옮겼기 때문이다. 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미하는데 팩토리얼을 수학적..

앞의 게시물에서도 이야기 했듯이 재귀 함수에는 반드시 적절한 종료 조건이 존재해야 한다. 따라서 문제를 해석하고 알고리즘을 구현할 때 언제 어떻게 재귀 호출을 종료하고 return 해야 하는지를 생각해야 할 것이다. 종료 조건을 추가한 재귀 함수에 대한 예시 소스코드이다. def recursive(i): if i == 100 : return print(i,"번째 재귀함수가 ",i+1,"번째 재귀함수 호출") recursive(i+1) print(i,"번째 재귀함수 종료") recursive(1) 이전의 예시와 유사하지만 recursive 함수에서 ' i '라는 매개변수가 존재한다. 먼저 가장 마지막 줄인 recursive(1)의 구문으로 재귀 함수가 매개변수 i에 1의 값을 갖고 호출된다. if 조건문에..

재귀 함수란 쉽게 이야기해서 함수내에서 자기 자신을 다시 호출하는 함수를 말한다. 즉, 함수A가 함수 내에서 자기 자신인 함수A를 호출하는 것이다. 간단한 예시로 아래와 같은 코드를 들 수 있다. def recursive(): print("재귀 함수 호출") recursive() recursive() 위의 예시에 대해 해석해보면 먼저 가장 아랫줄의 코드를 통해서 함수 recursive가 호출되게 된다. 그 이후 함수 내에서 "재귀 함수 호출" 이라는 메시지를 출력하게 되고 다음으로 다시 recursive 함수를 호출한다. 다음 호출에도 똑같은 과정이 반복될 것이고 따라서 무한으로 메시지가 출력되며 계속 함수가 호출되게 된다. 물론 파이썬에서는 재귀의 최대 깊이가 존재하기 때문에 어느정도 재귀 함수가 호출..

지난 게시물에서 스택과 큐 중 스택에 대한 내용을 다루었다. 이번 게시물에서는 큐에 대해서 이야기 해 보려고 한다. 큐는 아래와 같이 정의 내릴 수 있다. 큐 (Queue) 란 맛집에서 서는 대기줄과 같다. 대기줄을 설 때 처음 줄을 선 사람은 가장 앞에 서고 점점 그 뒤에 사람들이 대기줄을 서게 된다. 이후 자리가 나게 되면 대기줄의 가장 첫 사람이 식당으로 들어가게 된다. 이러한 비유는 큐를 설명하는데 매우 적합하다. 이를 큐에서의 데이터 삽입, 삭제와 비유하면 다음과 같다. - 삽입 (push / add) : 대기줄에 한 명씩 차례대로 서는 것 - 삭제 (pop / delete) : 대기줄의 가장 앞에서부터 한 명씩 빠지는 것 스택과는 반대로 큐는 선입선출 (First In First Out, FI..

이전 게시물에서 자료구조의 기본 개념이 되는 스택과 큐 라는 구조에 대한 간단한 설명을 게시했다. 이번에는 스택에 대해서 자세히 다뤄보려고 한다. 먼저 스택이란 책의 인용을 빌리면 아래와 같다. 스택 (Stack) 이란 박스 쌓기와 같다. 박스를 쌓을 때는 아래에서부터 차곡차곡 위로 쌓고 박스를 제거할 때는 위에서부터 하나씩 제거하게 되는데 이러한 구조가 스택과 매우 유사하다. 이를 앞의 게시물에서 설명한 핵심 함수에 비유하면 다음과 같다. - 삽입 (push) : 박스를 아래에서부터 한 층씩 쌓는 것 - 삭제 (pop) : 박스를 위에서부터 한 층씩 제거하는 것 이와 같이 스택은 선입후출 (Last In First Out, LIFO) 의 방식으로 데이터를 삽입, 삭제한다. 즉, 스택은 데이터의 삽입과 ..

Chapter 5. DFS/BFS를 들어가기 앞서 자료구조에 대한 기초적인 지식이 필요하다. 먼저 탐색(Search)과 자료구조(Data structure)에 대해서 알아본다. 탐색이란 많은 양의 데이터 중에서 자신이 원하는 데이터를 찾는 과정을 의미한다. 뒤에서 작성하게 될 그래프, 트리 등의 자료구조 내에서 원하는 데이터를 찾는 알고리즘이 자주 등장할 것이다. 대표적으로 DFS 혹은 BFS 등의 탐색 알고리즘이 존재한다. 이러한 탐색 알고리즘을 정확하게 이해하기 위해서는 자료구조에 대한 이해가 필요하다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그 중 스택(Stack)과 큐(Queue)는 자료구조의 기초 개념이며 자세한 내용은 다음 게시글에서 다루기로 한다. 스택과 큐..

문제) 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 ( A, B )로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 (반시계 방향으로 90도 회전한 방향) 부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로..

문제) 8 x 8의 체스판에서 나이트가 놓여져 있다. 나이트는 L자 형태로만 이동할 수 있으며 체스판 밖을 벗어날 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이와 같이 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이 때 체스판에서 행 위치를 표현할 때는 1 ~ 8로 표현, 열 위치를 표현할 때는 a ~ h로 표현한다. 입력 조건) 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과..