Data Structure&Algorithm

재귀 함수(Recursive Function) / 꼬리 재귀 함수(Tail Recursive Function)

재귀 함수 목표 재귀의 의미 재귀의 사용 시기 base case와 recursive case에 해당하는 재귀 함수 꼬리재귀함수의 이해 재귀(Recursive Function) 재귀(Recursion)는 자신을 정의할 때 자신을 재참조하는 방법을 의미합니다. 자신을 재참조하는 형태를 재귀 호출(Recursive Call)이라 합니다. 재귀 함수(Recursice Function)는 재귀적으로 자기 자신을 계속 호출하여 작업을 수행하여 문제를 작게 나눠서 답을 도출합니다. 예를 들어, 피보나치수열이나 팩토리얼에서 주로 사용합니다. 재귀적으로 자기 자신을 계속 호출하여 문제를 재귀적으로 작게 나누는 부분을 Recuresive case라고 하고, 더이상 나눌 수 없고 재귀를 탈출하는 부분을 Base Case라고..

토마토 - [백준 7576번]

토마토 - 백준 7576번 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에..

벽 부수고 이동하기 - [백준 2206번]

벽 부수고 이동하기 - 백준 2206번 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,..

타일 채우기 - [백준 2133번]

타일 채우기 - 백준 2133번 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 풀이 dp[1] n = 3 일 때, 경우의 수 : 3 dp[1] = 3 dp[2] n = 4 일 때, 경우의 수 : 11 dp[1] * dp[1] + 2 ( 새로운 모양 2개 ) dp[3] n = 6 일 때, 경우의 수 : 41 dp[1] * dp[2] + dp[2] * 2 ( dp[2] * 새로운 모양 ) + 2 ( 새로운 모양 2개 ) dp[4] n = 8 일 때, 경우의 수 : 153 dp[1] * dp[2] + dp[3] * 2 ( dp[2] * 새로운 모양[2] 2개 ) + dp[2] *..

캥거루 세마리2 - [백준 11034번]

캥거루 세마리2 - 백준 11034번 문제 캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇 번 움직일 수 있을까? 입력 여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) 출력 각 테스트에 대해 캥거루가 최대 몇 번 움직일 수 있는지 출력한다. 풀이 그리디 알고리즘?? 코드 import sys def threeKangaroo(a, b, c): a, b, c = sorted([a, b, c])..

전자레인지 - [백준 10162번]

전자레인지 - 백준 10162번 def microwave(second): button = [5 * 60, 1 * 60, 10] # 전자레인지 시간조절 버튼(단위 - 초) result = [] time = second if time % 10 != 0 : return -1 result.append(str(time // button[0])) # A버튼 갯수 time %= button[0] result.append(str(time // button[1])) # B버튼 갯수 time %= button[1] result.append(str(time // button[2])) # C버튼 갯수 return &#39; &#39;.join(result) # 출력 형태 : 0 0 0 &#39;&#39;&#39;테스트&#39..

세탁소 사장 동혁 - [백준 2720번]

세탁소 사장 동혁 - 백준 2720번 문제 미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 동혁이는 리암에게 실망했다. 리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다! 어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다. 거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈..

신입사원 - [백준 1946번]

신입사원 - 백준 1946번 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램..

도서관 - [백준 1461번]

도서관 - 백준 1461번 문제 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수 계산하는 프로그램 작성 세준이는 0에 위치, 책도 전부 0에 반납 한 걸음에 1칸씩, 최대 M권을 들 수 있고, 다시 0으로 돌아올 필요 없다. 입력 첫째 줄 - 책 개수 N, 한 번에 들 수 있는 책의 개수 M 둘째 줄 - 책의 원래 위치 출력 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수 코드 import sys '''' 왼쪽(음수)과 오른쪽(양수)로 나뉨 책들 모두 들면 다시 돌아와야하기 때문에 *2 책을 모두 제자리에 두고 그 자리에서 끝나기 때문에 최대값에서는 *1만 하기 때문에 책의 최대 거리 * 2 - 최대값 으로 계산함 ''' def solution(M, originLocations): result = 0 '..

강의실 - [백준 1374번]

강의실 - 백준 1374번 문제 N개의 강의 최대한 적은 수의 강의실을 사용하여 모든 강의 진행 한 강의실에서 동시에 강의 진행 불가 종료시간과 시작시간이 같아도 상관 없음 필요한 최소 강의실의 수 출력 입력 첫째 줄 - N : 강의 갯수(1