재귀함수

백준 1780 풀이 (종이의 개수, 재귀, 파이썬)

이번에는 이전보다 더 분할하는 문제를 풀어본다. 문제는 그냥 머랄까 이전에는 반을 나누었다면 이번에는 3등분하는 문제였다. 사실 코드적인 부분이 많이 달라지지 않았다. 저번에는 반으로 나누는 과정을 조금 무식하게 풀었는데, 이번에는 3등분을 해야하다보니 조금더 깔끔하게 처리하려고 노력했다. 막상 비교하려고 놓고 보니 별로 큰 차이가 없어보이네;;ㅎㅎ 여튼 이러한 방식으로 풀면 되는거라 이전 문제와 크게 다른점이 없었다. 처음 제출했을때 틀렸다고 해서 당황했는데 알고보니 0개수를 1개수랑 바꿔놓고 풀었었다. 정신 차리고 풀어야 겠다. import sys n = int(sys.stdin.readline()) nr1 = 0 n0 = 0 n1 = 0 def check(p): global nr1 global n0..

백준 9184 풀이 (재귀함수, 메모제이션, 다이나믹 프로그래밍)

우선 이 문제를 보고 당혹감을 감출 수 없었다. 식을 그냥 줬다. 그냥 풀어보라고 줘버린것이다. 이런건 유저가 만들어야하는데 주는 이유가 있을것이다. 처음에는 규칙을 찾아야하나?하고 고민을 했다. 솔직히 저렇게 복잡하게 얽히고 섥혀있는데 규칙을 어떻게 찾나 고민을 했다. 그러다가 9184를 구글링 했더니 메모제이션이라는 기법이나 DP가 같이 쓰여있는 것을 확인했다. 그래서 메모제이션을 찾아보았다. 메모제이션이란 일반적인 재귀에서 이미 같은 인자를 연산했더라도 또 연산하는 경우가 존재한다. 그래서 이미 연산한 결과는 저장해두고, 만약 같은 연산이 필요할때 꺼내어 쓰자는 의도이다. ssminji.github.io/2020/02/05/the-cake-thief/ [알고리즘] Memoization(메모이제이션)..

백준 15650 풀이 (재귀함수)

저번에 풀었던 15649문제에서 코드를 살짝만 수정하면 쉽게 구할수 있다. 조건은 뒤에 수열이 반드시 오름차순이어야하며 중복을 포함하지 않는다. 코드의 중복이 살짝 있지만 애교로 넘어가자 n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map[i],end=' ') print() return for i in range(n): if len(tlist) == 0: tlist.append(i) back(tlist,n,m-1) tlist.pop() else: if i > tlist[-1]: tlist.append(i) back(tlist,n,m-1) tli..

백준 15649 풀이 (재귀함수, 백트래킹)

음 백트래킹이 먼지 몰랐다. 그래서 여기저기 기웃거려본 결과 트리를 만들때 불필요한걸 쳐내면서 트리를 만드는거 같다. 물론 이 문제에 백트래킹을 어떻게 적용해야하는지 전혀 이해못했다. 그냥 재귀함수로 적용해서 풀어보자! 라는 마인드로 풀었는데 어찌저찌 풀리긴 풀렸다. 순서는 다음과 같다. 1. 빈 리스트, n, m을 인자로 넣어준다. 2. for 을 이용하여 사용되지 않은 숫자를 리스트에 추가하며 재귀함수를 실행시킨다. 3. m을 하나씩 줄여서 m이 0이 되면 리스트에 저장된 값을 출력해준다. n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map..

백준 11729 풀이 (하노이탑)

오우 아주 쒯같지만 좋다고 느낀 문제였다. 계속 재귀에 대해서 벽을 느끼고 있었는데 재귀의 동작방식을 너무나 잘 공부할 수 있었다. 하노이탑 알고리즘을 보다 보니 너무 좋은 글을 써주신 블로거분이 있어서 참고하면 좋을거 같다. (shoark7.github.io/programming/algorithm/tower-of-hanoi) 규칙은 쉬우나 문제는 법칙을 찾는게 어렵다는 것이다. 그래서 3을 기준으로 어떻게 옮기는지 보면 몇가지 방식으로 규칙을 찾을수 있다. 완벽히 이해한게 아니라 설명이 어려운데..... 1. 3을 A->C로 옮기는 경우 2. 1,2를 A->B로 옮겨야한다.(2를 A->B로 옮기는 재귀함수) 3. 3을 A->C로 옮겨야한다.(1개만 옮겨도 되기 때문에 재귀가 필요없다.) 4. 1,2를 ..

백준 10870 풀이 (재귀함수, 피보나치)

재귀함수는 아직 어렵다. 어떤 구조를 짜야하는지 계속 고민하게 된다. 그래도 얼추 대강 짜서 통과는 할 수 있었다. 솔직히 대강 짠거라 안좋은 코드인줄 알았으나 속도가 빠르다는 장점이 있었다. n = int(input()) def pibo(a,b,num): c = a+b if num == 0: return 0 elif num

백준 10872 풀이 (재귀함수, 팩토리얼)

예전에 c언어를 공부할때 재귀함수를 간단히 다뤄본적이 있다. 솔직히 구조가 한눈에 들어오지 않아서 꽤 맘에 안들었고 그 이후로는 자발적으로 재귀함수를 써본적이 없다. 그래도 이번에 재귀함수를 써야하는 문제가 나와서 오랜만에 재귀함수를 쓰게 되었다. 재귀라는 것은 어떤 사건에 대해서 나를 포함하나 나를 사용하여 정의되는 것을 의미한다. 함수로 생각한다면 함수를 정의할때 선언하는 함수가 포함되어있는것을 재귀함수라고 한다. 아래의 함수를 보면 packtorial함수정의 안에 return값으로 packtorial이 다시 포함되는 것을 확인할 수 있다. 만약 if 조건이 없다면 이 함수는 계속해서 무한루프에 빠질 것이다. 그러나 조건을 선언해주었기 때문에 함수가 종료될 수 있는 것이다. n = int(input(..