[재귀] 계단 오르기

알고리즘/재귀 2014. 5. 15. 15:14

프로그램 명: upstair                                                                                                            제한시간: 1 초


최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 출력 하는 문제이다.

그림은 n 이 4 인 경우의 예 이다.

  • 1 - 2 - 3 - 4
  • 1 - 2 - 4
  • 1 - 3 - 4
  • 2 - 3 - 4
  • 2 - 4

입력

n 은 30 이하의 양의 정수이다.

출력

오를 수 있는 가짓 수를 출력한다.

입출력 예

입력

4

출력

5


[문제 풀이]

최대 2칸을 오를 수 있다는 것은, 한 번에 1칸 또는 2칸을 올라갈 수 있다는 뜻이다.

  • 1칸씩 올라가기 : 1 - 2 - 3 - 4
  • 1칸 - 1칸 - 2칸 : 1 - 2 - 4
  • 1칸 - 2칸 - 1칸 : 1 - 3 - 4
  • 2칸 - 1칸 - 1칸 : 2 - 3 - 4
  • 2칸씩 올라가기 : 2 - 4 
이렇게 입력받은 수(n)만큼 올라갈 수 있는 방법의 가짓 수를 출력하는 것이 목표이다.

[소스코드 설명]
stair()의 n은 목표 계단 높이, now는 현재 계단 높이를 말한다.
문제 풀이에서도 설명을 했듯이, 한 번에 1칸 또는 2칸을 올라갈 수 있다는 뜻이기 때문에 

1칸 올라가는 경우(stair(n, now + 1))와 2칸 올라가는 경우(stair(n, now + 2))를 모두 구해서
목표 계단 높이(n)과 같을 때까지 재귀 호출을 하였다.


저작자표시

'알고리즘 > 재귀' 카테고리의 다른 글

[재귀] 유클리드 호제법  (0) 2014.05.15
[재귀] x의 y 거듭제곱  (0) 2014.05.15
[Doc.] 재귀 (recursion)  (0) 2014.05.15
Posted by 밍쫑
,

[재귀] 유클리드 호제법

알고리즘/재귀 2014. 5. 15. 15:02

프로그램 명: euclid

제한시간: 1 초

두 수를 입력받아 최대공약수,최소 공배수를 구하는 프로그램을 작성하시오.

입력

두 양의 정수 a , b 가 입력으로 주어진다. (1 <= a , b <= 100 000)

출력

최대공약수,최소공배수를 한 줄에 출력한다. 두 수의 최대공약수 와 최소 공배수는 정수 범위(2^31 - 1)를 넘지 않는다.

입출력 예

입력

8 12

출력

4 24


[문제 풀이]


유클리드 호제법

유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

- Wiki, 위키백과 -


1. 입력으로 두 수 m,n(m>n)이 들어온다.

2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.

3. n이 m을 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.

4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3으로 돌아온다.


최소공배수(lcm) = (A*B) / gcd(A, B);




저작자표시

'알고리즘 > 재귀' 카테고리의 다른 글

[재귀] 계단 오르기  (0) 2014.05.15
[재귀] x의 y 거듭제곱  (0) 2014.05.15
[Doc.] 재귀 (recursion)  (0) 2014.05.15
Posted by 밍쫑
,

[재귀] x의 y 거듭제곱

알고리즘/재귀 2014. 5. 15. 14:56

프로그램 명: powerofx

제한시간: 1 초

x 의 y 거듭제곱을 구하는 문제이다.

2 10 을 입력 받으면 2 의 10 거듭제곱 1024 가 출력되어야 한다.

2^10 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2=1024

입력

두 정수 x , y 가 입력된다.

출력

x 의 y 거듭제곱된 결과값을 출력한다.

출력 결과는 정수 범위( 2^31 - 1)를 넘지 않는다.

입출력 예

입력

2 10

출력

1024


[소스코드 풀이]

지수(y)의 숫자 만큼 밑수(x)를 곱하기 때문에, y가 1이 될 때까지 재귀적으로 함수를 호출해서 밑수를 계속 곱해준다.



저작자표시

'알고리즘 > 재귀' 카테고리의 다른 글

[재귀] 계단 오르기  (0) 2014.05.15
[재귀] 유클리드 호제법  (0) 2014.05.15
[Doc.] 재귀 (recursion)  (0) 2014.05.15
Posted by 밍쫑
,

[Doc.] 재귀 (recursion)

알고리즘/재귀 2014. 5. 15. 14:40

