MFC 미로 게임

Maze Generator

매번 만들어야지 생각만 하다가, 드디어 해봤다.
오랜만에 MFC를 잡아서인지 몇 시간 걸렸다.
이전에 선배 도와주면서 만들어본 "DFS와 BFS를 이용한 최단경로" 를 적용해서 [Find Path] 버튼을 추가할 예정.

역시 알고리즘은 이렇게 써먹으면 기분 좋음

한가지 재미있는 사실이라면, srand(time(NULL)) 같이 time함수를 잘 쓰지 않는 편이라 (온라인 저지 탓인ㄱ..) rand함수를 잘 사용하지 않았다.
그럼 어떻게 하느냐
srand((int)&val)); 과 같이 특정 변수의 주소를 정수로 변환해버린다.
그런데 이게 지역변수라 매번 할당을 다르게 할 줄 알았더니, Generate 버튼을 아무리 눌러도 항상 같은 미로를 만들었다. 주소값이 같은건가..!!
덕분에 좋은 난수 생성 알고리즘을 알았는데, 메르센 트위스터(MT) 고안자가 만든 WELL512 를 사용해봤다. 자세한 내용은 구글링 + 위키 참조

---

10-06 15:48 update. v1.2

- 셀 크기 설정 추가 (가로X세로에 대해 자동 계산)

- 정답 출력(Find Path) 추가

- 미로만 다시 그리기(Reset) 추가

여담:
- 셀 크기가 너무 작거나 크면 미로를 만들지 않도록 했는 데 먹히질 않는다 (!!)
- 셀 크기가 너무 작으면 튕긴다. 주의..
- BFS 과정 출력 버튼도 있었는데 너무 더러워서 제거 (....)

---

10-06 18:55 update. v1.3

- 랜덤하지 못하게 편향된 경로 결과 수정
- 셀 크기를 변경하고 Find Path를 누르면 잘못되던 버그 수정

---

10-06 20:37 update. v1.4.0

- 버튼 활성화/비활성화 추가
- 최소 셀 크기 제한
- 버튼 UI를 왼쪽으로 이동
- 숫자 입력 후 엔터 누르면 자동 Generate 반복문이 맞물려서 런타임 에러가 남. 일단 삭제
- 창 크기 및 출력 크기 변경 가능

---

10-10 20:02 update. v1.4.1

- 인쇄 기능 추가 (세로 모드로 출력)
- 왼쪽 상단에 미로의 크기 정보 표시
- 미로 난이도 상향 (...?)
- 길 찾기 결과 출력에 옵션 추가. (탈출로 / BFS 결과)
- 시작점과 출발점을 변경함 (윗쪽 중앙에서 아랫쪽 중앙으로 탈출)
- 그 외 기타 예외 처리.

Attached File
> Maze_Generator.v1.4.1.exe

1695 - 팰린드롬 만들기

처음에 그리디적으로 접근했는데, 이게 발상의 시초였다.

팰린드롬을 만들 때, 좌우 한쪽을 기준으로 잡고, 양쪽이 다르면 반대쪽에 "그 문자"를 추가한다고 생각해보았다. 예를 들면,

abaacd 라면 가장 왼쪽 a와 잡고 가장 오른쪽은 d를 비교한다. 이 때 문자가 서로 다르므로 오른쪽에 a를 추가하여 abaacda 를 만든다고 생각한다. a는 이제 추가했으므로 b를 잡고 다시 d를 비교한다. 다르므로 다시 추가하면 abaacdba 가 될 것이다.

이 행동을 반복하면

abaacdaba

abaacdaaba

abaacdcaaba

abaacdcaaba

하지만 위 방법은 너무 그리디적이여서 만약 번갈아서 추가해야하는 상황이 생기면 틀리게 된다.

생각을 살짝 바꾼다면, L번째와 R번째를 비교하는 함수를 p(L, R) 이라 하자.
p(L, R) 에서 나올 수 있는 경우는 3가지이다.

1. L과 R이 같은 경우

2-1. L과 R이 다를 때, p(L+1, R)에서 답이 나오는 경우 + 1 (여기서 1은 한쪽이 다르므로 문자를 추가한 비용)

2-2. L과 R이 다를 때, p(L, R-1)에서 답이 나오는 경우 + 1

우리는 이제 그리디적인 2-1 과 2-2 에 대해 유연하게 대처할 수 있게 되었다.

중복되는 연산이 굉장히 많으므로 [L][R]과 같이 저장해서 중복연산을 피하면 되겠다.

