백준

👉🏻 16946번: 벽 부수고 이동하기 4 from collections import dequeimport sys; input=sys.stdin.readlinedef bfs(i, j, group_id): q = deque() q.append((i, j)) visited[i][j] = True count = 1 # 현재 그룹의 0 개수 while q: x, y = q.popleft() group_ids[x][y] = group_id # 그룹 번호 할당 for d in range(4): nx = x + dx[d] ny = y + dy[d] if nx = n ..

👉🏻 10775번: 공항import sys; input=sys.stdin.readlinegates = int(input())N = int(input())airplanes = [int(input()) for _ in range(N)]parent = list(range(gates+1))def find(x): if parent[x] == x: return x else: parent[x] = find(parent[x]) return parent[x]def union(x, y): x = find(x) y = find(y) if x != y: parent[x] = ycnt = 0for i in range(N): gate =..

👉🏻 2230번: 수 고르기 import sys; input=sys.stdin.readlineN, M = map(int, input().split())num = sorted([int(input()) for _ in range(N)])left, right = 0, 1ans = float('inf')while right  💡 왜 이렇게 풀었을까?저는 투 포인터를 사용해서 해당 문제를 풀었습니다. 이제는 왜 투 포인터를 사용하는지 알겠더군요.M과 A[i]의 크기 범위만 봐도 2중 반복문으로 걸러내기엔 시간 초과가 날 것만 같았습니다.투 포인터는 정렬된 상태에서 탐색하면 두 수의 차이를 조금 더 효율적으로 계산할 수 있고,그래서 특정 차이를 만족하는 두 수를 빠르게 찾기 위해 투 포인터 기법을 활용해봤습니..

👉🏻 6603번: 로또☀️ 오늘의 문제def generate_lotto(numbers, selected, start, ____): # 목표 개수 if len(selected) == ____: # 로또 번호 개수 체크 print(' '.join(map(str, selected))) return for i in range(start, len(numbers)): selected.append(numbers[i]) generate_lotto(numbers, selected, ____, target) # 다음 시작 인덱스 selected.pop()while True: input_data = list(map(int, input()..

👉🏻 1517번: 버블 소트☀️ 오늘의 문제def merge_sort(arr, temp, left, right): # 병합 정렬의 종료 조건을 나타내는 코드, 배열의 크기가 1이하인 경우 if ____: return 0 mid = (left + right) // 2 inv_count = 0 # 왼쪽과 오른쪽을 나누어 정렬하고 swap 횟수를 계산 inv_count += merge_sort(arr, temp, left, mid) inv_count += merge_sort(arr, temp, mid + 1, right) # 병합 과정에서 swap 횟수를 계산 inv_count += merge(arr, temp, left, mid, right) ..

항해 99에서 자체적으로 새롭게 제작한 크롬 익스텐션 '탭고리즘'이라는 서비스가 최근 공개되었습니다.이 '탭고리즘'에서 출제되는 문제들이 백준 골드나 플레티넘 티어 정도였기 때문에 머리를 깨우는 겸 살짝씩 풀어보고 블로그에 해당 문제들을 리뷰해보고자 합니다! 👉🏻 2206번: 벽 부수고 이동하기☀️ 오늘의 문제from collections import dequedef bfs(n, m, grid): directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] visited = [[[False] * 2 for _ in range(m)] for _ in range(n)] # 3차원 방문 배열 queue = deque([(0, 0, 0, 1)]) # (x, y, ..

👉🏻 2294번: 동전 2n, k = map(int, input().split())money = [int(input()) for _ in range(n)]dp = [float('inf')] * (k+1)dp[0] = 0for i in range(1, k+1): for coin in money: if i - coin >= 0: dp[i] = min(dp[i], dp[i-coin] + 1)print(-1 if dp[k] == float('inf') else dp[k]) 🤔 왜 이렇게 풀었을까?전형적인 DP 문제입니다. 사실 처음에는 아래처럼 '거스름돈 문제다!!' 생각해서 냅다 그리디로 풀어봤는데, 당연하게도 시간이 초과했습니다.n, k = map(int, inpu..

👉🏻 24417번: 알고리즘 수업 - 피보나치 수 2mod = int(1e9) + 7n = int(input())ans = n-2prev, cur = 1, 1for _ in range(ans): nv = (prev + cur) % mod prev, cur = cur, nvprint(cur, ans)왜 이렇게 풀었을까?해당 문제는 제목만 봐도 파악할 수 있듯, 피보나치 수에 관한 내용을 다루고 있습니다. 피보나치 수를 알고리즘으로 구하기 위해서는 대표적으로 재귀, DP의 2가지 방법을 사용할 수 있는데, 문제에서는 두 개를 모두 요구하고 있습니다.fib(n) { if (n = 1 or n = 2) then return 1; # 코드1  else return (fib(n - 1..