목록baekjoon (solved.ac) (50)
Hikenny25
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..
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net - 분할정복법 import sys input = sys.stdin.readline def divide(arr): l = len(arr) // 2 divided_array = [] for i in [0,l]: for j in [0,l]: divided_array.append([row[j:j+l] for row in arr[i:i+l]]) for i in range(4): ..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net - 그래프 탐색 import sys input = sys.stdin.readline class Graph: def __init__(self, size): self.size = size self.matrix = [[0] * size for _ in range(size)] self.visited = [False] * size def add..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net - 그래프 탐색 import sys input = sys.stdin.readline def search(x,y): global amount_value if x = n or y >= n: return if matrix[x][y] == '1': amount_value += 1 matrix[x][y] = '0' search(x+1,y) search(x-1,y) searc..