재귀
-
백준 1915 가장 큰 정사각형Algorithm/BOJ 2021. 4. 19. 20:26
출처: www.acmicpc.net/problem/1915 분류: DP 접근방식 문제 이름처럼 만들 수 있는 가장 큰 정사각형을 찾는 문제입니다. 정사각형의 성질을 생각해보면 DP와 재귀를 활용해 정사각형의 크기를 쉽게 구해낼 수 있습니다. 정사각형은 다른 정사각형의 모음입니다. 3x3짜리 정사각형을 예로 들어볼까요? 각 칸에 정사각형의 크기를 적어보면 다음과 같습니다. 3 2 1 2 2 1 1 1 1 여기서 하나가 빠져서 아깝게 정사각형이 못되는 경우를 생각해보면 다음과 같습니다. 2 2 1 2 1 1 1 1 0 규칙이 보이시나요? 정사각형은 자신을 둘러싸고 있는 정사각형들의 크기 중 가장 작은 값 + 1 만큼이 자신의 크기입니다. 위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠! 이 성질을 ..
-
백준 1074 ZAlgorithm/BOJ 2021. 2. 18. 12:28
출처: https://www.acmicpc.net/problem/1074 분류: 재귀 접근방식 백준 1992 쿼드트리 와 비슷한 문제였습니다. 대신 쿼드트리처럼 전부 방문하면 시간 제한에 걸리게 되기 때문에 어느 사분면에 포함되는지 체크해서 해당 분면만 재귀적으로 호출해줘야 합니다. 방문의 순서는 알고 있기 때문에 해당 사분면에 가능한 방문의 범위도 알 수가 있습니다. 4x4 배열이라면 각각 0~3, 4~7, 8~11, 12~15 사이의 값이 오겠죠? 이를 이용해서 방문 가능한 카운트 범위도 같이 넘겨주면서 해결했습니다. 해결방법 import Foundation extension Int { func pow(_ n: Int) -> Int { var powered = 1 (0..
-
백준 1992 쿼드트리Algorithm/BOJ 2021. 2. 18. 11:20
출처: https://www.acmicpc.net/problem/1992 분류: 재귀 접근방식 사각형의 영역을 1, 2, 3, 4분면씩 쪼개서 재귀로 풀 수 있는 문제였습니다. 고민하다가 잘 모르겠어서 다른 분들 풀이를 참고해서 풀었네요 ㅠ-ㅠ 처음엔 포문을 먼저 돌려서 모두 1인지 0인지 체크하는 방식으로 풀었는데, 다른 분들의 풀이를 보니 어차피 재귀로 돌릴거라면 먼저 체크하지 않아도 결과를 가지고 확인해서 풀 수도 있네요! 해결방법 처음 풀이 포문으로 전부 0인지 1인지 체크, 아니라면 compression func compress(size: Int, at point: Point) -> String { guard size != 1 else { return String(map[point.r][poin..
-
Recursion 재귀Algorithm/Theory 2020. 6. 11. 12:21
많은 일들은 대개 작은 조각들로 나누어 볼 수 있습니다. 그리고 한 조각이 작으면 작을수록 일은 단순해지고 반복되는 형태를 띄는 경우가 많습니다. 완전히 같은 코드를 반복적으로 하는 작업이 있다면 이때 재귀 함수(recursion fnction), recursion(재귀 호출)이 유용하게 사용될 수 있습니다. 1~100까지의 합을 구하는 경우를 재귀적으로 생각해봅시다. 1~100까지의 합은 100 + 1~99까지의 합으로 나눠서 생각할 수 있습니다. 마찬가지로 1~99까지의 합은 99 + 1~98까지의 합으로 볼 수 있겠죠. "n + 1~n-1까지의 합" 이라는 과정은 완벽하게 동일합니다. 이를 코드로 구현해보면, func sum(_ n: Int) -> Int { if n == 1 { return 1 }..