2004 - 조합

nCm 에 대해서 오른쪽부터 0의 개수를 출력하는 문제이다.

nCm = (n! / m!) / (n-m)! 이다. 여기서 m≤n≤2,000,000,000 인데 각각 팩토리얼을 계산한다면 절대 구할 수 없을 것이다. (오버플로우나 시간복잡도 등..)

이 문제 이전에 일반적인 nCm 을 구하는 문제부터 짚어보자.
오버플로우를 피해서 nCm을 구하는 것이라면 각 팩토리얼을 모두 계산 후에 나누는 게 아니라 분자(2 * 3 *... * n-m+1) 와 분모(2 * ... * m) 을 구성하는 각 숫자를 하나씩 계산하는건데

12C5 를 예로 들자면 12! 을 계산 후에 5! 7! 으로 나누는게 아니라 아래와 같이 진행한다.
12C5는 아래와 같이 나타낼 수 있다.
( 12 * 11 * 10 * 9 * 8 ) / ( 5 * 4 * 3 * 2 * 1 )
위 식은 다시말해 (12/5) * (11/4) * (10/3) * (9/2) * (8/3) 을 따로 한 것과 같은 결과이다.

그럼 0의 개수는 어떻게 구할까?
0의 개수를 구하는 문제는 보통 숫자를 소인수분해해서 2의 지수갯수와 5의 지수갯수 중 더 작은 만큼이 0의 갯수를 구성하는 게 일반적이다.
예를들면 120 = 2³ * 3¹ * 5¹ = 2¹ * 3¹ * 10¹ 이라서 가능하다.

서론이 길었는데, 다시 본문으로 돌아와서.
이 문제에서는 nCm을 구하는게 아니라 nCm의 0의 개수를 구하는 문제이니, [분자에서 나온 2^a * 5^b]와 [분모에서 나온 2^c * 5^d] 를 구해서 a-c 와 b-d 중에 더 작은 값이 곧 nCm의 0의 개수가 된다.

N=9 으로 생각해보자.
N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 이 될 것이다.
여기서 2의 배수만 추려낸다면 2의 지수를 구할 수 있을 것이다.
2의 배수 = N/2 개만큼 있다. = 4개 ( 2, 4, 6, 8. )   --- 여기서 2의 배수만 구했는데, 그럼 2, 4, 6 이 각각 2¹ 을 가지고 있다는 뜻이된다.
4의 배수 = N/4 개만큼 있다. = 2개 ( 4, 8. )       ---- 2¹에 대해서 앞에서 더해줬기 때문에 지금 센 것이 중복일 지 몰라도 잘 생각해보면 "중복을 피했다"

마찬가지로 8의 배수, 16의 배수... 에 대해서 반복하면 된다.
5의 배수도 위와 같이 세면 된다.

수학적인 사고가 부족해서 위 개념을 이해하는 데 한참 걸렸다. 답답함을 안고 알려준 친구에게 고마움을 표한다.

1701 - 소녀시대 공식팬클럽 회장

2번 이상 나타나는 부분문자열을 찾고 그 최대 길이를 출력하는 문제이다.

Suffix Array 를 사용했는데,
길이가 n인 문자열 s에 대해 s[i...n]의 suffix (n개)를 나열한다. 예를들어, abbac 라면

abbac
bbac
bac
ac
c

와 같이 나오는데, 이걸 사전순으로 정렬하여 다음과 같이 만든다.

abbac
ac
bac
bbac
c

위 suffix array에 대해 서로 문자열을 비교한다.
i번 문자열과 i+1번 문자열에 대해 [0...j]를 비교. [i][j] 와 [i+1][j] 가 다를 때까지의 길이가 부분문자열의 길이가 된다.
이는 "모든 부분문자열은 모든 접미사의 접두사들"이기 때문이다.

Suffix Array는 간단한 구현으로 많은 문제에 영감을 줄 수 있지만, 위와 같이 N개에 대해 저장하거나 N²의 시간복잡도를 가지는 경우가 있어서 길이가 1만 정도만 넘어도 사용하기 힘들어진다고 한다.

길이가 10만을 넘는 문자열에 대해서 부분문자열은 어떻게 찾는지 고심해봐야겠다.

7579 - 앱

M 메모리를 확보하기 위해 활성화 중인 앱을 종료시켜야 하는데
다시 실행하는 데 드는 비용 C 를 최소화하는 문제이다.

생각을 바꿔서, 비용 C로 얼마만큼의 메모리를 확보할 수 있는가로 풀면 된다.

