이모저모

0. 문제 1. 손정리 2. 코드 import sys # 준비 # 집의 수와 공유기 개수 받아오기 n, c = map(int, sys.stdin.readline().split()) # 집들의 x 좌표값 받기 locations = [] for _ in range(n): location = int(sys.stdin.readline()) locations.append(location) # 집의 좌표 오름차순 정렬 locations.sort() # 가장 인접한 공유기 간의 거리가 주어졌을 때 몇 개의 집까지 설치할 수 있는지 세 주는 함수 def how_many(min_dis): recent = locations[0] count = 1 for i in range(1, n): cur = locations[i] d..

문제: https://leetcode.com/problems/search-a-2d-matrix-ii/ 오늘의 진도였던 이진탐색! 그래서 이 문제도 이진 탐색으로 풀어보았다. 각 행과 열을 이진탐색해가는 방식이다. 그런데 풀고나서 책을 봤는데 이진탐색이 아닌 다른 방식의 풀이를 추천해주었다. 정리하면, 이 문제에 대해 (1) 이진탐색으로 풀이 (2) 첫행의 맨 뒤에서 탐색 (3) 파이썬다운 방식 이런 접근들이 가능하다. 미리 말하자면 직접 리트코드에서 돌려본 실행시간은 (1) : 136ms (2): 243ms (3): 124ms 와 같았다. 아직 궁금한 점은, 왜 나는 리트코드에서 돌릴 때 (2)방법이 오래 걸렸을까? 새로 느낀 점은 파이썬다운 방식에서 사용한 any()함수는 강력하다는 것! 1. 이진탐색..

문제 중위표기식(연산자가 피연산자 사이에 위치하는 것 - 일상에서 사람들이 사용하는 방식)을, 후위표기식(연산자가 피연산자 뒤에 위치해서 왼쪽부터 순서대로 계산할 수 있는 방식 - 컴퓨터에게 표현해줄 수 있는 방식)으로 바꾸기 infix = "3+5*2/(7-2)" stack = [] res = '' for x in infix: # 피연산자(10진수 숫자)라면 바로 결과물에 넣어준다. if x.isdecimal(): res += x else: if x == '(': stack.append(x) elif x == '*' or x == '/': # * 나 / 보다 우선순위가 높은 것을 꺼낼 것인데, 먼저 들어간 * 이나 / 이 해당 while stack and (stack[-1]=='*') or (stack..

아마 이 문제는 top-down방식(재귀사용)으로도 풀 수 있을 것 같다. 그런데, 지금의 나는 bottom-up이 재귀보다는 착하게(?) 느껴져서 일단 bottom-up으로 풀었다ㅎㅎ 재귀로도 시도해봐야지 다음에. 0. 문제 1. 손 계획 2. 코드 def solution(triangle): # 자주 사용할 숫자 변수로 n = len(triangle) # 각 칸에 이르면서 만들 수 있는 최대합을 기록할 다이나믹 배열 준비 dy = [] for i in range(n): row = [0] * (i+1) dy.append(row) # 작고 확실한 시작점 dy[0][0] = triangle[0][0] for j in range(1, n): for k in range(j+1): if k == 0: dy[j][..

0. 문제 1. 손 계획 2. 코드 import collections import heapq def solution(priorities, location): # 타겟 location 의 문서가 몇 번만에 출력되었는지 count 해가는 변수 answer = 0 # 입력 순서를 지키고 있는 데큐 q1 = collections.deque() # 우선순위 높은 것을 꺼내기 위한 heapq 로 사용할 리스트 q2 = [] # 입력된 우선순위들을 두 개의 큐에 넣어준다. 단 우선순위는 부호반전하여 넣는다. (최대힙처럼 사용하기 위해) for i, priority in enumerate(priorities): doc = (-priority, i) q1.append(doc) heapq.heappush(q2, doc) ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr import heapq def solution(scoville, K): answer = 0 # 작은 값부터 뽑을 것이므로 heap 사용할 것. heap = [] # 이미 최솟값이 K 보다 크거나 같다면 섞어볼 필요 없어서 0회를 return if min(scoville) >= K: return 0 # 최소힙을 지원하는 파이썬 heapq 를..