재귀(Recursion)


수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다.

-  Wiki, 위키 백과 -



특징

  • 구현하려는 알고리즘 자체가 재귀적 특성을 갖는다면, 재귀 함수를 이용하면 쉽게 구현이 가능하다.
  • 프로그램 내의 반복문은 재귀호출로 바꿀 수 있으며, 그 반대로 재귀호출은 반복문으로 고쳐 쓸 수 있다.
  • 일반적으로 재귀 함수는 반복문을 이용한 함수로 변환이 가능


long factorial(int number)

{

...

factorial(number - 1);    // 함수 내부에서 자기 자신의 함수를 호출 (재귀함수)

...

}




n!

    • 수식 n! (n factorial)은 1 * 2 * 3 * ... * (n-2) * (n-1) * n 을 의미

계승 수식은 재귀적 특성을 갖음

    • 즉 n!을 구하기 위해서 (n-1)!을 먼저 구한다면 쉽게 n!을 구할 수 있음
    • 그러나 재귀적 호출이 종료되는 조건이 없다면 무한 호출에 의해 문제가 발생
if (n<=1)
n! = 1
else
n! = n * (n-1)!

↓

long factorial(int number)

{

if (number <= 1)

return 1;

else

return (number * fatorial (number -1));

}




피보나치 수

  • 다음 수가 앞의 두 수의 합이 되는 수열

0    1    1    2    3    5    8    13    21    ...

  • n번째 수를 Fn이라 하면, Fn은 다음과 같이 재귀적으로 표현

  • 피초나치 수를 발생시키는 프로그램을 작성한다면 재귀적 특성을 이용하여 쉽게 구현 가능.

int fibo(int n)

{

if (n==0)    return 0;

else if (n==1)    return 1;

else    return return fibo(n-1) + fibo(n-2);

}


main()

{

printf("%d", fibo(4));

}



  • 반복적 방법을 이용하여 구현

long fibo (int n)

{

int fn, fn1, fn2;

int i;


if (n <=1)    return n;

else {

fn2 = 0;

fn1 = 1;

for (i=2; i<=n; i++) {

fn = fn1 + fn2;

fn2 = fn1;

fn1 = fn;

}

return fn;

}

}


팩토리얼 문제나 피보나치 수열 문제 말고도 재귀를 대표하는 문제들을 많이 있습니다. (ex. 하노이의 탑)

저작자표시

'알고리즘 > 재귀' 카테고리의 다른 글

[재귀] 계단 오르기  (0) 2014.05.15
[재귀] 유클리드 호제법  (0) 2014.05.15
[재귀] x의 y 거듭제곱  (0) 2014.05.15
Posted by 밍쫑
,

멤고리즘 4회 2번. 규민이는 유성온천 부자 (재귀, BFS)

알고리즘/멤고리즘 2014. 4. 22. 23:20

규민이는 유성온천 부자


문제 

규민이는 멤버십에서 제일 가는 부자이다. 규민이네 정원 안에는 큰 온천가 있고, 그것을 막는 댐이 있었다. 

그런데 어느날 그 댐이 무너져내려 온천에 있는 유황온천수가 규민이네 정원을 모두 뒤덮으려한다. 

온천에 있는 유황온천수는 다음 1시간에 한 블럭으로 이동하며, 규민이네의 유황온천수는 무한하다. 

유황온천수는 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.

 

규민이네 가정부인 당신은 댐이 터진 순간 규민이네 정원 지도를 받았다. 

당신이 수행해야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 유황온천수가 더 이상 진행하지 못하도록 하는 것이다.

 

입력

첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고

다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 정원, 1은 정원에 있는 건물이다. (유황온천수는 건물을 뒤덮지 못한다고 가정한다.)

그리고 그 다음 줄에는 유황온천수가 터진 좌표 x, y가 주어지고,

다음 줄에는 댐이 지어지는 시간인 K가 주어진다.


출력

지어야 하는 댐의 숫자를 출력한다. 

만약, 정원이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "OH, MY GOD"을 출력한다. 

(좋은 의미로든, 나쁜 의미로든....)


예제 입력​

5
0 1 0 0 1
0 0 0 0 0
1 1 1 0 1
0 0 0 0 0
1 0 1 0 1
1 1
5

예제 출력

3


예제 입력​

5
0 0 1 0 0
0 0 0 0 0
1 1 1 0 0
0 0 1 1 0
0 0 0 0 0
5 2
3

예제 출력

2


입출력 설명

