![]()
문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,..
문제 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접..
1. 브루트 포스(Brute-force) 문제를 해결하기 위해 가능한 모든 경우를 다 따지며 해를 찾는 간단하고 직관적인 알고리즘. 모든 가능한 해를 찾아내는데 유용하지만, 문제의 크기가 커질수록 실행시간이 급격하게 증가하고 효율성이 낮아서 대부분은 다른 최적화 기법이나 다른 알고리즘을 사용한다. 보통 다음과 같은 과정으로 이루어진다. 후보 생성 : 모든 가능한 후보 해를 생성한다. 후보 평가 : 후보들을 평가하여 주어진 조건에 부합하는지 확인한다. 적합한 해 선택 : 문제의 요구조건에 따라 최적의 후보 해를 선택한다. 예시) 백준 1182번 부분 수열의 합 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램..
🥰 Liked (좋았던 점) 혼자서 풀 수 있는 문제들이 점점 많아졌고, 문제를 풀기 전 간단하게 분석하고 어떻게 풀어야할지에 대해 접근방법이나 사용해야 하는 알고리즘에 대해 고민해 볼 수 있어서 좋았다. 😢 Lacked (아쉬웠던 점) 이분탐색이나 그래프, BFS, DFS는 아직 익숙하지 않아서 문제를 봐도 잘 모르겠다... 템플릿화 하면 금방 풀 수 있다고 하는데, 아직은 그만큼 이해가 쌓이지 않은 것 같다. 😮 Learned (배운 점) 기본적인 자료구조들인 스택, 큐, 덱, 힙, 해시 테이블에 대해서도 공부했고 어려워하던 이분탐색이나 DFS, BFS에 대해서도 여러가지 문제들을 풀어보면서 정리할 수 있어서 좋았다. 물론 아직 완벽하게 잘 쓸수 있거나 문제를 잘 풀수 있지는 않다. 그래도 이 문제는..
![]()
# 한번의 이동에서 옮길 수 있는 중량의 최댓값 # 이분탐색으로 중량의 범위와 최대값을 찾고 bfs로 가능한지 확인한다 from collections import deque import sys input = sys.stdin.readline def bfs(weight): # weight = 중간값(최대 중량) queue = deque() # 큐 queue.append(one) # 시작노드인 one부터 시작 visited = [False] * (n + 1) # 방문확인 visited[one] = True while queue: x = queue.popleft() for i, w in graph[x]: # 방문 가능한 섬들을 방문 if not visited[i] and w >= weight: # 미방문 & ..
![]()
# 요구사항 - 건물이 최소 몇개일지? # 스택에 암것도 없음 -> 높이를 스택에 넣기 # 스택에 넣어야 하는경우 - 아무것도 없을때. 현재높이 보다 더 높은 건물일때. # 스택에 안넣어야 하는 경우 - 높이가 같을때.(중복) # 스택에서 빼야하는 경우 - 높이가 낮아졌을때. 해당 건물이 끝났음. import sys input = sys.stdin.readline n = int(input()) building = 0 # 건물 개수 stack = [] # 스택 선언 for i in range(n): x, y = map(int, input().split()) while stack and stack[-1] > y: # 스택에 뭐가 있음 & 최근 높이가 현재 높이보다 더 큼 building += 1 # 건물 추..
![]()
# 최소비용 계산하기. 최소힙. from heapq import * import sys input = sys.stdin.readline t = int(input()) # 테스트 케이스 수 for _ in range(t): k = int(input()) # 장 수 nums = list(map(int, input().split())) # 파일 크기 heapify(nums) # 힙으로 변환 total = 0 # 총합 while len(nums) > 1: # 더이상 더할 수가 없을때까지 더함 x = heappop(nums) # 가장 작은 수 y = heappop(nums) # 그 다음 작은 수 total += x + y # 총합에 더해주고 힙에 다시 추가 heappush(nums, x + y) print(tot..
![]()
# 동생을 찾을 수 있는 가장 빠른 시간. => 최소 거리. BFS # 걷는다면 x-1/ x+1. 순간이동은 2*x. 시간은 모두 1초. # 큐에 뭔가 있다면 k인지 아닌지 확인 # 아니라면 이동방법만큼 반복. 이동했을때 인덱스 범위 내에 있어야하고 방문하지 않았어야함 # 걸린 시간을 visited에 추가하고 1초 추가 + 큐에 추가 from collections import deque n, k = map(int, input().split()) m = 10 ** 5 # 최대 범위 visited = [0] * (m + 1) # 방문 기록 def bfs(start): queue = deque([start]) # 큐에 현재 위치를 인큐 while deque: x = queue.popleft() # x = 현재..
![]()
# 나이트가 최소 몇번 움직여야 원하는 칸으로 이동할 수 있는지 -> bfs # 나이트가 이동할수있는방향 알기. from collections import deque t = int(input()) for _ in range(t): l = int(input()) # 체스판의 길이 now = list(map(int, input().split())) # 현재 위치 dest = list(map(int, input().split())) # 이동해야하는 위치 graph = [[0] * l for _ in range(l + 1)] # 체스판 visited = [[False] * l for _ in range(l + 1)] # 방문 확인할 배열 queue = deque() # 큐 선언 # 나이트가 이동할 수 있는 방향..
![]()
from collections import deque def bfs(x,y): q.append((x, y)) # 큐에 현재 좌표 추가 dx = [-1, 0, 1, 0] # 움직일 방향 dy = [0, 1, 0, -1] visited[x][y] = 1 # 현재 위치 기준. while q: # 큐가 비지 않았다면 x, y = q.popleft() # 첫번째값을 가져옴. for d in range(4): # 4방향으로 이동 nx = x + dx[d] ny = y + dy[d] # x, y가 범위를 벗어나지 않고, 같은 색이고, 아직 방문하지 않은 경우 if 0
