이번주 목표는 재귀 파트 넘기기
재귀 나에게 매우 어렵다 예전에도 알고리즘 공부하다가 재귀 파트에서 포기했던 기억이 난다
이젠 포기도 불가능 많이 풀어서 외워버릴테다
재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
- 함수를 명확하게 정의해야 함
- 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다 -> 반복문보다 메모리/시간에서 손해를 본다
- 자기 자신을 여러 번 호출하면 비효율적일 수 있다 -> 동일한 연산을 하는 함수 호출이 반복될 경우
재귀의 조건
1. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 : base condition
2. 모든 입력은 base condition으로 수렴해야 함
1,2중 한 조건이라도 무시된다면 무한으로 돌게 됨
절차지향적 사고를 탈피해 귀납적으로 사고해야 한다
잘안된다고요.....ㅠ)
BOJ
재귀적으로 풀기위한 귀납적 사고
- 1승을 계산할 수 있다
- k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다
예를 들어 a^4을 계산해야 한다고 하면 지수법칙을 적용해서 a^ * a^을 해주면 된다
여기에 다시 지수법칙을 적용하여 분할하면 (a * a) * (a * a)로 표현할 수 있다
만약 2^7을 계산한다면(2^4) * 2^2 * 2로 짝수승과 같이 계산한 후 2를 한번 더 곱해주면 된다
이건 아래와 같이 재귀로 표현할 수 있다
fun pow(a: Int, b: Int): Int { // a: 밑, b: 지수
if (b == 1) return a
val tmp = pow(a, b / 2)
if (b % 2 == 0)
return tmp * tmp * 2
return tmp * tmp
}
문제에서 입력값이 21억이 넘기 때문에 (int 표현 범위 초과) 모듈러 산술 연산의 분배법칙을 적용하여 계산해주어야 한다
(a * b) mod c = (a mod c * b mod c) mod c
fun pow(exponent: Long): Long {
if (exponent == 0L) return 1
if (exponent == 1L) return a % c
val result = pow(exponent / 2)
if (exponent % 2 == 0L)
return result * result % c
return (result * result % c) * a % c
}BOJ
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 하기 때문에 시작 지점에서 제일 밑에 있는 원판이 가장 먼저 도착 지점으로 옮겨져야 한다.
n번째 원판을 도착지점으로 옮기기 위해선 n-1 ~ 1번 원판이 시작지점도 도착지점도 아닌 곳에 옮겨져야 한다
n-1 ~ 1번 원판이 옮겨졌으면 n번 원판을 도착지점으로 옮긴다
n번 원판이 옮겨졌으면 n-1 ~ 1번 원판을 도착지점으로 옮긴다
종료 조건 : 옮길 원판이 맨 위에 있는 원판일 경우 n = 1
항상 n보다 작을 경우에 대해 함수를 호출하기 때문에 n = 1이라는 종료조건에 수렴할 수 있다
import java.io.*
private val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
hanoi(n, 1 , 3)
bw.close()
}
fun hanoi(n: Int, from: Int, to: Int) {
if (n == 1) {
bw.write("$from $to\n")
return
}
hanoi(n-1, from, 6 - from - to)
bw.write("$from $to\n")
hanoi(n-1, 6 - from - to, to)
}
r,c 를 찾기 위해 완전 탐색하면 시간초과가 난다
배열을 4등분 했을 때 r,c가 어떤 구역에 속하는지 알면 나머지 구역은 탐색할 필요가 없어진다
따라서 배열을 4등분해서 구역을 좁혀가며 r,c의 위치를 찾는다
n이 3이고 지그재그 형태로 (0,0)부터 방문한다고 했을 때 (6,5)를 몇번째로 방문하는지를 구해보자
우선 구역을 좁히기 위해 4등분 해야 한다
구역 별 인덱스 범위를 나타내면 아래와 같다
- row < n/2 * n/2, col < n/2 * n/2
- row < n/2 * n/2, col >= n/2 * n/2
- row >= n/2 * n/2, col < n/2 * n/2
- row >= n/2 * n/2, col >= n/2 * n/2
(r,c)는 4번구역 범위에 해당하기 때문에 탐색 범위를 좁혀준다
그리고 4번구역에서 탐색을 시작하기 전 해주어야 하는 계산이 있다
4번 구역 탐색을 한다는 것은 이미 앞선 구역(1,2,3)들에 대해 탐색을 마쳤다는 전제가 깔려있기 때문에
4번까지 오는데 몇번이나 방문했는지를 계산해야 한다
규칙에 따라 계산하면 n/2 * n/2 * 3 = 48이다
범위를 좁혀 탐색을 진행하기 위해 좁혀진 범위에서의 상대적인 (r,c) 값을 알아야 한다
원래는 (6,5)였으나 줄어든 범위내에서 (r,c) 값은
(6- n/2, 5- n/2) -> (2, 1)이 된다
위 과정과 마찬가지로 4등분하여 (r,c)가 속한 영역을 찾아 그 부분에서만 탐색을 진행하도록 한다
좁혀진 범위 크기가 1이 될 경우 (r,c) 값을 찾은 것이기 때문에 탐색을 종료한다
import java.io.*
import java.util.*
import kotlin.math.*
private var r = 0
private var c = 0
private var count = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val st = StringTokenizer(readLine())
val n = st.nextToken().toInt() + 0.0
r = st.nextToken().toInt()
c = st.nextToken().toInt()
z(r, c, 2.0.pow(n).toInt())
print("$count")
}
fun z(row: Int, col: Int, size: Int) {
if (size == 1) return
val half = size / 2
// 1
if (row < half && col < half) {
z(row, col, half)
}
// 2
else if (row < half && col >= half) {
count += half * half
z(row, col - half, half)
}
// 3
else if (row >= half && col < half) {
count += half * half * 2
z(row - half, col, half)
}
// 4
else {
count += half * half * 3
z(row - half, col - half, half)
}
}
종이가 같은 색으로 칠해져 있지 않을 경우 4등분 한다고 할 때, 최종적으로 만들어지는 하얀 종이와 파란 종이의 수를 구하는 문제다
1. 영역을 탐색하며 같은 색의 종이인지 확인한다
2. 이때 색이 같지 않은 종이가 나온다면 종이를 자른다
잘라진 종이 구역에서 1을 진행한다
import java.util.*
import java.io.*
private var white = 0
private var blue = 0
private lateinit var arr: Array<IntArray>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
arr = Array(n) { IntArray(n) }
for (i in 0 until n) {
val st = StringTokenizer(readLine())
for (j in 0 until n) {
arr[i][j] = st.nextToken().toInt()
}
}
partition(0, 0, n)
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("$white\n$blue")
bw.close()
}
fun partition(row: Int, col: Int, n: Int) {
val color = arr[row][col]
if (checkColor(row,col, n)) {
if (color == 1)
blue++
else
white++
return
}
// 색종이 자르기
val size = n / 2
partition(row, col, size)
partition(row + size, col, size)
partition(row, col + size, size)
partition(row + size, col + size, size)
return
}
fun checkColor(row: Int, col: Int, size: Int): Boolean {
for (i in row until row+size) {
for (j in col until col+size) {
if (arr[i][j] != arr[row][col])
return false
}
}
return true
}
위 색종이 만들기와 유사한 문제
드디어 내가 푼 재귀 문제가 생겼다 🥹
1. 영역에서 모두 같은 수로 된 종이만 존재하는지 확인한다
2. 같지 않다면 종이를 9개로 나눈다(나눠진 한 영역의 크기는 n/3)
나눠진 영역에서 1을 진행한다
각 영역의 첫번째 칸의 위치를 넘겨주어 첫째칸 ~ 해당 영역 마지막 칸까지 탐색을 진행하며 같은 종이인지 확인한다
| 0,0 | 0,3 | 0,6 | ||||||
| 3,0 | 3,3 | 3,6 | ||||||
| 6,0 | 6,3 | 6,6 | ||||||
import java.util.*
import java.io.*
private var count0 = 0
private var count1 = 0
private var countM1 = 0
private lateinit var arr: Array<IntArray>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
arr = Array(n) { IntArray(n) }
for (i in 0 until n) {
val st = StringTokenizer(readLine())
for (j in 0 until n) {
arr[i][j] = st.nextToken().toInt()
}
}
count(n, 0, 0)
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("$countM1\n$count0\n$count1")
bw.close()
}
private fun count(size: Int, row: Int, col: Int) {
// 영역을 탐색한다
if (check(size, row, col)) {
when (arr[row][col]) {
0 -> count0++
1 -> count1++
else -> countM1++
}
return
}
// 영역을 9개로 나눈다
val nSize = size / 3
count(nSize, row, col) // 1
count(nSize, row, col + nSize) // 2
count(nSize, row, col + (nSize * 2)) // 3
count(nSize, row + nSize, col) // 4
count(nSize, row + nSize, col + nSize) // 5
count(nSize, row + nSize, col + (nSize * 2)) //6
count(nSize, row + (nSize * 2) , col) // 7
count(nSize, row + (nSize * 2), col + nSize) // 8
count(nSize, row + (nSize * 2), col + (nSize * 2)) // 9
}
private fun check(size: Int, row: Int, col: Int): Boolean {
for (i in row until row + size) {
for (j in col until col + size) {
if (arr[i][j] != arr[row][col]) return false
}
}
return true
}
재귀함수가 뭔가요? 몰라요! ㅡㅡ
n이 2일 때 출력되어야 하는 내용
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.
종료 조건 : n == 0 일때
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
반복되어야 하는 부분
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."라고 답변하였지.
import java.io.*
import java.lang.StringBuilder
private val sb = StringBuilder()
private var repeat = 0
private val msg1 = "\"재귀함수가 뭔가요?\"\n"
private val msg2_0 = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n"
private val msg2_1 = "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n"
private val msg2_2 = "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n"
private val msg3 = "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n"
private val msg4 = "라고 답변하였지.\n"
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
repeat = readLine().toInt()
sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n")
recursion(repeat)
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write(sb.toString())
bw.close()
}
private fun recursion(n: Int) {
if (n == 0) {
sb.append("_".repeat(repeat * 4))
sb.append(msg1)
sb.append("_".repeat(repeat * 4))
sb.append(msg3)
sb.append("_".repeat(repeat * 4))
sb.append(msg4)
return
}
sb.append("_".repeat((repeat-n) * 4))
sb.append(msg1)
sb.append("_".repeat((repeat-n) * 4))
sb.append(msg2_0)
sb.append("_".repeat((repeat-n) * 4))
sb.append(msg2_1)
sb.append("_".repeat((repeat-n) * 4))
sb.append(msg2_2)
recursion(n-1)
sb.append("_".repeat((repeat-n) * 4))
sb.append(msg4)
}
1. 같은 숫자로만 되어 있는지 확인한다
2. 같은 숫자로 되어 있지 않을 경우 영역을 4개로 나눈다
- 영역을 나눌 때마다 괄호 열고 네구역 탐색이 끝나면 괄호 닫아주기
import java.io.*
private lateinit var arr: Array<CharArray>
private val sb = StringBuilder()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
arr = Array(n) { CharArray(n) }
for (i in 0 until n) {
val s = readLine()
s.forEachIndexed { j, c ->
arr[i][j] = c
}
}
quadTree(n, 0, 0)
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write(sb.toString())
bw.close()
}
private fun quadTree(size: Int, r: Int, c: Int) {
if (check(size, r, c)) {
when (arr[r][c]) {
'0' -> sb.append('0')
'1' -> sb.append('1')
}
return
}
val nSize = size / 2
// 영역 나누기
sb.append('(')
quadTree(nSize, r, c)
quadTree(nSize, r, c + nSize)
quadTree(nSize, r + nSize, c)
quadTree(nSize, r + nSize, c + nSize)
sb.append(')')
}
private fun check(size: Int, r: Int, c: Int): Boolean {
for (i in r until r + size) {
for (j in c until c + size) {
if (arr[i][j] != arr[r][c]) return false
}
}
return true
}
ㅇ
ㅇ
