one Book a Day

비트마스트 bfs. 외판원순회처럼dfs로 해보려다가 중대한 문제점을 발견했다. 내가 dfs return값, 메모이제이션 설계를 잘 못한다는 것이었다.. 특히 분기가 많아질수록.. 다음번엔 그거 보완해야겠다. 큰 깨달음을 얻은 문제. from collections import deque import sys input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def bfs(): while q: x, y, key, cnt = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

배열의 길이가 줄어듦에 따라 idx도 조정해줘야한다. import sys input = sys.stdin.readline N, K = map(int, input().split()) nums = [i for i in range(1, N + 1)] result = [] idx = 0 for _ in range(N): idx += K-1 if len(nums)

dp.. 그놈의 정사각형 import sys input = sys.stdin.readline N = int(input()) maps = [list(map(int,input().split())) for _ in range(N)] dp = [[0]*(N+1) for _ in range(N+1)] for i in range(1,N+1): for j in range(1,N+1): dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+maps[i-1][j-1] max_profit=dp[1][1] for k in range(N): for i in range(1,N-k+1): for j in range(1,N-k+1): cur_profit = dp[i+k][j+k]-dp[i-1][j+k]..

또상정렬. heap써서 완전한 위상정렬은 아니고 그냥 앞숫자부터 빼주는위상정렬. import sys input = sys.stdin.readline from heapq import heappop,heappush def topological_sort(): heap=[] for i in range(1,N+1): if not level[i]: heappush(heap,i) while heap: cur_solve = heappop(heap) answer.append(cur_solve) for next_solve in ordered[cur_solve]: level[next_solve] -=1 if not level[next_solve]: heappush(heap,next_solve) # 문제는 모두 풀어야한다. ..

코드는 한방에 짰는데 1갯수 확인하는 코드에서 노래수만큼이 아니라 기타수만큼 반복문돌려서 7번 틀렸다.. import sys input = sys.stdin.readline from itertools import combinations # 기타 플레이 리스트 이진수로 바꿔서 set에 저장. N,M = map(int,input().split()) guitars = set() for _ in range(N): name,pos = input().split() bin_change='' for chr in pos: if chr=="Y": bin_change += '1' else: bin_change += '0' guitars.add(int(bin_change,2)) # 셋에서 0 제거하고 비었으면 -1출력후 종료..

발전소 최솟값으로 키는 문제. 꺼져있으면 켜져있는 발전소중에 제일 싼 발전소로 선택해 키는게 상태값 최저가면 최신화. import sys input = sys.stdin.readline from collections import deque def make_electic(start,cur_cnt): queue = deque() dp[start] = 0 answer=float('inf') if target_cnt==0 or cur_cnt>=target_cnt: return 0 elif cur_cnt==0: return -1 else: queue.append([start,0]) while target_cnt > cur_cnt: # 한 순회에 하나씩 킬꺼임. circle_SIZE = len(queue) for ..

버튼을 누르면 5가지 방향에 대해 불이켜지고 꺼지는 버튼이 있다. 2열부터는 위쪽 열에만 켜져있는걸 꺼주는 식으로 진행해주면 되는데 1열처리가 문제이다.(각각 누르고 켜는 경우의수 2의 10승) 때문에 1열 경우의 수에 대해 비트마스크 처리를 해준다. 사실 그 외의 탐색은 10*10이어서 그리 오래걸리지 않기 때문에 1열 경우의수 탐색만 잘 처리해주면 통과한다. table = [] for i in range(10): temp = list(input()) for j in range(10): if temp[j] == 'O': temp[j] = True #True: 불 켜져있음 continue temp[j] = False #False: 불 꺼져있음 table.append(temp) # 5방탐색. dx = [-..

백트래킹의 설계문제이다. 실제 모든 경우의수를 각 인덱스마다 탐색하는 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