본문 바로가기

재귀

(6)
[ BOJ / 파이썬 ] 쿼드트리 재귀 재귀 문제에서 지금 반복해 연습 중인 도형 자르기 문제. 6개월 전 풀었던 풀이를 바탕으로 시간복잡도 줄이기 위해 코드를 정리해나가봤다. 우선, 6개월 전 풀이. # 하.. 처음에 quadtree짤 때, return 받아서 print하게 한 걸, # 수정하면서 같이 안 고쳐줘서 엄한 데서 오류 찾고 있었다. 시간 많이 잡아먹었다:-( import sys input = sys.stdin.readline n = int(input()) board = [list(map(int, input().strip())) for _ in range(n)] def quadtree(x, y, n): if n == 1: print(board[x][y], end="") return canCompress = True for i..
[ BOJ / 파이썬 ] 11729. 하노이 탑 이동 순서 와.. 정말 초등 기초 교구느낌이었던 하노이 탑인데.. 생각해보면 나는 어렸을 때 풀어본 적이 없다. 하하 그래서일까 꽤 버거웠다. 핵심은 반복되는 재귀 구조의 일반항을 찾아내는 것. function(n) 에서 function(n-1)을 이용한 function(n)의 내용을 정리하는 게 핵심이었다. 사실 이게 재귀 문제의 핵심이라 어려운 부분인데.. 그래서 더 끈질기게 이 문제 잡고 늘어지면서 이해를 했던 것 같다. 어떤 문제를 만나도 잘 풀어낼 수 있도록 문제 자체에서 그 방식을 읽어내는 사고를 갖고자 했다. 정말 ! 정말 ! 도움이 많이 됐던 글.. ( 링크 ) 위의 글을 참고해서 풀어낸 코드. 정답. def move(k, start, to): global result result.append((st..
[ BOJ / 파이썬 ] 1780 종이의 개수 (22.08.25) / 다시 제출 / import sys input = sys.stdin.readline n = int(input()) paper = [list(map(int, input().split())) for _ in range(n)] typeCount = {-1:0, 0:0, 1:0} def cut(x, y, n): if n == 1: typeCount[paper[x][y]] += 1 return type = checkPaper(x, y, n) if type != None: typeCount[type] += 1 return else: for i in range(3): for j in range(3): cut(x + (i * (n // 3)), y + (j * (n//3)), n //3) def ..
[ BOJ / 파이썬 ] 1991 트리 순회 재귀 진짜 너무 안 된다. 머리가 안 도는건가. https://fre2-dom.tistory.com/231 [baekjoon] 백준 1991번(파이썬): 트리 순회 문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름 fre2-dom.tistory.com 라고 우울해했었으나, 저녁 먹고 재귀 몇 문제 더 보고 다시 오니까 이해가 된다. 다시 으쌰으쌰해서 풀어봤다. / 제출 1 / import sys input = sys.stdin.readline n = int(input()) tree = {} start ='' for i in range(n): no..
[ BOJ / 파이썬 ] 1074 Z / 제출 1 / import sys input = sys.stdin.readline n, r, c = map(int, input().split()) def findOrderZ(n, r, c): if n == 0: return 0 half = 2**(n-1) if r < half and c < half: return findOrderZ(n-1, r, c) if r < half and half
[ BOJ / 파이썬 ] 11729 하노이 탑 이동 순서 어떤 분이 통곡의 하노이 탑이라고 적었던데 동의한다. 나는 왜 이 문제가 그 어떤 문제보다 이해가 안 되었을까.. 다행히 널리 알려진 문제라 설명이나 풀이가 많아 엄청 많이 찾아보고 각 설명의 핵심 포인트가 모여 이해 가능하게 정리되었다. 처음 접한 설명 https://blog.encrypted.gg/943?category=773649 [실전 알고리즘] 0x0B강 - 재귀 안녕하세요, 재귀 파트를 시작하겠습니다. 지금 자신있게 말할 수 있는게 있는데 이 파트가 정말 어려울 것입니다. 물론 이전의 내용들 중에서도 군데군데 어려운게 있었겠지만 이번 단원에서 blog.encrypted.gg 1. 재귀에 대해 다시 생각하자. 재귀는 절차지향적인 연산흐름과 떨어뜨려놓아야 한다. 사고를 바꿔야 쉽게 다가올 것. 2..