거북이처럼 천천히

1. 문제 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 입력 : 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력 : 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력 2. 생각 본 문제는 계차 수열을 이용하여 풀었다. 계차 수열 알고리즘을 이용한 이유는 다음과 같다. ex) N = 2 일 때는 2 개의 방을 이동해야 하며, ex) N = 8 일 때는 3 개의 방을 이동해야 한다. 위 몇 가지..

1. Selection sort public class SelectionSort { public static void main(String[] args) { int[] list = {29, 10, 14, 37, 13}; printList(list, "Before"); for(int i=list.length; i>1; i--) { int max = 0; for(int j=1; j

1. 문제 집합을 입력받아서 그 집합의 멱집합을 구하라. 멱집합(Powerset)이란? ▶ 주어진 집합의 모든 부분 집합들로 구성된 집합 2. 생각(Recursion Thinking) 고등학교때 배운 내용을 떠올리며, set A = {a, b, c, d, e, f}가 존재한다고 가정한다. Q) 집합 A의 부분 집합의 갯수는 몇 개인가? 집합의 원소들은 "부분 집합내에 존재하는가?"에 따라서 두 가지 경우의 수를 갖는다. 이를 바탕으로 모든 원소가 존재하지는 공집합 부터 모든 원소가 존재하는 경우까지 경우의 수를 생각하면 집합 A의 부분 집합의 갯수는 2^6 = 32개이다. 2.1. Powerset를 구현하는 알고리즘 아이디어 부분 집합의 갯수를 세는 것처럼 "특정 원소가 부분 집합에 존재하는가?"를 이용..

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..