본문 바로가기

알고리즘(Algorithm)/재귀(recursion)

 (5)
(재귀)피보나치 수열(Fibonacci Sequence) 피보나치치 수열(Fibonacci Sequence)은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. ▲ (출처: https://blogs.glowscotland.org.uk/glowblogs/jypetrieuodep/2018/10/09/fibonacci-sequence-significant-coincidence/) 피보나치 수열을 구현하기 위한 방법이 몇가지 존재하는데 여기서는 재귀함수를 이용하도록 하겠다. 재귀함수(Recursive Function)란? 글을 읽어보면 재귀함수에는 재귀가 수렴해야 할 베이스케이스와 재귀케이스가 있어야 하는데 0번째 항부터 피보나치 수열을 시작할 경우 베이스케이스와 재귀케이스는 아래와 같다. 베이스케이스 : F0 = 0 and F1 ..
(재귀)N-Queen 문제 N-Queen 문제는 재귀문제중 매우 대중적인 문제인데 어떤 문제인지 파악부터 해보자. N-Queen 문제는 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 솔류션을 구하는 문제이다. 예를들어 8x8 체스판이 있다면 그림1. 처럼 Queen은 N=8개가 놓일 수 있는데 이게 맘대로 배치하면 안되고 특정 규칙에 따라 배치해야 한다. 특정 규칙이라는것은 그림2처럼 Queen 이 배치 될때 같은 행(row), 열(column)에 다른 Queen이 있으면 안되고 대각선(diagonal) 으로도 있으면 안된다는 것이다. [출처] https://helloacm.com/n-queen-problem-in-back-tracing-bit-logics/ 여기까지 왔으면 문제는 다 파악된것이다. 요..
(재귀)Blob(Labeling) 알고리즘 Blob Labeling 알고리즘(Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) )은 영상처리 분야에서 Labeling을 할 때 주로 쓰는 알고리즘인데, N*N 크기의 2차원이미지에서 인접한(상,하,좌,우,대각선모두포함) 화소에 모두 같은 번호(Label)을 붙이고 연결되지 않은 다른 성분(component)에는 다른 번호를 붙이는 알고리즘인데 주로 이미지 안에 연결되어 있는 객체가 몇개 인지 알아낼 때 사용하는 것이다. 문제는 픽셀 (x,y)가 포함된 blob의 크기를 알아내기 위해서 어떻게..
(재귀)미로(MAZE)찾기 미로(MAZE)찾기란 그림 1 처럼 출발지 (A)에서 도착지 (B)까지 가는 경로를 알고리즘적으로 푸는 방법이다. [출처] https://www.researchgate.net/figure/Ariadnes-Thread-Algorithm-The-thread-avoids-walking-in-cycles-The-Algorithm-produces_fig4_221437678 길찾기 알고리즘이 필요한 대표적인 사례는 네이게이션이나 마이크로마우스이다. [출처] https://www.hackster.io/jordanjameswong/micromouse-83dab7 마이크로마우스는 빠른시간 안에 미로의 정해진 구역에 도착해야 하는 문제를 풀기위해 길찾기 알고리즘이 성능이 매우 중요한데 미로를 탈출하려다가 막다른 길이 있을..
재귀함수(Recursive Function)란? 재귀함수에 관련된 글을 읽기전에 함수(function)가 무엇인지 잘 모르면 [JAVA] 함수(Function)란? 을 먼저 읽어보기 바란다. (물론 재귀함수를 읽으려고 들어온사람이 함수(funtion)이 무엇인지 모르는 분은 없을거라 생각한다) 재귀(순환)함수란? 바로 자기 자신을 호출하는 함수를 말한다. 예를들어 recursion() 이란 함수가 있다면 recursion() 함수 안에 또 recursion()을 호출(자기자신 호출)하는 형태를 말한다. 1 2 3 4 5 6 7 void recursion() { .... recursion(); ... } 그런데 만약 재귀함수 안에 자기자신을 호출하게 되면 어떤 일이 벌어질까? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 publ..

티스토리툴바