one Book a Day

그 전단계에 비해 실제 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 # 일단 자기자신을 분할..

어떤 인자를 선택 하느냐 마느냐의 subset은 비트마스크로 풀수도, 가져가는 분기와 가져가지 않는 분기를 나누는 DFS로 모두 풀 수 있다. 이 풀이는 DFS풀이지만 비트마스크 공부 후 비트마스크로도 풀이에 도전할 것. from sys import stdin from collections import defaultdict def dfs(idx, end_idx, subtotal, direction): global answer # 종료 index에 왓을때 오른쪽에 진행되던 분기는 left 딕셔너리에 s-자기의 총합만큼의 left값이 있나 체크 후 그 숫자만큼 답에 더해주고 # 왼쪽은 총합만큼 딕셔너리에 기록해준다.(왼쪽과 오른쪽의 합이 s가 되는 만큼 answer에 더해진다.) if idx == end_i..

턴마다 상황이 바뀌는 시뮬레이션 문제다. 최근 큐빙이나 2048에 도전하면서 시뮬레이션을 좀 풀어봐야겠다 생각했는데 그래도 이건 그나마 쉬운편. 그냥 방향만 90도씩 돌려가며 점마다 새로 찍어주면 된다. 다찍으면 전꺼랑 합쳐서 다시 90도 돌리고 찍어준다. 시뮬레이션 문제가 체감상 많이 어렵게 느껴지니 앞으로 고난이도 알고리즘 습득보다 시뮬레이션이나 구현 및 기본기 문제들을 좀 더 다질 생각. import sys input = sys.stdin.readline dx = [1, 0, -1, 0] dy = [0, -1, 0, 1] n = int(input()) matrix = [[0 for _ in range(101)] for _ in range(101)] for i in range(n): x, y, d, ..

mid를 i로 나누면 i번째 행에서 나보다 작은 숫자의 갯수를 알 수 있다. 행의 최대갯수인N을 넘지 않도록 주의하며 나보다 작은 숫자의 갯수를 세준다. cnt값이 최종적으로 목표인 k와의 비교에 따라 점점 k에 수렴하도록 mid값을 조정해간다. import sys input = sys.stdin.readline N = int(input()) k = int(input()) start = 1 end = k # k번째의 '값'을 찾기위한 탐색. start와 end가 만나는 지점에 mid값이 k번째로 정렬된 수 이다. while start = k: answer = mid end = mid-1 else: start = mid+1 print(answer)

dp로 적당히 뒤집고 설계하니 풀렸다. -1, 3의 곱, 2의곱중 이동횟수가 작은값에 1더해서 저장 + 배열 저장. N = int(input()) dp = [[0,[]] for _ in range(N+1)] dp[1][0] = 0 dp[1][1] = [1] if N>1: for i in range(2,N+1): dp[i][0] = dp[i-1][0]+1 dp[i][1] = dp[i-1][1] + [i] if not i%3 and dp[i//3][0]+1 < dp[i][0]: dp[i][0] = dp[i//3][0]+1 dp[i][1] = dp[i//3][1]+[i] if not i%2 and dp[i//2][0]+1 < dp[i][0]: dp[i][0] = dp[i//2][0]+1 dp[i][1] = d..

결국 만들 수 있는 최고 가까운 수에서 target넘버의 차만큼에 리모컨을 눌러 만든 숫자 i의 길이만큼의 버튼 cnt를 더한값을 최소로 하게 설계하는 것. 최초 DFS로 설계했다가 재귀횟수 초과남. 프루트포스풀이. import sys input = sys.stdin.readline def can_push_num(num): num = list(str(num)) for i in num: if i in broken: return False return True target = int(input()) m = int(input()) broken = list(input().split()) min_push = abs(target - 100) for i in range(1000001): if can_push_num(..

결국 반복문으로 x나y를 증가시켜 일정 배수를 만드는게 목표이다. 변수가 나오면 항등식을 잘 세울 것. ==만 생각하는게 아니라 %로 일정 배수 만드는 경우도 유의할 것. def num(m, n, x, y): while x