잡다로그

1629 곱셈 문제 및 조건 설명: https://www.acmicpc.net/problem/1629 알고리즘 설계 💡idea. 문제에서 주어진 대로 바로 a 곱셈을 b번 반복하면, 시간 초과 판정이 날 수 있다. (b가 최대 21억이기 때문) 수행해야 하는 연산은 곱셈 또는 나머지 연산으로 동일하므로 재귀함수를 사용할 수 있다. $a^n * a^n = a^{2n}$이 힌트가 된다. 🎲step. 1. 함수 정의 a를 b번 곱해서 m으로 나눈 수를 출력한다. ($a^b$ mod m 계산) def POW(a, b, m) 2. base condition b = 1 일 때 종료 3. 재귀 $a^n * a^n = a^{2n}$을 힌트 삼아, 계속해서 지수를 이등분하여 제곱 연산량은 줄이면서 나머지를 구할 수 있다..

1074 Z 문제 및 조건 설명: https://www.acmicpc.net/problem/1074 알고리즘 설계 💡idea. 사각형을 사등분하고, 각 부분에 같은 연산을 적용할 수 있으므로 재귀적으로 생각한다. 시간 제한이 0.5초이고 입력 제한이 1 ≤ N ≤ 15 이므로, 무작정 반복하면 시간/메모리 초과 오류를 마주하게 되니 주의하자. 🎲 step. 1. 함수의 형태 $(x, y)$로 시작하는 $n*n$ 크기의 사각형을 탐색하는 함수 def func(n, x, y) 2. base condition (종료 조건) 탐색을 시작하려는 사각형의 시작 좌표가 찾고자 하는 $(r, c)$와 동일할 때 종료 3. 재귀 사등분한 사각형에 대해 같은 규칙(=재귀 함수)을 적용한다. 사각형이 한 칸씩 네 칸이 될 ..

11729 하노이 탑 이동 순서 문제 및 조건 설명: https://www.acmicpc.net/problem/11729 알고리즘 설계 💡idea. 어떠한 규칙은 있지만, 모든 경우를 따져주기에는 복잡해 보인다. → 절차지향적 사고가 아닌, 귀납적 사고로 접근하자❗ 단계별로 생각해서 일반항을 유추해 내는 것이 아니라, 특정 규칙(해당 문제에서는 'i에서 k로 이동한다.')이 반복되면 n항에도 적용이 된다는 귀납적 사고를 적용하는 것. 단계별로 어떤 모양이 될지를 고민하지 말 것. 그냥, 냅다, 적용하기. 즉, 가장 큰 n번 원판을 옮기기 위해서는 n-1개의 원판을 전부 기둥 1에서 기둥 2로 옮긴다. n번 원판을 기둥 1에서 기둥 3으로 옮긴다. n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다. → 재..

1388 바닥장식 문제 및 조건 설명: https://www.acmicpc.net/problem/1388 알고리즘 설계 💡idea. 같은 타일인지 확인하기 위해 BFS 사용한다. 가로, 세로를 따로 세어 총합을 구한다. - 다른 BFS 함수를 사용한다. 🎲step. 가로(-)일 때는 BFS를 좌, 우에 대해서만 반복 탐색한다. 전체 그래프를 반복하는데, '-' 일 때만 BFS 시작한다. 세로(|)일 때는 BFS를 상, 하에 대해서만 반복 탐색한다 전체 그래프를 반복하는데, '|' 일 때만 BFS 시작한다. 두 번 반복한다. BFS 실행을 시작할 때마다 타일의 갯수를 1 증가시킨다. * 결국 BFS 함수는 반환 값 없이, 과정에서 방문표시를 하기 위해 진행하게 된다. 코드 구현 from collection..