본문 바로가기

BOJ 알고리즘 (패캠)/자료구조, 구현

 (11)
7490번: 0 만들기 (구현, 재귀) - Fastcampus www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net def recur(N, res, a=[]): if N == 1: res.append(a[:]) return for op in (" ", "+", "-"): a.append(op) recur(N-1, res, a) a.pop() T = int(input()) for _ in range(T): N = int(input()) a = list(range(1, N + 1)) res = [] recur(N, res) for ops in res: exp = "" for i i..
1074번: Z (구현, 재귀) - Fastcampus www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 �� www.acmicpc.net def recur(size, cnt=0, x=0, y=0): global res if size == 1: if x == R and y == C: res = cnt cnt += 1 return cnt size //= 2 for i, j in [(x, y), (x, y+size), (x+size, y), (x+size, y+size)]: # 가지치기 추가: 4분면 중 1개만 탐색한다 if (i
2747번: 피보나치 수 (구현, 재귀) - Fastcampus www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된�� www.acmicpc.net # 반복 def fibo(n): a, b = 0, 1 for _ in range(n-1): a, b = b, a+b return b # 재귀 def fibo(n): if n
4195번: 친구 네트워크 (구현, 해시, dict, 분리집합) - Fastcampus 집합을 부모테이블 (Union-Find 알고리즘)으로 표현할 수 있다 www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): rx = find(x) ry = find(y) if rx != ry: parent[ry] = rx count[rx] += count[ry] # 입력: [('Fred'..
1920번: 수 찾기 (구현, 해시, set) - Fastcampus www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net def run(s, nums): res = [] for x in nums: if x in s: res.append(1) else: res.append(0) return res N = int(input()) s = set(map(int, input().split())) # set M = int(input()) nums = list(map(int, input().spli..
10930번: SHA-256 (구현, 해시, hashlib) - Fastcampus www.acmicpc.net/problem/10930 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net import hashlib s = input() encoded = s.encode() hashed = hashlib.sha256(encoded).hexdigest() print(hashed)
5397번: 키로거 (구현, 스택) - Fastcampus www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net # 배열로 풀면 시간초과 (배열의 insert 연산 때문에) def run(string): pwd = [] idx = 0 # 커서의 위치 for ch in string: if ch == "": idx = min(len(pwd), idx + 1) elif ch == "-": if pwd: pwd.pop() idx -= 1 else: pwd.insert(idx, ch) idx += 1 return pwd #..
1966번: 프린터큐 (구현, 큐) - Fastcampus www.acmicpc.net/problem/1966 1966번: 프린터 큐 첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음 www.acmicpc.net from collections import deque def run(N, M, a): qu = deque([(p, i) for i, p in enumerate(a)]) # 큐 cnt = 0 while qu: cp, ci = qu.popleft() if all(cp >= p for p, i in qu): # 중요도가 최대값이면 출력 cnt += 1 if ci == M: return..

티스토리툴바