one Book a Day

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 배열돌리기 쓸데없이 귀찮지만 오늘 괜찮은 방법론을 배웠다. deque로 rotate시켜버리는 것. 따로 tmp를 안두어도 된다는게 너무 맘에 든다. import sys input = sys.stdin.readline from collections import deque def rotate_each(x,y,d,m): q = deque() for i in range(y-..

최소공배수 길이를 만들어 비교해줬다. 근데 다른 풀이보니까 그냥 상대 문자 길이만큼 곱해줘도 되더라..(꼭 최소가 아니라 그냥 공배수면됨) import sys input = sys.stdin.readline from math import gcd s = input().rstrip() t = input().rstrip() n = len(s) m = len(t) a = gcd(n,m) if s*(m//a) == t*(n//a): print(1) else: print(0)

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net K명 모두가 친구여야 통과하는 dfs를 짜주면 된다. import sys input = sys.stdin.readline def dfs(v,arr): if len(arr)==K: for num in arr: print(num) exit() for i in range(v+1,N+1): if not visited[i]: for num in arr: if num not in graph[i]: break el..

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])