본문 바로가기
728x90

재귀2

재귀, DFS 알고리즘하면서 재귀의 중요성을 알려준 DFS. 하지만 어려워서 계속 까먹는다. 그래서 이번에 정리를 아예 해둘려고 한다. 재귀를 쓰는 이유 뭐 사실 알고리즘 시간에서는 특정 케이스를 제외하면 시간복잡도나 효율면에서 떨어진다고 학습을 하기 마련이다. 하지만 재귀를 사용하면 수많은 for문을 사용해야되는 경우, 복잡한 코드 같은 경우를 손 쉽게 구현할 수 있다. 종만북에서 n 개의 서로 다른 원소a 중 x 개의 원소를 순서를 고려해서 뽑는 경우의 수를 구한다면, x개만큼의 반복문이 필요하기 때문 재귀함수를 잘 사용할려면 문제를 소문제로 잘 분리 시켜야된다. 간단한 아래 예시를 보자 아래는 중복순열을 구하는 재귀함수코드이다. 이 코드의 핵심은 트리를 만들면서 진행한다는 소리인데 이게 아는 사람들은 금방 이해하.. 2024. 4. 6.
[백준] 2630번: 색종이 만들기 - python https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 처음에 작성한 무지성 4로 나눠 재귀하기 코드이다. 너무 비효율적이고 틀렷다고 떠서 다시 로직을 작성하였다. n = int(input()) arr = [] blue = 0 white = 0 def paper(n, x_start, x_end, y_start, y_end): global blue global white x_mid = (x_start + x_end) //2 y.. 2024. 4. 4.
728x90