공작소

문제 링크 : https://www.acmicpc.net/problem/1074풀이 과정2xN 배열을 4등분 했을 때 어느 방향으로 갈지에 따라 다르게 탐색하는 재귀함수를 작성하여 풀이했다.전체 코드# 1074 : Zimport sysinput = sys.stdin.readlinedef func(size, start, sr, sc, er, ec): if size == 0: print(start) return # -- 4등분 했을 때 # 왼쪽 위에 있다면 if sr

문제 링크 : https://www.acmicpc.net/problem/1012풀이 과정BFS를 이용해 이웃한 배추 그룹의 개수를 센다.전체 코드# 1012 : 유기농 배추import sysfrom collections import dequeinput = sys.stdin.readlinet = int(input().rstrip())for _ in range(t): m, n, k = map(int, input().rstrip().split()) maps = [[False for _ in range(m)] for _ in range(n)] for _ in range(k): x, y = map(int, input().rstrip().split()) maps[y][x] ..

문제 링크 : https://www.acmicpc.net/problem/1003풀이 과정fibonacci(N) 이 0을 출력하는 횟수는, fibonacci(N-1) 에서 0을 출력하는 횟수 + fibonacci(N-2) 에서 0을 출력하는 횟수와 같다.이는 1을 출력할 때도 동일하다. 해당 점화식을 활용해 DP 테이블을 채워서 출력한다.전체 코드# 1003 : 피보나치 함수import sysinput = sys.stdin.readlinedp = [[0, 0] for _ in range(41)]dp[0] = [1, 0]dp[1] = [0, 1]for i in range(2, 41): dp[i] = [dp[i-2][0] + dp[i-1][0], dp[i-2][1] + dp[i-1][1]]t = int(inp..

문제 링크 : https://www.acmicpc.net/problem/11724풀이 과정BFS 를 이용해 연결되있는 그룹들의 개수를 셌다.전체 코드# 11724 : 연결 요소의 개수import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())edges = [[] for _ in range(n+1)]for _ in range(m): u, v = map(int, input().rstrip().split()) edges[u].append(v) edges[v].append(u)visited = [False for _ in range(n+1)]cnt = 0for i i..

문제 링크 : https://www.acmicpc.net/problem/1927풀이 과정파이썬의 heapq 라이브러리를 이용해 풀이했다.전체 코드# 1927 : 최소 힙import sysimport heapqinput = sys.stdin.readlinen = int(input().rstrip())pq = []for _ in range(n): v = int(input().rstrip()) if v == 0: print(heapq.heappop(pq) if pq else 0) else: heapq.heappush(pq, v)

문제 링크 : https://www.acmicpc.net/problem/11723첫 번째 과정파이썬의 set 자료형을 이용해 풀이했다.첫 번째 코드# 11723 : 집합import sysinput = sys.stdin.readlineS = set()m = int(input().rstrip())for _ in range(m): ope = list(input().rstrip().split()) if ope[0] == 'add': S.add(int(ope[1])) elif ope[0] == 'remove': if int(ope[1]) in S: S.remove(int(ope[1])) elif ope[0] == 'check': print(1 if int(o..

문제 링크 : https://www.acmicpc.net/problem/11659풀이 과정구간 합 배열을 O(N) 만에 구하여 들어오는 요청을 O(1) 씩 M번 수행한다.시간 복잡도 : $ O(N) + O(M) $전체 코드 # 11659 : 구간 합 구하기 4import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())arr = list(map(int, input().rstrip().split()))sums = [0]for i in range(n): sums.append(sums[-1] + arr[i])for _ in range(m): a, b = map(int, input().rstrip().split()) p..

문제 링크 : https://www.acmicpc.net/problem/21736풀이 과정I 부터 시작하는 너비 우선 탐색을 이용해 방문하는 P 의 개수를 셌다.전체 코드# 21736 : 헌내기는 친구가 필요해import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())maps = [list(input().rstrip()) for _ in range(n)]queue = deque()visited = [[False for _ in range(m)] for _ in range(n)]for i in range(n): for j in range(m): if maps[..