1244 - 스위치 켜고 끄기

남학생의 경우 주어진 수(k라 하자)의 배수마다 NOT 연산을 한다.
이부분은 인덱스 idx를 k-1부터 시작해서 idx += k 씩 증가시키면서 NOT을 하면 된다.

여학생의 경우 주어신 수 k를 기준으로 좌우대칭 구간만큼 NOT 연산을 한다.
left = k, right = k 로 설정하고 left--, right++ 을 하면서 배열의 [left]원소와 [right]원소가 다를 때 까지 NOT 연산을 반복하면 된다.

최대 학생 수=100, 스위치=100 이라 걱정없었지만, 더 큰 입력에 대해선 어떻게 해야할 지 모르겠다. 더 효율적인 좋은 방법이 있으리라 생각한다.

4493 - 가위 바위 보?

가위, 바위, 보는 서로를 향하는 상성을 가진다.
이기면 +2점, 비기면 +1점, 지면 0점이라고 했을 때
X(행)가 Y(열)과 붙었을 때 얻을 수 있는 점수는 아래와 같이 표현할 수 있다

	R	P	S
R	1	0	2
P	2	1	0
S	0	2	1

입력된 char형에 따라 R => 0, P => 1, S => 2 으로 변환하고, 테이블을 참조하여 플레이어 기준으로 점수를 더하게 했다.

1912 - 부분합

음수는 더하면 손해다. 하지만 음수의 포함한 구간이 더 큰 수를 나타낼 수도 있다.

[ 6, -4, 10, -20, 5, 4 ] 같은 경우에는 [ 6, -4, 10 ]= 12 로 최대이다.

처음부터 수를 누적하면서, 합이 음수가 되면 합을 초기화한다. 그리고 합은 더할때마다 가장 최대값을 따로 저장해둔다.
그럼 합이 음수가 되어 합이 초기화 되는 순간 "하나의 구간"이 구분되고, 따로 저장된 최대값은 "그 구간 내에서 나올 수 있는 최대 합"이 된다.

2504 - 괄호의 값

스택인건 알겠는데 내가 스택 처리를 너무 복잡하게 한 것 같다.

스택 2개를 사용했는데, 하나는 누적값을 넣고, 나머지 하나는 가장 최근에 열린 괄호를 쌓아올렸다.
그리고 닫는 괄호가 나올때마다 이전의 누적값을 갱신했다.
"([])" 를 예로 들면 아래와 같다.

