one Book a Day

백트래킹의 설계문제이다. 실제 모든 경우의수를 각 인덱스마다 탐색하는 DFS방식이며 모든 check를 통과하며 result배열이 길이 N만큼 완성될경우 result에 담긴 숫자배열이 리턴되고 출력된다. import sys input = sys.stdin.readline #부호와 합이 일치하는지 확인하는 함수 일치하면 true 합과 일치하지 않으면False def ck(idx): hap = 0 for i in range(idx, -1, -1): hap += result[i] if hap == 0 and S[i][idx] != 0: return False elif hap = 0: return False elif hap > 0 and S[i][idx]

부분수열또한 선택과 비선택의 비트마스킹이 잘어울리는 문제이다. 단지 index를 확실히 해둬야 가져가고 안가져가고를 선택하는데 도움이 될 것이다. first, second라는 dp배열을 양쪽에 두어 dp배열간 합이 s에 일치하는경우 각 합이 되는 경우의 수를 cnt해 곱하는 식으로 답을 찾아나간다. import sys # 입력부 n,s = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) # 이분 분할 m = n//2 n = n - m # first : 왼쪽 Subset # 왼쪽의 경우의 수. first = [0] * (1

비트마스킹의 가장 대표유형인 TSP 노드들에 대해 0101010101느낌으로 방문여부를 판단한다. if before == (1i)%2 i번째 숫자가 켜져있는지 확인하는 연산. i번째 숫자가 0이어야 i번 당기고 2로 나눳을때 짝수가 나온다.이를통해 방문 안한 노드만 방문하도록 설계. tmp = find(i, before|(1

마찬가지로 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()) ..

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