눈송이의 개발생활

문제 https://www.acmicpc.net/problem/1260 코드 from collections import deque import sys input = lambda : sys.stdin.readline().strip() def dfs(v): print(v, end=' ') visited[v] = 1 for i in range(1, N+1): if visited[i] == 0 and graph[v][i] == 1: dfs(i) def bfs(v): visited = [0] * (N + 1) # BFS 위해서 초기화하기 queue = deque([v]) visited[v] = 1 while queue: k = queue.popleft() print(k, end=' ') for i in range..

문제 https://www.acmicpc.net/problem/11724 코드 import sys input = lambda : sys.stdin.readline().strip() sys.setrecursionlimit(10000) def dfs(v): visited[v] = 1 for i in range(1, N+1): # 연결되어 있고 visited 아니면 다시 탐색 if s[v][i] == 1 and visited[i] == 0: dfs(i) N, M = map(int, input().split()) s = [[0] * (N+1) for i in range(N+1)] visited = [0 for i in range(N+1)] count = 0 for i in range(M): a, b = map(..

문제 https://www.acmicpc.net/problem/11052 코드 import sys input = lambda : sys.stdin.readline().strip() n = int(input()) p = [0] + list(map(int, input().split())) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for k in range(1, i+1): # dp를 max값으로 계속 갱신 dp[i] = max(p[k] + dp[i-k], dp[i]) print(dp[n]) 풀이 사실 처음에는 접근이 어려워서 힌트를 보고 풀었다🤔 점화식을 찾고 그 점화식에 맞는 코드를 짜서 풀 수 있었다. 문제에 있는 예시로 설명하자면, P1 = 1, P2..

문제 https://www.acmicpc.net/problem/15988 코드 import sys input = lambda : sys.stdin.readline().strip() n = int(input()) dp = [0] * 1000001 dp[1], dp[2], dp[3] = 1, 2, 4 for i in range(4, 1000001): dp[i] = dp[i - 1] % 1000000009 + dp[i - 2] % 1000000009 + dp[i - 3] % 1000000009 for _ in range(n): num = int(input()) print(dp[num] % 1000000009) 풀이 1번째는 메모리 초과, 2번째 시도는 시간초과로 틀린 문제이다 메모리 초과는 왜 나는지 계속 찾..

Deque == Double-Ended Queue 큐의 앞과 뒤에서 모두 삽입/삭제가 가능하다 덱을 이용해서 양방향 큐/원형 큐를 구현할 수 있다 파이썬에서는 collections 모듈 내에 있는 deque를 사용할 수 있다 📌 다양한 함수 append(x) : 맨 끝에 x를 삽입 appendleft(x) : 맨 앞에 x를 삽입 pop() : 맨 뒤에 있는 원소 삭제 popleft() : 맨 앞에 있는 원소 삭제 clear() : 덱 전체를 비움 (len == 0) copy() : 뎃 전체를 복사 count(x) : 덱의 원소 중 x의 개수를 셈 extend(iterable) : iterable 원소들 모두 덱의 맨 끝에 덧붙임 insert(x, i) : index i에 x를 삽입 index(x[, st..

자주 쓰이는 순열, 중복순열, 조합, 중복조합 구현하기 itertools 공식문서에 따르면 itertools는 효율적인 루핑을 위한 iterator를 만드는 함수라고 한다 해당 모듈에는 다양한 함수들이 있다 그 중 자주 나오는 순열 조합 함수들에 대해 정리해 볼 것이다 📌 permutations from itertools import permutations arr = [1, 2, 3, 4] print(permutations(arr, 2)) print(list(permutations(arr, 2))) # # [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)] permutations(li..

문제 https://www.acmicpc.net/problem/1406 코드 #1 - WRONG ❌ from collections import deque import sys input = lambda : sys.stdin.readline().strip() str = deque(input()) n = int(input()) cursor = len(str) for _ in range(n): op = input().split() if op[0] == 'L' and cursor != 0: cursor -= 1 elif op[0] == 'D' and cursor != len(str): cursor += 1 elif op[0] == 'B' and cursor != 0: del str[cursor - 1] curso..

문제 https://www.acmicpc.net/problem/1748 코드 import sys input = lambda : sys.stdin.readline().strip() n = input() answer = 0 length = len(n) - 1 for i in range(length): # i는 0부터 시작 ~ 자릿수보다 하나 작은거까지 answer += (i+1) * 9 * (10 ** i) answer += (length + 1) * ((int(n) - (10 ** length)) + 1) print(answer) 풀이 그리디 유형 문제 중 처음으로 아무런 힌트 없이 쉽게 풀 수 있는 문제였다 예시를 보면 쉽게 패턴을 찾을 수 있다 15 → 123456789 + 101112131415 15..