one Book a Day

마찬가지로 N=26이지만 5개 확정시켜줘서 N=21인 비트마스킹 문제. 입력된 글자에대해 0001010101001 켜진 이진수를 tmp에 더해주고 배열에 저장해뒀다가 1,2,,8,16등 2의 배수가 저장된 배열에서 k개 뽑아낸 조합(2의 배수들은 알파뱃의 1,0켜지고 안켜지고를 나타낸다.) 조합의 합과 아까 저장해둔 필요알파뱃 비트합의 tmp값과 비교해 같으면 문자를 만들수 있는 알파뱃조합이라고 판명해 ct를 쌓는 방식으로 어떤 알파뱃 조합이 cnt가 가장 높은지(많은 문자열을 소화할 수 있는지) 판단하는 문제. from itertools import combinations n, k = map(int, input().split()) # 글자가 5개 미만이면 antic도 못배우니까 어떤 글자도 배울 수 없..

비트마스크 문제. 0~9까지의 숫자를 총 자릿수를 늘려가고 뒷자릿수에 따른 경우의수를 더해주며 dp진행합니다. 초깃값은 100000000, 010000000,00100000 ....000000001 시작값에 대해 불을 켜주고 경우의수 1을 더해주고 시작합니다. dp[x][y][z]에서 x는 비트숫자(불켜진 모든 경우의수), y는 자릿수(0:1자리), z는 마지막자리의 숫자. import sys input = sys.stdin.readline n = int(input()) # dp: 비트 정보, 자릿 수, 끝나는 수 dp = [[[0] * 10 for _ in range(101)] for _ in range(1

dp를 그리는데 구하라는대로 최대변의 길이를 구해주면 된다. 끊어지면 끊고 1부터 다시 시작하는 방식이고 가장 긴 길이를 저장한느 방식이다. 숫자는 위 왼쪽 그리고 대각 왼쪽 위가 모두 이어지는 그림이어야 dp[i][j]의 숫자가 올라가는 방식이다. import sys input = sys.stdin.readline while 1: N,M = map(int,input().split()) if N==0 and M==0: break square = [list(map(int,input().split())) for _ in range(N)] dp = [[0]*(M+1) for _ in range(N+1)] # 위 왼 대각 왼쪽 위가 0이면 1부터 다시 시작함. # 어디 하나라도 짧으면 그 길이가 최대길이로 저장..

S의 요소인 좌우값 사이에 자리를 찾고 N의 왼쪽 오른쪽의 경우의수를 계산하는 문제이다. import sys input = sys.stdin.readline from bisect import bisect L = int(input()) AB_list = list(map(int,input().split())) AB_list.sort() N = int(input()) if N < AB_list[0]: answer = max(0,(AB_list[0]-N)*(N)-1) else: index= bisect(AB_list,N) answer = max(0,(AB_list[index]-N)*(N-AB_list[index-1])-1) print(answer)

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()) ..

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