one Book a Day

xor로 다른거 찾은 다음 1이랑 0 갯수 세서 옮기거나 더해줌 import sys input = sys.stdin.readline for _ in range(int(input())): N, M = map(lambda x: int(x,2), input().split()) xor = N^M n = len(bin(xor)[2:]) one = 0 zero = 0 answer = 0 for i in range(n): if xor & 1

편집거리 알고리즘 두 문자열의 유사도를 판단하는 알고리즘 유사도란? 어떤 문자열을 삽입, 삭제, 변경을 몇 번 해서 동일하게 바꿀 수 있는지의 최솟값. LCS와 같이 2차원 배열을 통해 문자열을 하나씩 비교. 최초는 공집합과 비교해 문자열 길이만큼 1씩 카운트를 준다(공집합에서 그 문자열이 되려면 열마나 삽입되어야 하는가?) 두 문자를 비교해 추가, 삭제, 변경의 소요마다 1씩 카운트. A[i]==B[j]일 때 편집거리 D(i,j) = D(i-1,j-1) 같은 문자가 나왔을 때는 대각선 왼쪽 위의 값을 가져온다. A[i]!=B[j] 면 D(i,j) = min(D(i-1,j),D(i,j-1),D(i-1,j-1)) + 1 즉 수정, 삽입, 삭제를 한 편집거리중 최소값을 가져온다. def editDistanc..

세번째 푼다. 솔직히 이젠 쉬운듯. 중복 탐색은 조금 존재한다. import sys input = sys.stdin.readline def dfs(x,y,depth,s,init_x,init_y): global max_sum if depth==4: max_sum = max(max_sum,s) return for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

hash map import sys input = sys.stdin.readline N, M = map(int, input().split()) dic = {} for _ in range(N): adress, pw = input().split() dic[adress] = pw for _ in range(M): print(dic[input().rstrip()])

bfs로 나머지값보다 작고 첫번째 가능한 제곱수값과 나머지의 차이보다 큰 제곱수들만 조사하는 방식. 좋은걸 깨달았다. bfs의 종료조건은 무조건 위보다 아래가 좋다는 것을.. 아래에 하고 return해야 한분기 덜 돈다. import sys input = sys.stdin.readline from collections import deque def bfs(n): q = deque() q.append((n,0)) visited[n] = True while q: r, cnt = q.popleft() flag = 1 for square in squares: next_r = r-square if next_r > 0 and not visited[next_r]: if flag: first = next_r flag ..

portal만들고 중복체크만해줌. import sys input = sys.stdin.readline from collections import deque def bfs(start): q = deque() q.append((start,0)) visited[start] = True while q: cur_node, cnt = q.popleft() for i in range(1,7): next_node = cur_node+i if next_node >= 100: return cnt+1 if visited[next_node]: continue visited[next_node] = True if next_node in port: if not visited[port[next_node]]: visited[port[..

평범한 구간합과 쿼리 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) dp = [0] for i in range(N): dp.append(dp[i]+arr[i]) for _ in range(M): i, j = map(int, input().split()) print(dp[j] - dp[i-1])

방에 들어갔다 나왔다. def solution(enter, leave): n = len(enter) answer = [0] * (n+1) enter_idx = 0 leave_idx = 0 room = set() while leave_idx < n: if leave[leave_idx] in room: room.discard(leave[leave_idx]) leave_idx += 1 continue if enter[enter_idx] not in room: for man in room: answer[man] += 1 answer[enter[enter_idx]] = len(room) room.add(enter[enter_idx]) enter_idx += 1 return answer[1:]

dfs로 쭉 파고들면서 check def dfs(v): for i in range(n): if visited[i] == 0 and matrix[v][i] == 1: visited[i] = 1 dfs(i) n = int(input()) matrix = [list(map(int, input().split())) for _ in range(n)] for i in range(n): visited = [0 for _ in range(n)] dfs(i) print(*visited)

말 그대로 절댓값 힙 import sys input = sys.stdin.readline from heapq import heappop,heappush N = int(input()) arr = [] for _ in range(N): x = int(input()) if x: heappush(arr,(abs(x),x)) continue try: print(heappop(arr)[1]) except: print(0)