꾸준하게 거북이처럼

19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 완전탐색 + 빡구현 문제 유형으로, 내가 생각하는 포인트 1. 한 칸에 물고기 번호와 물고기가 바라보는 방향 정보를 위해 3차원 배열 이용하는 것이 포인트. 2. 완전 탐색으로 dfs 재귀 호출할때, 계속되는 참조를 막기 위해서 deepcopy 사용. 3. 상어가 이동할 수 있는 좌표 중 하나를 선택해서 해당 좌표를 재귀 호출 매개변수로 넘겨주기 풀이 1. 상어가 0,0으로 이동. 물고기 먹음 2. 물고기 이동. 서로 바꾸는 방식, 낮은 번호 순..

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 위의 사진은 n == 27일 때 패턴과 주황색으로 표시한 부분은 n== 9일 때의 패턴이다. 그림을 보면 n==9 일 때는 n == 3 일 때의 패턴을 기준으로 만들어지고, n == 27일 때는 n == 9일 때의 패턴을 기준으로 만들어지는 것을 알 수 있다. 아이디어 n == 3일 때의 패턴을 배열로 나타내면 arr = ['***', '* *', '***'] 로 표현할 수 있다. n == 9일 때의 패턴을 찾아보자. 1. arr의 각..

1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 어제도 하노이 탑 문제(11729번)를 풀었는데, 오늘은 문제에서의 조건이 조금만 다른 하노이 탑 문제를 리뷰한다. 이 문제에서는 20이하의 입력일 때는 옮긴 횟수와 그 과정까지 출력이지만, 20을 넘어서면(20< n 즉 2^n - 1 이 점화식임을 알 수 있다. 심각하게 생각하지말고 센스를 길러보자^^ 참고: https://bgspro.tistory.com/6

하노이 탑은 정말 유명한 대표적인 재귀 알고리즘 문제이다. 그렇기 때문이기도 하고 전에 배웠지만 또 까먹어서 정확히 개념을 정리하고자 한다. 하노이 탑에서는 결국은 목적이 모든 원반을 하나씩 옮겨서 1에서 3으로 다 옮겨야한다. 그렇다면 이를 반복적인 부분을 고려해서 크게 3가지로 세분화 할 수 있는데, 1. 작은 원반 n-1개를 즉, 맨 아래 원반을 제외한 나머지 원반. 을 A 에서 B로 이동 2. 큰 원반인 제일 아래 원반 1개를 A에서 C로 이동 3. 작은 원반 n-1개를 다시 B에서 C로 이동 이렇게 크게 나눌 수 있다. 재귀니까 종료조건도 생각해야하는데 n-1부분 재귀를 하다보면 1개가 남을 것이다. 그 때가 종료 조건이 된다. 파이썬 코드로 옮겨 보자면 n = int(input()) a = [..

import sys sys.setrecursionlimit(10**6) 이 두 줄의 코드는 코딩 테스트에서 재귀 관련 문제를 풀 때 거의 필수라고 한다. 중요하니까 기억하자!!