첫 번째 입력에서 (1,1) 위치에서 유황온천수가 터졌다면, 유황온천수는 시간마다 다음과 같이 진행된다.

(B는 건물의 위치)


0 B 4 5 B

1 2 3 4 5

B B B 5 B

9 8 7 6 7

B 9 B 7 B


그러므로 5 시간인 세군데를 막아 유황온천수이 진행하지 못하게 하는 것이 최선이다.

그러므로 출력이 3

출제자 : 임현수


(http://183.106.113.109/30stair/dam/dam.php?pname=dam)

저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 5회 1번, 멤고리즘 랭킹(정렬)  (0) 2014.05.10
멤고리즘 4회 3번. 운영자의 사탕 (DP)  (0) 2014.04.22
멤고리즘 4회 1번. 먹보 영훈이2 (칼로리 계산)  (0) 2014.04.22
멤고리즘 3회 3번. 술잔 나누기  (0) 2014.04.22
멤고리즘 3회 2번. 색종이(피자) 쪼개기  (0) 2014.04.22
Posted by 밍쫑
,

멤고리즘 3회 1번. 오목 (재귀)

알고리즘/멤고리즘 2014. 4. 22. 23:13

병훈이의 오목


문제


  

병훈이는 자신이 만든 오목 대전시스템에 자부심을 갖고 있다. 다음 단기에도 AI대회를 위해 후계자를 양성해야 한다.

바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, …, 19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, …, 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알이 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오.


단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

프로그램의 실행시간은 1초를 넘을 수 없다. 

 

입력

입력 파일은 19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않은 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.


출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다.

검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그중 가장 위에 있는 것)의 가로줄 번호와 세로줄 번호를 순서대로 출력한다.

 

예제 입력​

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0 
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력

1
3 2


출제자 : 임현수


[문제 풀이]

일반적으로 모두가 알고 있는 오목과 같은 룰이다.

오목은 어느 방향으로든 같은 색의 돌이 연속으로 5개가 놓이면 승리하는 게임이다.

가로로 놓일 경우 제일 왼쪽의 돌을, 대각선으로 놓일 경우 제일 위쪽의 돌을 기준으로 연속인지 확인한다.

다만, 주의할 점은 연속으로 6개가 놓이면 이긴것이 아니다. (아래에서는 이런 경우를 6돌이라 부르겠다.)


[소스코드 풀이]

x와 y의 좌표가 (0, 0) 이 아닌 (1, 1)부터 시작하게 하기 위해서 처음 map을 선언할 때 MAX+1을 해주고 0으로 초기화하였다.


- bool 타입의 chk 함수

x, y : 좌표

d : 방향

count : 개수

color : 선택한 색깔


일단, 처음에 맵의 크기를 넘어서는지를 확인하면서 6돌인지를 확인한다.

그리고 다음 돌이 현재 선택된 돌과 같은색인지를 체크하는 if문을 만들었다.


여기서 d의 경우 한 시부터 시계 방향으로 각 각 1~4의 방향이고 이 외의 것을 0으로 생각한다.



1~4 이외의 방향인 0의 경우 각 방향별로 반대 방향에 돌이 있는지를 확인하는 case 0: 을 작성합니다.


그리고 재귀로 chk함수를 계속 돌면서 count가 늘어나게 되는데

6목의 경우 이긴경우가 아니라고 했는데 count가 6일 경우에 true를 줬을까요?

그건 바로 count가 6까지 증가를 하고 chk()에 들어왔을 때에 5개의 돌이 연속인 것이 확인 되어 있기 때문이다.



주의! 

우리가 일반적으로 수학에서 배운 좌표계와 배열에서 사용하는 좌표계는 다릅니다!

밑에 표에서 보시는 바와 같이 오른쪽과 아래쪽으로 갈수록 크기가 커집니다.


          y   /   x

0

1 

2 

 0

0 

0 

1 

 1

1 

2 

1 

 2

3 

1 

0 





저작자표시

'알고리즘 > 멤고리즘' 카테고리의 다른 글

멤고리즘 3회 3번. 술잔 나누기  (0) 2014.04.22
멤고리즘 3회 2번. 색종이(피자) 쪼개기  (0) 2014.04.22
멤고리즘 2회 3번. 산삼 찾기(DP)  (0) 2014.04.22
멤고리즘 2회 2번. 이진회귀수  (0) 2014.04.22
멤고리즘 2회 1번. 거꾸로 말해요  (0) 2014.04.22
Posted by 밍쫑
,

티스토리툴바