백준16 [백준 1012번] 유기농 배추 # 개강전 마지막 백준.. # 다음학기 알고리즘을 좀 더 배우게 되면 공부와 백준을 같이해보자! -- 정답코드 import sys sys.setrecursionlimit(10**6) T = int(sys.stdin.readline()) # 테스트 케이스의 개수 # 상하좌우가 붙어있는 그룹 count! # 재귀함수를 이용 def check_group(x, y): if x = M or y = N: return if [x,y] in cabbage: cabbage.remove([x,y]) else: return check_group(x + 1, y) check_group(x, y+1) check_group(x-1, y) check_group(x, y-1) for _ in ra.. 2022. 2. 27. [백준 11724번] 연결 요소의 개수 # 요즘 알바도 새로 시작하고 머신러닝 스터디도 진행하느라 너무 바빠 정말 오랜만에 백준 문제를 풀어보았다. # DFS, BFS를 사용한 알고리즘 문제 -- 정답 코드 # 연결 요소의 개수 import sys from collections import deque # 정점의 개수 N # 간선의 개수 M N, M = map(int, sys.stdin.readline().split()) gansun = {} for i in range(1, N+1): gansun[i] = set() for _ in range(M): a, b = map(int,sys.stdin.readline().split()) if a in gansun: gansun[a].add(b) else: gansun[a] = set([b]) if b .. 2022. 2. 7. [백준 1260번] DFS와 BFS # 화가난다... 정답 제출 형식을 제대로 파악하지 못해 2시간을 날렸다... # 계속 리스트 형식으로 제출했는데 구글링을 하고 보니 정답 제출 형식이 str ㅋㅋ.... # 2시간동안 dictionary를 잘못만든건지 DFS와 BFS 알고리즘을 잘못 짠건지만 고민했다 ㅠ -- 정답 코드 import sys from collections import deque # 정점의 개수 N # 간선의 개수 M # 탐색을 시작할 정점의 번호 V N, M, V = map(int, input().split()) gansun = {} for _ in range(M): a, b = map(int,sys.stdin.readline().split()) if a in gansun: gansun[a].add(b) else: gan.. 2022. 1. 23. [백준 2606번] 바이러스 - BFS, DFS # BFS와 DFS 알고리즘을 공부한 뒤 바로 예제문제를 풀어보았다. -- 처음 짠 코드 # bfs 방식 import sys from collections import deque n = int(input()) # 컴퓨터의 수 ssang = int(input()) # 연결되어 있는 컴퓨터 쌍의 수 network = {} # 네트워크를 저장할 딕셔너리 for i in range(ssang): a, b = map(int,sys.stdin.readline().split()) network[a] = network.get(a,[]) # 시작 : 끝 순서로 딕셔너리를 완성! network[a].append(b) for i in network.keys(): # bfs 알고리즘을 돌리기 위해 value type을 set.. 2022. 1. 22. [백준 2579번] 계단 오르기 - 동적 계획법 # 뭔가 복잡해보이는 문제들도 생각보다 동적 계획법 식으로 생각하면 쉽게 풀리는 경우가 많다! # 동적계획법으로 풀까?를 결정하는데까지의 시간을 줄이는 걸 목표로! # 점화식을 생각하는 법을 더 정교하고 빠르게 ! -- 정답 코드 # 계단 오르기 게임 # 계단을 밟으면 그 계단에 쓰여있는 점수를 얻게된다. # 계단은 한번에 한 계단 or 두 계단씩, 연속된 3개의 계단을 모두 밟으면 안됨, 마지막 계단은 반드시 밟아야됨 import sys n = int(input()) # 전체 계단의 개수 stairs = [0] * (n+1) # 시작점을 포함한 계단 for i in range(1, n+1): # 계단의 점수를 stairs에 기록 stairs[i] = int(sys.stdin.readline().stri.. 2022. 1. 16. [백준 1463번] 1로 만들기 - 동적 계획법 # 어렵다... 아이디어를 짜내려하는데 참 어렵다.. 처음 이 문제를 보고 풀이 방법을 생각해보는데 너무 복잡하여 마땅한 해결방법을 찾지 못했다. 따라서 일단은 작은 수부터 어떤식으로 1을 만들 수 있을지를 계산해 보았다. # 1 # 2 1 # 3 1 # 4 3 1, 4 2 1 # 5 4 2 1 ,5 4 3 1 # 6 2 1 # 7 6 2 1 # 8 4 2 1 # 9 3 1 # 10 9 3 1 # 11 10 9 3 1 # 12 4 2 1 # 13 12 4 2 1 # 14 7 6 2 1 # 15 5 4 2 1 # 16 8 4 2 1 # 17 16 8 4 2 1 # 17 16 15 5 4 2 1 이런 식으로 최소한의 경우로 1을 만들 수 있겠구나 하는 생각이 들었고 최대한 규칙을 찾아보았다. 1. 3의 제곱.. 2022. 1. 14. 이전 1 2 3 다음