혯의 코딩블로그

문제 링크 구름LEVEL 구름LEVEL 문제를 풀이하고 부족한 부분을 보완하며 실력을 키워보세요. 구름LEVEL은 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입 level.goorm.io 풀이 dy = [0, 0, -1, 1] dx = [-1, 1, 0, 0] def bomb_drop(N, bombs): land = [[0] * N for _ in range(N)] for bomb in bombs: y, x = bomb y -= 1 x -= 1 # 폭탄이 떨어진 위치 land[y][x] += 1 # 상하좌우 for i in range(4): ny, nx = y + dy[i], x + dx[i] if ny = N..

문제 링크 구름LEVEL 구름LEVEL 문제를 풀이하고 부족한 부분을 보완하며 실력을 키워보세요. 구름LEVEL은 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입 level.goorm.io 풀이 def max_events(schedule): schedule.sort(key=lambda x: x[1]) # 끝나는 시간을 기준으로 정렬 last_end_time = -1 count = 0 for event in schedule: if event[0] > last_end_time: # 이전 행사 종료 시간보다 시작 시간이 크면 (시간 겹치지 않음) count += 1 last_end_time = event[1] return count if __name__ ..

문제 링크 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 풀이 from collections import deque import sys def bfs(): visited = [-1]*(n_city+1) visited[1] = 0 # 수도: 1번 도시 queue = deque() queue.append(1) while queue: loc = queue.popleft() # 현 위치 for next_loc in road[loc]: # 갈 수 있는 곳 if visited[next_loc] == -1: visi..

문제 링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 1. 너비 우선 탐색(bfs) from sys import stdin from collections import deque def bfs(x, y, w, h, grid, visited): queue = deque([(x, y)]) visited[x][y] = True directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] while queue: c..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 from itertools import permutations # 수식 숫자와 연산자로 분리 def sep_num_op(expression): nums, ops = [], [] num = "" for s in expression: if s.isdigit(): # 숫자면 num += s else: # 연산자면 nums.append(num) num = "" ops.append(s) nums.append(num) return nums, ops # 주어진 숫자와 연산자를 사용해 우선순위에 따라 계산 ..

문제 링크 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 # 톱니바퀴 주어진 방향으로 회전시키기 def rotate_gears(gear, direction): if direction == 1: # 시계 방향 회전 return gear[-1] + gear[:-1] else: # 반시계 방향 회전 return gear[1:] + gear[0] # 톱니바퀴 회전시키고 최종 점수 계산 def solve(gears, rotations): for gear_num, direction in rotations: # ..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 # 올바른 괄호 문자열 확인 def is_correct(p: str) -> bool: stack = [] # 여는 괄호와 닫는 괄호 개수 일치, 열린 후 닫히면 올바름 for bracket in p: if bracket == '(': stack.append(bracket) elif stack: stack.pop() else: return False return not stack # 균형잡힌 괄호 문자열로 분리 def split_brackets(p: str) -> tuple: open_count..

문제 링크 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 from collections import deque # 주어진 나라들에서 연합 찾기 def find_union(board, n, l, r): dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] groups = [] visited = [[False for _ in range(n)] for _ in range(n)] # 모든 나라 순회, 연합 찾기 for x in range(n): for y in range(n): if..

문제 링크 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 # 입력받기 n = int(input()) arr = list(map(int, input().split())) # 주어진 배열에서 연속합 중 최댓값 반환 def max_continuous_sum(arr): dp = [0] * len(arr) dp[0] = arr[0] max_sum = dp[0] for i in range(1, len(arr)): dp[i] = max(dp[i-1] + arr[i], arr[i]) max_sum = max(max_sum, d..

문제 링크 Kth Smallest Element in a BST - LeetCode Can you solve this real interview question? Kth Smallest Element in a BST - Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. Example 1: [https://assets.leetco leetcode.com 풀이 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0..