www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys from collections import deque input = sys.stdin.readline q = deque() M, N, H = map(int,input().split()) dx, dy, dz = [1,-1,0,0,0,0], [0,0,-1,1,0,0], [0,0,0,0,-1,1] m = [[list(map(int,input().split())) for _ ..
www.acmicpc.net/problem/21316 21316번: 스피카 위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다. 시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 www.acmicpc.net # 입력되는 숫자만 다르고 그래프 모양은 같으므로 "Spica가 몇번인지 어떻게 판단할까??" 생각해본 결과 그래프의 정점의 간선의 갯수로 판단을 해보자고 생각했다. 1. 별자리가 그래프라고 생각하고 x, y가 입력되면 서로 연결되있는 것으로 생각했다. dic[x]에 y를 append하는 식으로 x정점과 연결되어있는 정점들을 모두 저장했다. 별자리를 보면 알 수 있듯이 정점과 연결된 간선의 갯수는 모두 1..
www.acmicpc.net/problem/21318 G번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 단순히 수학문제여서 정석대로 풀었다가 혼쭐난 문제이다. 1. 처음에 그냥 for문으로 hard배열(난이도)를 돌면서 현재 난이도가 다음 난이도보다 높으면 miss에 1을 더해주고 miss를 return 해주는 식으로 풀었다. import sys input = sys.stdin.readline N = int(input()) hard = list(map(int,input().split())) def mistake(x,..
- 유클리드 호제법: 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 그냥 쉽게 말해 A = Bq + R이라는 식에서 A와 B의 최대공약수(GCD)는 B와 R의 GCD와 같다는 뜻이다. 이 알고리즘을 사용하면 빠르게 A와 B의 최대공약수를 구할 수 있다. - 증명은 다음 블로..
www.acmicpc.net/problem/18291 18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net 일단 N=1일 때부터 직접 계산해보면서 규칙을 찾아보았다. N=1일 때 1, N=2일 때 1, N=3일 때 2, N=4일 때 4, N=5일 때 8 ... N=1일 경우를 제외하고 2의 (N-2)제곱이 나오는 것을 확인 할 수 있었다. 단순히 print(2**(N-2))를 하면 N의 범위가 최대 10**9이므로 O(10**9)가 되어서 시간초과가 발생한다. 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다. # 분할정복을 이용한 거듭제곱은 따로 정리해..
# 분할정복을 이용한 거듭제곱 - C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다. - 아래 코드에서 fpow함수가 그 방법이다. - n이 1이면 그냥 C의 1제곱이므로 return C를 해준다. - n이 2이상일 때, C의 n제곱은 다음과 같다. - n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다. 코드로 짜면 다음과 같다. 1. 재귀사용 def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x * x * C 2. 반복문 사용 - n & 1은 n이 짝수이면 0이므로 False이고, n이..
www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net (0, 0)에서 (M-1, N-1)까지 이동 가능한 경로의 수를 모두 구해야 하기 때문에 단순히 DFS로는 풀 수 없고, DP를 통해 메모이제이션까지 써야 한다. 1. N * M크기의 지도 m을 입력받고, dp배열을 만들고 -1로 채운다. 2. dp[i][j] = (i, j)까지 이동하는 경로의 수 3. (M-1, N-1)부터 상하좌우 방향을 탐색하며 dp[x][y]에 dfs(nx, ny)값을 더해준다. ->..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이번엔 DFS로 푼 문제이다. dfs함수: m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다. 전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다. BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데 DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는 집의 수를 ..
모르는 사이에 조금씩 조금씩..
