알고리즘/백준
-
[백준] 10816번 숫자 카드 2 (파이썬)
10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 코드 from sys import stdin _ = stdin.readline() N = sorted(map(int,stdin.readline().split())) _ = stdin.readline() M = list(map(int,stdin.readline().split())) index, m_dic = 0, {} for m in sorted(M): cnt = 0 if m not in m_dic: while index < len..
-
[백준] 1920번 수 찾기 (파이썬)
1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 n = int(input()) A_list = list(map(int, input().split())) m = int(input()) m_list = list(map(int, input().split())) for i in range(m): if m_list[i] in A_list: print(1) else: print(0)
-
[백준] 1780번 종이의 개수 (파이썬)
1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 코드 n = int(input()) li = [] for _ in range(n): li.append(list(map(int, input().split(" ")))) answer = [] def find(x, y, N): color = li[x][y] for i in range(x, x+N): for j in range(y, y+N): if li[i][j] != color: find(x,y, N//3) find(x, y+N//3, N//3) find(..
-
[백준] 1992번 쿼드트리 (파이썬)
1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 코드 n = int(input()) li = [] for _ in range(n): input_li = list(input()) li.append(list(map(int, input_li))) answer = [] def find(x, y, N): color = li[x][y] for i in range(x, x+N): for j in range(y, y+N): if li[i][j] != color: answer.append("(") find(x,y..
-
[백준] 2630번 색종이 만들기 (파이썬)
2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 코드 n = int(input()) li = [] for _ in range(n): li.append(list(map(int, input().split(" ")))) answer = [] def find(x, y, N): color = li[x][y] for i in range(x, x+N): for j in range(y, y+N): if li[i][j] != color: find(x,y, N//2) find(x, y+N//2, N/..
-
[백준] 1010번 다리 놓기 (파이썬)
1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 코드 def factorial(n): if n == 0: return 0 elif n == 1: return 1 else: return n * factorial(n-1) def solution(n, m): a = factorial(m) b = factorial(m-n) if b == 0: return 1 else: return a // (b*factorial(n)) n = int(input()) for _ in range(n): input_li = list(ma..
-
[백준] 11050번 이항 계수 1 (파이썬)
11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 코드 n, k = map(int, input().split(" ")) cache = [[-1 for _ in range(n+1)] for _ in range(n+1)] def choose(times, got): if times == n: return got == k if cache[times][got] != -1: return cache[times][got] cache[times][got] = choose(times+1, got) + choose(times+1, got+1) return cache[times][got] if k > n: p..
-
[백준] 12865번 평범한 배낭 (파이썬)
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 코드 n, k = map(int, input().split()) weight = [] value = [] for i in range(n): w, v = map(int, input().split()) weight.append(w) value.append(v) s = [[0]*(k+1) for i in range(n+1)] for i in range(1,n+1): for j in range(k+1): ..