거북이처럼 천천히

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. 문제 문제) 한 개의 자연수 N를 입력받은 뒤, N-by-N, 2 dimensional array를 생성하여 N개의 Queen를 배치한다. 단, 어떠한 퀸도 다른 퀸을 위협해서는 안되기 때문에 서로 퀸이 움직일 수 있는 경로상에 퀸이 있어서는 안된다. 퀸은 상하좌우, 대각선 4방향으로 움직일 수 있다. 2. 생각(Recursion Thinking) 2.1. 들어가기 전 N개의 말들은 다른 퀸의 경로 상에 있어서는 안되기 때문에 서로 다른 행에 존재할 수 밖에 없으며, N개의 말들을 배치시킬 수 있는 경우의 수는 총 N × N개라고 할 수 있다. 문제 해결 방법으로 첫 번째 말을 첫 번째 행에 놓고, 두 번째 말을 다음 행에 놓지만, 첫 번째 말의 경로상에 벗어난 위치에 놓는다. 그리고, 세 번째 말..

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. 문제 (미로 찾기) 파란색은 벽, 흰 색은 이동할 수 있는 통로를 의미 입구는 (0, 0), 출구는 (N-1, N-1)이며, 입구에서 시작해서 출구로 빠져나올 수 있도록 경로를 찾는다. 2. 생각(Recursion Thinking) 본 문제를 Recursion(재귀)를 이용하여 풀기 위해서 Recursion 하게 생각하였다. Recursion Thinking을 하면 현재 상황을 다음과 같이 나누어서 생각할 수 있다. If 현재 위치에서 출구까지 갈 수 있는 경로가 존재하려면 현재 위치가 출구 이거나 이웃한 셀들(= 현재 위치에서의 동서남북 셀)중에서 현재 위치를 지나지 않고, 출구까지 가는 경로가 있어야 한다. 2.1. Write the code by recursion. Recursion Think..

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 binary search? 이진 탐색(Binart search)은 정렬된 배열안에서 특정 값을 찾아내는 알고리즘이다. 배열의 원소들 중에서 중간값을 찾아서 1) 찾고자 하는 값보다 클 경우, 타켓 값은 중간 값을 기준으로 왼쪽에 위치하고, 2) 작을 경우, 타켓 값은 중간 값을 기준으로 오른쪽에 위치한 것을 알 수 있다. 동일한 방법으로 다시 중간의 값을 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 2. Example of binary search List = {1, 2, 3, 4, 5, 6, 7}, Target = {1} 시작점 인덱스는 0, 종점 인덱스는 6일 경우 중간 인덱스는 (시작점 인덱스 + 종점 인덱스) / 2 = 3이다. List[3]와 target ..

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(); } } ..