one Book a Day

2를 탐색해준후 BFS로 거리에따른 숫자 기록을 진행해줬다. 처음엔 2방으로 했었는데 하고보니 막혀있는 구간에서 사방 탐색이 필요해서 사방으로 바꿔줬다 import sys input = sys.stdin.readline from collections import deque def BFS(i,j): global dp_dists queue = deque() queue.append([i,j]) dp_dists[i][j] = 0 while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0

처음엔 네크워킹만 보고 MST생각해서 바로 크루스칼로 풀었는데 틀렸다. "복구 전보다 모든 컴퓨터에 대해 전송시간이 짧아야한다" 이걸 맵 전체로 해석했기 때문인데 사실은 모든 노드에 대해 최소 거리를 가져야 한다는 말이다. import sys input = sys.stdin.readline def find(x): if parents[x]==x: return x parents[x] = find(parents[x]) return parents[x] def union(a,b): a = find(a) b = find(b) if a>b: parents[a] = b else: parents[b] = a # N개의 컴퓨터 네트워크. # 회선은 성능차이가 있음. N,M = map(int,input().split()) ..

실버1문제치고 N이 1e15에 최대 1e18까지가서 당황. 이분탐색해보려다 메모리 초과났다. import sys input = sys.stdin.readline from collections import deque def buy_flower(optimal_cost): global min_cost queue = deque() start_price = 0 flower = 0 queue.append([start_price,flower]) while queue: cur_price,flower = queue.popleft() for flo_cnt,flo_cost in ((A,B),(C,D)): if cur_price + flo_cost =N: if cur_price + flo_cost < min_cost: min..

비트마스크(bit mask) 비크마스크란 무엇인가? 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술. 집합에서 하나의 원소는 하나의 bit로 표현(꺼져있다, 켜져있다.) ex switch_states = [True, False, False, True, True, False, False, False, True, True] switch_states = 0b1001100011 # 611, python에서는 앞에 &#39;0b&#39;를 붙여 이진수 표현 가능 정수형으로 표현하면 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 더 작은 메모리의 사용. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함. (중요) 위와같은 장점이 ..

사이클 찾기. 오랜만에 사이클 찾기 풀었다. 사이클이 여러개 있을 수 있는 경우. import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) def find_cycle(cur_node): global cnt check_cycle[cur_node] = True cycle_stack.append(cur_node) next_node = choices[cur_node] if not check_cycle[next_node]: find_cycle(next_node) else: if next_node in cycle_stack: cnt -= len(cycle_stack[cycle_stack.index(next_node):]) # 프로젝트 팀원 수 제한 ..

시뮬레이션 구현문제로 난이도는 어렵지 않은 편. 이분탐색으로 풀었지만 사실 그냥 while문 돌려도 풀린다. import sys input = sys.stdin.readline def is_clearDungeon(Max_hp, H_atk): cur_hp = Max_hp for room in dungeon: command,atk,health = room[0],room[1],room[2] if command==1: if health%H_atk==0: cur_hp -= ((health//H_atk)-1)*atk else: cur_hp -= (health//H_atk)*atk if cur_hp

그 전단계에 비해 실제 LIS 리스트 까지 뽑아내야 하는 문제이다. 전 문제는 LIS길이만을 측정하기에 배열 순서 상관없이 이분탐색으로 자기위치에 삽입, 계속 LIS배열을 초기화 새롭게 덮어씌우는 방법으로 길이를 측정했지만 이번문제는 temp배열에 삽입되는 모든 인자를 인덱스값과 인자를 묶어 전부 삽입해준 후 재검사를 통해 queue에 들어간 배열과 temp에 들어간 인덱스값을 비교해 동일하면 temp에서 그 값을 ans에 넣어주는 방식이다. 즉 이분탐색으로queue에서 index값을 관리하고 temp에서 그 값에 일치하는 x값들을 모두 관리하는 방식. import sys from bisect import bisect_left input = sys.stdin.readline n=int(input()) a..

온전하게 BFS를 순서까지 맞춰서 검사하는 방법에는 무엇이 있을까? 실제 BFS를 돌려 그 순서를 기록하는 방법? 노드 순회 순서에따라서 천차만별일 것이다. 그럼 레벨을 정해 레벨단위로 추적하는 방법? 레벨3이 레벨2인 어떤 노드에서 큐에 삽입됐는지까지 추적하지 않는다면 완벽한 검사는 불가능하다. 하지만 아래 코드는 완벽하게 검사해야하는 리스트를 실제 BFS의 작동방식처럼 num이 기존의 queue에 삽입된 노드로부터 왔는지를 순서대로 검사한다. 만약 순서가 잘못되어잇다면 레벨상 맞더라도 완벽하게 검열당한다. BFS는 단순히 레벨 0에서 갈수있는 레벨 1들을 정하고 레벨2들을 정해 검사하는 방식이 아니라 큐를 이용하는 FIFO의 검사방식이라는걸 늘 명심해야 할 것이다. 내일은 DFS스페셜 저지를 풀예정인..

퀸은 열, 행, 대각의 검사를 통해 있으면 다음검사로 넘어가고 없으면 퀸을 일단 놓고 진행하는 방식이다. dfs를 통해 퀸의 갯수가 행의 갯수만큼 놓이면 검사를 결과의 횟수를 하나 추가해주고 dfs의 순회는 매행 1~n번 열의 칸이고 칸을 옮길때마다 isTrue를 통해 checkrow로는 같은 열상에 퀸이 존재하나를 체크, 1~x까지 그동안 순회했던 행들의 인덱스를 통해 대각선 검증까지 해준다. import sys input = sys.stdin.readline n = int(input()) check_row = [0 for _ in range(16)] result = 0 # 진입한 cnt값의 check[cnt]값은 지금 검사하는 열의 번호. # 이 열에 check_row[i]즉 같은 열에 퀸이있거나 #..

result는 문자열의 i번쨰까지 펠린드롭 최소분할의 갯수를 저장해 이어오는 dp이다. dp[i][j]는 i에서 j까지 문자열이 펠린드롬일때 1값을 가진다. 솔직히 펠린드롬 검사하는 방법수도 한번 싹다 정리해야할듯 싶다. 결국 기준을 중심으로 좌우를 검사하는 방법 또는 기준을 중심으로 한방향으로 일정크기만큼 늘려가며 검사하는 방법인데 인덱스가 많이 헷깔린다. import sys input = sys.stdin.readline strings = input().rstrip() n = len(strings) dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)] result = [float('inf')] * (n+1) result[0] = 0 # 일단 자기자신을 분할..