Hikenny25

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net - BFS import sys input = sys.stdin.readline from collections import deque m, n = map(int, input().split()) tomato = [list(map(int, input().split())) for _ in range(n)] q = deque() for i in range(n): for j in range(..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net - 구현 import sys input = sys.stdin.readline n = int(input()) m = int(input()) s = input()[:-1] p = 'I' for _ in range(n): p += 'OI' try: idx = s.index('IOI') except: print(0) exit() cnt ..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net - 분할정복법 import sys input = sys.stdin.readline def divide(arr): l = len(arr) // 2 print('(', end='') for i in [0,l]: for j in [0,l]: quadtree([row[j:j+l] for row in arr[i:i+l]]) print(')', end='') def quadtree(matrix)..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net - BFS import sys input = sys.stdin.readline from collections import deque class Graph: def __init__(self, size): self.size = size self.matrix = [[0] * size for _ in range(size)] self.visited = [Fa..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - DP - BFS n, k = map(int, input().split()) dp = [int(1e9)] * 200001 dp[n] = 0 if n == 0: dp[1] = 1 dp[2] = 2 else: dp[n-1] = 1 dp[n+1] = 1 dp[2*n] = 1 if n >= k: print(n-k) exit() for i in range(n+1, k+1): i..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - BFS import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) maze = list() for _ in range(n): maze.append([int(i) for i in input().strip()]) bfs = [[1,0],[0,1],[-1,0],[0,-1]] visited = [[False] *..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline def isint(x): return not (x-int(x)) n = int(input()) dp = [int(1e9)] * (n+1) dp[1] = 1 k = [1] for i in range(2, n+1): if isint(i**0.5): dp[i] ..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net - 분할정복법 import sys input = sys.stdin.readline def divide(arr): l = len(arr) // 3 for i in [0,l,2*l]: for j in [0,l,2*l]: check([row[j:j+l] for row in arr[i:i+l]]) def check(paper): l = len(paper) data = [[paper[0][0]]..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net - 분할 정복법 import sys input = sys.stdin.readline n, r, c = map(int, input().split()) pow2 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768] pow4 = [i*i for i in pow2] area_list = list() while n > 0: # n번 반..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net - 정렬 - 구현 import sys input = sys.stdin.readline n = int(input()) x = list(map(int, input().split())) xl = list(set(x)) xl.sort() d = dict() for i in range(len(xl)): d[xl[i]] = i for i in x: print..