(
x2

( [
x2 x3

(
x2 +3


+6

중간에 짝이 다르면 곧바로 0을 리턴하도록 했다.

소스

6500 - 랜덤 숫자 만들기

숫자를 sprintf 등을 이용해서 0이 채워진 8자리 숫자의 형태로 (문자열로) 가공한다.

즉, 8580 은 00008580 과 같이 만든다.

문제의 조건에 따라 다음 숫자의 형태는 둘 중 하나로 결정된다.

숫자가 9999보다 크다면 00####00 을 추출하고, 아니라면 0000#### 를 추출한다. (여기서는 n=4 이기 때문에)

atoi를 이용하여 위에서 추출한 문자열이 곧 다음 숫자가 된다.

위 행동을 반복하면서 사이클이 (=같은 숫자가 다시) 나올 때 행동을 중지하고 반복 횟수를 출력한다.

2075 - N번째 큰수

N² 크기의 테이블이 주어지면 그 중에서 N번째 큰 수를 구하는 것인데
사실 테이블이라는 형태는 의미 없고 크기가 N² 인 수열에서 N번째 큰 수를 찾으면 된다.

필자는 입력과 동시에 처리하였다. min-heap의 형태를 이용하였는데,
N번째 큰 수를 찾기 위해서는 N개만 누적하고 있으면 되기 때문이다.

12 7 9 15 5 까지 입력된 상황이라면 min-heap은 5 7 9 12 15 의 형태를 이룰 것이다.
다음으로 13 이 들어오면 min-heap에서 최소값을 pop 하고 13 을 push 하면 된다.
그럼 13 이 push된 상황은 7 9 12 13 15 와 같을것이다.

이렇게 N개의 크기를 끝까지 유지하고 입력이 종료 되었을 때 min-heap의 가장 top를 출력하면 그게 N번째 큰 수가 된다.

안드로이드에서 Jsoup을 사용하기 위한 세팅

Jsoup 이라는 훌륭한 클래스를 사용했다.

Document document = Jsoup.connect("http://www.blogger.com/").get();
Element el = document.select("#selectID");

select라는 메소드는 강력한 기능을 가진다.
마치 자바스크립트 콘솔에서 선택자를 그대로 옮긴 느낌인데 자세한 사용법은 공식 사이트 API를 참고하면 된다.

Jsoup을 사용하기 위해서는 libs폴더에 jsoup.1.x.x.jar 를 옮긴 다음
Project - Properities - Java build path 에서 Library탭에 들어가고 [Add Jars..] 를 클릭해서 불러오면 된다.

마지막으로 인터넷 접근 권한을 허용하기 위해 안드로이드 메니페스트에서 <uses-permission android:name="android.permission.INTERNET" /> 를 추가한다.

이제 Jsoup을 사용하기 위한 세팅이 끝났다.

1149 - RGB거리

<9465 - 스티커>의 솔루션을 그대로 적용해서 풀면 된다.

i번째에서 R을 고르면 i+1번째에서는 G, B밖에 못 고르고 둘 중 (선택했을 때 더욱) 최소값인 것을 저장하면 된다.

스티커에서 재귀로 짰다가 시간초과에 후덜거렸기때문에 O(N)만에 끝나게 안정적으로 짰다!

9465 - 스티커

한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.
그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다.

A B C D
E F G H

위와 같이 있을 경우, A 를 선택한다면 C D F G H 중에 선택하게 된다. (하지만 대각선을 선택하는게 가장 좋기 때문에 F 가 선택될 것이다.)
여기서 F 를 선택했다고 생각하면 남은건 C D H 인데, C D 중 더 큰 것을 선택한 것이 F 를 선택했을 때의 최선의 선택이다. X번의 최선의 선택을 F(X) 라 하자.
이해하기 쉽게 위아래로 나누자면 윗줄 중에서 최선의 선택을 F(X), 아랫줄은 G(X) 라고 했을 때,
F(X) 는 F.x(윗줄 x번째 스티커의 값) 과 max( G(X+1), G(X+2) )을 더한 값이 최선의 선택일 것이다.

50 10 100 20 40
30 50  70 10 60

은 아래와 같이 진행된다.

(Base case)
0 0 0 0 40
0 0 0 0 60

0 0 0 20+60=80 40
0 0 0 10+40=50 60

(남은 대각선 방향에서 가장 최선의 값을 누적. 같은 줄은 이미 이전에 확인을 함!)
0 0 100+max(50,60) 80 40
0 0 70+max(80,40) 50 60

(사실 여기서부터는 대각선 방향에서 가장 최선을 볼 필요가 없다. 왜냐면 대각선 방향이 이미 최선이 되었기 때문)
0 10+150 160 80 40
0 50+160 150 50 60

50+210 160 160 80 40
30+160 210 150 50 60

이제 F(0) 과 G(0) 중에서 무엇이 더 큰가만 확인하면 된다.

1212 - 8진수 2진수

처음에 파이썬으로 풀었는데 재채점되면서 오답으로 바뀌었다.

파이썬 코드는 다음과 같다.

print bin(int("0%d"%input(),8))[2:]




그래서 그냥 C++로 바꿨다. 8진수는 3자리씩 끊어서 2진수로 변환이 가능하다.

314 → 011 001 100 → 11001100

근데 이거도 귀찮아서 제일 확실한 방법을 썼다. 방법은 아래 코드 참고

숫자에서 앞의 0을 제거하는건 라이브러리 함수를 찾아볼까하다가 그냥 플래그 하나 놓고 처리했다.

9575 - 운 좋은 수

모듈화를 잘 하니까 쉬워졌다.

처음에 배열의 갯수가 바뀌는 줄 알고 재귀적으로 생각했다가
배열이 항상 a, b, c 로 고정된거 깨닫고 3중 for문으로 끝냈다.

bool형 배열 선언해서 캐싱하면서 중복되는 수를 제외시켰고
lucky(n) 이란 함수로 정수 n에 5나 8이 포함되는지 확인했다.

5나 8이 확인되는지는 sprintf로 스트링을 만든 다음 인덱스 하나씩 확인했음.

중복 제외시킬 때 숫자 최대 합이 90000 인거랑 매번 테스트케이스마다 초기화를 까먹어서 오답을 받았다.
초기화랑 배열 범위는 항상 조심!

2312 - 수 복원하기

소수 찾기처럼 에라토스테네스의 체를 이용하면 굳이 n까지 확인을 안 해도 될거라 생각했는데, 아닌가보다.

매개변수를 2부터 N까지 증가시키면서 나누어 떨어진다면 N을 2로 나눌 수 있는 만큼 나누고 몇번 나눴는가를 출력했다.

사실 매개변수를 k 라고 한다면 logkN 으로 알 수 있지 않을까 했는데 그렇지도 않았다. 나누어떨어진다는 이유로 다른 소인수를 무시하고 억지로 나누어버리기 때문. (예를들면 k=2 인 상황에서 n=10)

1005 - ACM Craft

DFS로 탐색을 했다. 그냥 DFS를 했다고 해야하나? 역전 앞

노드와 간선의 정보가 주어지고 노드 번호가 주어지면 "그 노드까지 이어진 최장 경로"를 찾는 문제로 생각할 수 있는 데, 그림의 간선 방향을 반대로 바꾸면 "시작노드가 주어지고 시작노드로부터 가장 긴 경로"를 찾는 문제가 될 거라고 생각했다.

하지만 위 알고리즘은 시간초과를 벗어날 수 없게되었다...

친구의 도움을 받아 백트래킹을 이용하면 풀 수 있다는 것을 알게 되었다.
한 노드를 잡고 그 노드까지 가는 최대 경로를 누적하면 목적지까지 가는 노드를 알 수 있다!

백트래킹이 뭔지 모르는 친구에게 백트래킹을 배웠다. 밤낮으로 더 열심히 문제를 풀어야겠다.

2133 - 타일 채우기

원제목 : Tri Tiling

여기(algorithmist.com)가 더 설명을 잘 해서 내용을 대체한다.

7575 - 바이러스

라빈-카프 알고리즘을 사용했다. 사실 KMP 알고리즘이 더 적합할 거 같지만..

vector< vector<int> > 형을 사용해서 두 문자열 s와 t에 나오는 패턴들의 교집합 저장하였다.
정확히는 [패턴 집합] 과 [문자열]에 대한 교집합을 새로운 [패턴 집합]으로 교체하면서 다음 문자열과 이것을 반복했다.

예를 들면, 문자열 [1 3 2 5 4] 와 [2 5 3 1] 에서 뽑아낼 수 있는 패턴 집합은 "[1 3], [2 5]" 이다. 이 집합을 초기 집합으로 설정하고 "[1 3], [2, 5]" 와 [6 5 1 3 5] 의 교집합을 구한다.
그럼 여기서 일치하지 않는 패턴들은 소거된다.

위 생각으로만 제출했을 때 메모리 초과를 받았다. "[1 2], [1 2], [1 2], [1 2]..." 와 같이 계속 들어갔기 때문인데, map을 사용해서 중복되는 패턴의 삽입을 방지하니 정답을 받았다.
여기서 신기한게 map의 key값 형태를 vector<int>로 하고 체크할 때 인스턴스만 넘겼는데 배열의 각 원소들을 모두 비교한건지 어쩐거지 겹치는 벡터가 없었다. STL의 위엄

9461 - 파도반 수열

작년 ACM 본선 문제.

단순한 규칙성 문제라 정답은 아래 정의 하나로 끝나지만 몇가지만 조심하면 된다.

파도반 수열의 N번째 항은 P(N) = P(N-2) + P(N-3); 과 같이 나타낼 수 있다.

하지만 재귀식이므로 DP를 이용해서 꼭! 시간복잡도를 줄여야한다.

2417 - 정수 제곱근

n이 주어지면 q² ≥ n 이 되는 q를 찾으라는데, 식을 뒤집으면 q ≥ √n 이므로 경계만 잘 파악하면 쉽게 q를 알아낼 수 있다.

이 문제에서 꽤 여러번 틀렸는데, 입력되는 정수 N 의 범위가 0 ≤ N ≤ 2⁶³ 이라길래 당연히 unsigned long long 을 썼다. 그런데도 계속 틀린 답이 나와서 도대체 뭐가 문제인지 몰랐는데, 오답은 "0 ≤ N" 을 간과해서 나온 것이였다.

unsigned long long 은 0 을 포함하지 않으므로 overflow가 나는걸 주의하자.

그리고 최소/최대 케이스 테스트할 때, 대충 하지 말아야겠다.

1753 - 최단경로

정점의 갯수 V와 간선의 갯수 E가 주어지고, E개만큼의 간선 정보가 입력된다.
정점은 1....V 만큼 있을 때 시작점 V_s 로부터 모든 간선으로의 최단 경로를 출력하는 문제이다.


먼저, 필자는 벨만-포드 알고리즘을 사용했다. 벨만-포드는 O(VE)의 시간복잡도를 가져서 이 문제에서는 적합하기 않다. ( 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000 이기 때문 )

E개의 노드를 차례로 살피면서 각 노드의 최단경로 정보를 갱신한다. 정확도를 위해 (누락되는 경로가 없도록) 각 정점의 갯수 V만큼 갱신을 반복한다. 그래서 O(VE)이다.

당연히 시간초과를 받았지만, 확률상으로 누락되는 경로가 있을까 싶어서 모험을 해봤다.
V번 반복하지 않고 log(V)번 반복해서 시간복잡도 O(E logV)로 도전해봤는데 정답을 맞았다. 운이 좋았다. 그리고 난 쾌재를 불렀다

7806 - GCD!

n! 와 k 의 최대공약수를 구하는 문제이다.

n!과 k를 각각 소인수분해해서 각 겹치는 인수들 중에 지수가 더 작은 것끼리 곱하면 그것이  n!과 k의 공약수이다.

예를 들어, (n=4)!, k=18 이라면 4! 을 소인수분해하면 2³x3 이고 18 은 2x3² 이다. 겹치는 인수는 2, 3 이고 지수가 더 작은 것끼리 곱하면  2¹x3¹ = 6 이다.

매개변수 p를 두고 p=2 부터 $p^2 \le k$ 까지 늘려가면서 아래 작업을 수행한다.

n에서 p^a 를 알아내고, k에서 p^b 를 알아내서 result 에 p^min(a,b)를 중첩하여 곱셈했다.

5724 - 파인만

정답은 "N까지의 {N_k²}들의 합" 이다.

N=1 일 때 칸은 1개이다.
N=2 일 때는 1개짜리 칸이 2X2. 총 4개만큼 늘어나고, 거기에 2X2짜리 네모가 1개 있다.
N=3 일 때는 1개짜리 칸이 3X3개 + 2X2짜리가 4개 + 3X3짜리가 1개....

더이상 자세한 설명은 생략한다.

1003 - 피보나치 함수

보통 피보나치는 문제의 설명에 적혀있듯이 재귀적으로 작성할 수 있다.

return fibonacci(n‐1) + fibonacci(n‐2); 와 같이 말이다.

하지만 함수의 호출 스택의 한계를 무시한다고 생각해도 일단 중복되는 호출이 굉장히 많다.
f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = f(1) + f(0) + f(0) 과 같이 f(3)만 하더라고 f(1)을 여러번 부른다. 이러면 시간복잡도는 지수함수가 되는데, 메모리는 둘째치고 시간이 굉장히 오래걸린다.

즉, 이 문제는 재귀를 사용하지 않고 비재귀적(iterative)하게 작성할 수 있는가가 핵심이다.

원리만 잘 파악하면 피보나치는 변수 2개로 해결할 수 있다.

먼저 a = 0, b = 1 로 시작한다. 그리고 다음번의 b 가 a + b 가 되고, 다음번의 a 는 바뀌기 전의 b 가 된다. 이 행동을 반복하면, b는 N번째 피보나치 수가 된다.

예를 들면, 순서대로 a b 라고 할 때 1~5번의 반복이 일어날 동안 변수의 상황은 아래와 같다.

0 1
1 1
2 1
3 2
5 3

예시를 잘 보면 문제를 해결할 수 있을 것이다.

1159 - 농구 경기

자료구조 map을 그대로 사용하면 된다.

단순한 map의 사용 문제

소스 보기

1012 - 유기농 배추

DFS나 BFS와 같은 전탐색으로 문제를 해결할 수 있다.
필자는 DFS를 사용했는데, int dirt[4]={-1,0,1,0}; 과 같이 선언하고

08	int DFS(int y, int x, int H /*최대 높이*/, int W /*최대 너비*/)

09

{

10	if( /* Base Case; 기저 케이스 */ ) return 0;

15	for(int i=0; i < 4; ++i)

16	DFS( y+dirt[(i+3)%4], x+dirt[i], H, W );

17

return 1;

18

}


위와 같이 [상(-1,0), 우(0,-1), 하(+1,0), 좌(0,+1) ]의 조합을 배열 하나로 사용했다.

여기서 DFS가 return 1; 을 했다. 이건 한 덩어리(구간)의 출발점만 리턴될 것이다.
왜냐하면 기저 케이스에서 "방문한 노드"는 return 0; 으로  걸러질 것이기 때문이다.