거북이처럼 천천히

1. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 생각 본 문제는 길이가 M인 수열을 구해야 하기 때문에 state-space tree를 이용하여 해가 될 수 있는 모든 노드에 직접 방문하여 찾아야 하기 때문에 1) Depth-first search, 2) Back..

1. 문제 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 문제 출처) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 생각 본 문제를 푸는 알고리즘은 다양하지만, Recursion의 연습을 위해 Recursion으로 풀도록 하겠다. 2.1. Recursion Thinking Recursion을 이용한 알고리즘은 다음과 같다. 합계(value) 값을 0으로 초기화한 뒤, 1부터 3까지 각각 더한다. if) 합계(value) 값이 입력 받은 값(num)보다 크면 "해당 구성 요소들의..

1. 문제 0(Background pixel)과 1(Image pixel)로 구성된 Binary 이미지에서 서로 인접한 Image pixel의 집합을 Blob라 한다. 상하좌우 + 이웃한 대각선까지 인접한 것으로 간주 문제) Binary 이미지에서 Blob의 집합과 그의 크기를 구하기 2. 생각(Recursion Thinking) 본 문제는 하나의 Image pixel를 기준으로 이웃한 Image pixel의 갯수를 반복적으로(?) 세야하기 때문에 재귀 함수(Recursion)를 이용하였다. Recursion Think를 이용하여 단계별로 나누면 다음과 같이 나눌 수 있다. 2.1. 첫 번째 Recursion Base Case) Binary image에서 [0, 0]부터 시작해서 [N-1, N-1]까지 ..

1. Basic structure of recursion recursion의 기본적인 구조는 Base area, Recursion area로 나뉘며, 각각의 area는 다음과 같은 특성을 갖는다. Base area : Recursion 내에 적어도 하나의 base area가 존재해야 하며, 이 영역은 infinite loop를 순회하는 recursion을 종료시키는 역활을 한다. Recursion area : 모든 Case는 base case에 수렴하도록 설계해야 한다. 이번에는 Recursion을 더 잘 이해하고, 일반적인 반복문과의 차이점을 확인하기 위해서 1) 일반적인 반복문으로 구현 했을 때와 2) Recursion으로 구현했을 때을 비교해보도록 하겠다. 2. Sequential search 2...

1. What is Recursion? Recursion은 자기 자신을 호출하는 메서드를 의미하며, Recursion을 번역하면 "순환, 재귀 메서드" 라 한다. Java를 통해 Recursion을 구현해보자. methodForTest 메서드를 main 메서드에서 호출했으며, methodForTest 메서드내에서 다시 한번 자기 자신을 호출하였다. 아래 코드와 같이 실행하면 어떤 결과가 발생하는가? public class Test { public static void main(String[] args) { methodForTest(); } private static void methodForTest() { System.out.println("Say Hello!"); methodForTest(); } } ..