aeightchill

[백준] 27961. 고양이는 많을수록 좋다 / 브론즈1코드 변수 정의cnt : 연산 횟수madoka_cat : 현재 고양이 수Greedy시간복잡도 : O(logN)def f(): N = int(input()) cnt, madoka_cat = 0, 0 # 연산 횟수(cnt)와 현재 고양이 수(madoka_cat) 초기화 while madoka_cat    풀이 방식 고양이 수를 증가시키는 과정에서 최소한의 연산 횟수를 찾는 문제로, 고양이 수 madoka_cat은 두 가지 방법으로 증가할 수 있다.생성 마법    →     +1 연산복제 마법    →     x2 연산마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다.0마리 이상 k마리 이하의 고양이를 추가할 수 있으므로..

[백준] 15686. 치킨 배달 / 골드5코드 변수 정의chickens : 치킨집 좌표 리스트houses : 집 좌표 리스트min_dist : 최종 반환할 최소 치킨 거리total_dist : 치킨집 조합별 총 치킨 거리house_to_chicken : 현재 집의 치킨 거리Brute Force시간복잡도 : O(C(13,M)×(H×M))≈O(10^6)from itertools import combinationsdef chicken(): N, M = map(int, input().split()) # 도시 크기 NxN, 선택할 치킨집 개수 M board = [list(map(int, input().split())) for _ in range(N)] # 도시 정보 입력 # 치킨집과 집의 좌표 ..

[백준] 2615. 오목 / 실버1코드 변수 정의function : checkcnt : 연속된 같은 바둑알의 개수ax, ay : 가장 왼쪽에 위치한 바둑알의 좌표function : fdirections : 탐색할 4가지 방향is_valid : 5개의 같은 바둑알이 연속되어 있는지 확인x, y : 5개의 같은 바둑알이 연속되어 있는 경우, 해당 바둑알 중 가장 왼쪽에 있는 위치Brute Force시간복잡도 : O(6000)    * 최대# 5개의 같은 바둑돌이 연속되는지 확인하는 함수def check(board, i, j, d1, d2): cnt, ax, ay = 1, i, j # 현재 돌 포함, 초기 위치 저장 # 주어진 방향 (d1, d2)으로 이동하면서 같은 돌인지 확인 for dx..

[백준] 2529. 부등호 / 실버1코드 변수 정의depth : 현재 선택한 숫자의 개수를 의미하며, k+1개가 되면 종료num_list : 현재까지 선택한 숫자들을 저장한 리스트min_num, max_num : 반환할 숫자num_to_str : 리스트를 문자열로 변환한 값visited : 숫자 사용 여부 표시Backtracking시간복잡도 : O(10!)       *최대 탐색 경우# x, y가 부등호를 만족하는지 확인하는 함수def is_valid(x, y, sign): return (sign == '' and x > y)# 부등호 조건을 만족하는 최댓값과 최솟값을 찾는 함수def search(k, inequal): # 백트래킹을 이용한 숫자 조합 탐색 def backtrack(dep..

[백준] 1051. 숫자 정사각형 / 실버3코드 변수 정의min(N, M) : 만들 수 있는 정사각형 한 변의 최대 길이Brute Force시간복잡도 : O(N x M x min(N, M))             *최악의 경우def f(): N, M = map(int, input().split()) board = [input() for _ in range(N)] for s in range(min(N, M), 1, -1): # 주어진 보드로 만들 수 있는 모든 정사각형의 한변의 길이 for i in range(N - s + 1): for j in range(M - s + 1): # 정사각형 4개 모서리가 모두 같은 값을 갖는 경우 ..

[백준] 1018. 체스판 다시 칠하기 / 실버4코드 변수 정의function : check_patternpattern1, pattern2 : 체스판의 시작이 W인 패턴, 체스판의 시작이 B인 패턴replace1 : pattern1인 체스판인 경우 다시 칠해야 하는 칸의 수replace2 : pattern2인 체스판인 경우 다시 칠해야 하는 칸의 수function : fcompare_board : 주어진 보드에서 잘라낸 8X8 체스판min_ans : 체스판에서 다시 칠해야 하는 정사각형의 최소 개수Brute Force시간복잡도 : O(NXM)def check_pattern(board): pattern1 = ['WBWBWBWB', 'BWBWBWBW'] * 4 # 시작이 W인 패턴 pattern..

[백준] 2573. 빙산 / 골드4코드 변수 정의function : melt_icebergnew_graph : 녹은 후의 빙산 상태 그래프 생성을 위한 리스트directions : 상하좌우 탐색을 하기 위한 배열sea_cnt : 빙산에 인접한 바다의 개수function : count_icebergiceberg_cnt : 빙산 덩어리 개수function : maingraph : 현재 빙산 상태day : 경과 일수max_day : 무한 루프 방지용 최대 일수BFS시간복잡도 : O(N x M)from collections import deque# 현재 그래프 빙산 상태에서 녹은 후의 그래프를 반환하는 함수def melt_iceberg(graph, N, M): # 새로운 빙산 상태를 저장할 리스트 초기화 ..

[백준] 1707. 이분 그래프 / 골드4코드 변수 정의graph : 인접 리스트 그래프colors : 정점 색상 표시 배열results : 이분 그래프이면 YES, 아니면 NOBFS시간복잡도 : O(k * (V + E))from collections import deque# 이분 그래프인지 확인하는 함수def is_bipartite_graph(V, E, edges): # 그래프 초기화 graph = [[] for _ in range(V + 1)] for u, v in edges: graph[u].append(v) graph[v].append(u) # 색상 표시 배열 (0: 미방문, 1: 검정, -1: 흰색) colors = [0] * (V+1) ..

[백준] 2667. 단지번호붙이기 / 실버1코드 변수 정의graph : 아파트(1)가 표시된 지도cnt : 현재 단지 내 아파트 수dx, dy : 상하좌우를 탐색할 변수. 상(-1, 0), 하(1,0), 좌(0,-1), 우(0,1)nx, ny : 현재 위치에서 상하좌우로 이동했을 때의 좌표apartment : 각 단지의 아파트 수를 저장할 리스트BFS시간복잡도 : O(N^2)from collections import deque# BFS를 이용하여 연결된 아파트 단지의 크기를 계산하는 함수def bfs(graph, i, j, visited): q = deque([(i, j)]) # 큐에 시작 좌표(i, j)를 추가 cnt = 1 # 현재 단지 내 아파트 수 (초기값=1, 시작점 포함) wh..

[백준] 1697. 숨바꼭질 / 실버1코드 변수 정의x, time : 현재 위치, 현재 위치까지 오는 데 걸리는 시간ans : 수빈이가 동생을 찾을 수 있는 가장 빠른 시간BFS시간복잡도 : O(N)  *N=100001 (문제에서 위치 최대 값+1)from collections import deque# bfs 함수 : N에서 K로 이동하는 최소 시간을 계산def bfs(N, K, time): # 큐를 생성하고 초기 위치와 시간(time=0)을 삽입 q = deque() q.append((N, time)) # 위치 x를 방문했는지 방문 여부 기록 visited = [False] * 100001 # 최소 시간 변수 (초기값=무한대) ans = float('inf') ..