one Book a Day

실상 온풍기를 돌리고 영역의 온도를 확산시키고 그런것들은 어렵지 않았으나 벽에 대한 분기의 처리가 조금 까다로웠다. 바람 방향에 따라 갈수없는 영역이 정해진다. 갈 수 없는 영역 정보에 대해선 key-value로 접근하도록 해 check하고 초콜릿 101개 이상 못먹는다는 문장을 못봐서 3시간정도 낭비한듯.. 그거 한문장이 안보여서 K가 1000인데 어떻게 101분기만에 목표를 달성하는지 말이 안된다고 생각했다.. from collections import defaultdict, deque import sys input = sys.stdin.readline def spread_temperature(): for warmer in warmers: q = deque() x, y = warmer d = warm..

주사위 굴리기 1이랑 비슷합니다. 주사위 좌표이동, 방향에 따른 회전, 위치에 따른 좌표 값 * cnt 만큼 최종합에 더해줌. 주사위 밑면과 지도값 비교에 따라 방향성 수정 위의 4가지 로직으로 이루어져 있습니다. 사실 새로운 지도 배열을 만든 후 거기에 미리 위치마다 더해야 하는 값을 미리 연산해 두면 같은 위치마다 bfs를 돌지 않아도 되지만 통과됐으니 생략.. 아래가 직관적인 로직이라고 생각합니다. import sys input = sys.stdin.readline from collections import deque def rotate_dice(d): if d == 0: dice['top'], dice['left'], dice['bottom'], dice['right'] = dice['left']..

단순히 조건이 여러개 주어지는 걸 보고 교집합으로 풀려고 했다. 하지만 넓은 범위의 쿼리가 여려개 주어진다면 매번 교집합 연산을 해주어야 한다는 점에서 효율성이 부족했다. 오히려 상태조건이 4 * 3 * 3 * 3 으로 몇개 되지 않았기 때문에 dp로 배열을 만들거나 경우의 수에 따라 최초 배열에 삽입시켜 준 후 정렬하는게 약 3배정도 빨랐다. 조건이 적을 땐 모든 조건에 대해 입력해두는게 후에 쿼리를 수행함에 있어 유리한걸 잊지말자. 쿼리문제. 상태인자별로 미리 정리하자. 검색을 단순화 하자. 아래는 교집합 코드 그 아래 상태조사 코드 def solution(info, query): answer = [] lang_set = defaultdict(set) job_set = defaultdict(set) ..

최초 문자열 길이의 반까지 올려주면서 단위별로 탐색 def solution(s): n = len(s) answer = n for unit in range(1, n//2 + 1): cnt = 1 now = s[:unit] tmp_answer = '' for i in range(unit, n + unit, unit): if s[i:i + unit] == now: cnt += 1 else: if cnt > 1: tmp_answer += str(cnt) + now else: tmp_answer += now now = s[i:i + unit] cnt = 1 answer = min(answer, len(tmp_answer)) return answer

요구하는 순서대로 구현 def solution(p): if not p: return p n = len(p) left, right = 0, 0 for i in range(n): if p[i] == '(': left += 1 else: right += 1 if left == right: break u = p[:i+1] v = p[i+1:] stack = [] for char in u: if char == '(': stack.append(char) else: if stack: stack.pop() else: new_u = u[1:-1] tmp = '' for char in new_u: if char == '(': tmp += ')' else: tmp += '(' return '(' + solution(v) +..

0 - 1Knapsack Problem 쪼갤 수 없는 물건을 배낭에 담는문제로 DP로 풀어야하는 대표적인 문제 DP로 풀수 있는지 여부는 Principle of Optimality 성립 여부를 보면 된다. Principle of Optimality 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다 즉 부분사례의 최적해가 현 사례의 최적해의 부품이 된다면 DP로 풀 수 있다. 물건을 취하지 않고 P[i-1][j]를 선택하느냐 취하고 P[i-1][j-wk] + v[i]를 하느냐. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 13 13 2 0 0 0 0 8 8 13 13 3..

오름차순이면 ascending 반대면 descending 둘다 아니면 mixed arr = list(map(int, input().split())) pivot = [i for i in range(1, 9)] if arr == pivot: print('ascending') elif arr == pivot[::-1]: print('descending') else: print('mixed')

제곱 합의 나머지 print(sum(list(map(lambda x: int(x)**2, input().split()))) % 10)

분리집합 문제. union-find로 묶고 다른게 있으면 No 한집단이면 YES import sys input = sys.stdin.readline def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] N = int(input()) M = int(input()) edges = [list(map(int, input().split())) for _ in range(N)] plan = list(map(lambda x: int(x) - 1, input().split()..

뒤에서부터 역산. 크면 해당 값으로 작으면 현재값보다 큰 배수로.(몫 + 1) * 통과속도 import sys input = sys.stdin.readline n = int(input()) v = list(map(int, input().split())) answer = 0 for i in range(n-1, -1, -1): if answer