one Book a Day

dp 누적으로 최소값 구해줬습니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(N)] dp = [[[0,0,0] for _ in range(M)]] + [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N)] for i in range(1,N+1): for j in range(M): if j < M-1: dp[i][j][0] = min(dp[i-1][j+1][1],dp[i-1][j+1][2]) + matrix[i-1][j] if 0 <..

처음에 그냥 matrix에 넣었다가 시간초과나고 합연산은 한번에 하는걸로 코드 수정. 통과 import sys input = sys.stdin.readline for test in range(int(input())): N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] ans = [[] for _ in range(2)] for i in range(N): ans[0].append(sum(matrix[i])) for i in range(N): ans[1].append(sum(matrix[m][i] for m in range(N))) for _ in range(M): r1,c1,r2,c2,v = ma..

자바의 main() 메서드 Java 프로그램은 특정 순서로 실행되는 Java 명령의 시퀀스기 때문에 시작과 끝이 있다. Java 프로그램을 실행하려면 JVM에 프로그램 실행을 시작할 위치를 신호해야한다. Java의 모든 명령어(코드)는 Java 클래스 내에 위치해야한다. 클래스는 함께 속한 데이터와 명령어를 그룹화하는 방법이다. 따라서 클래스는 변수와 메서드를 모두 포함 할 수 있다. 변수는 데이터를 포함할 수 있으며, 메서드는 데이터에 대한 작업 집합(명령어)을 함께 그룹화한다. 자바 클래스 선언 Java 코드는 클래스와 동일한 파일 이름을 가진 파일에 있어야하며 파일 접미사로 끝나야한다. 즉 파일이 클래스 이름과 일치하는 파일에 있어야 Java SDK의 Java 컴파일러 또는 Java IDE 내부에서..

각 value, cnt를 축으로 둔 2차원 dp를 통해 하나씩 고르는 경우의 수를 check해주었습니다. 이전에 수확한게 왼쪽인지 오른쪽인지 각각 수확량의 최댓값을 취하며 계산해 주었습니다. import sys input = sys.stdin.readline N = int(input()) v = [0]+[int(input()) for _ in range(N)] dp = [[v[i] * N if i == j else 0 for i in range(N + 1)] for j in range(N + 1)] for left in range(1, N + 1): for right in range(left - 1, 0, -1): dp[right][left] = max(dp[right + 1][left] + v[righ..

라인 스위핑. 큰걸 기준으로 작은걸 감싸냐 안감싸냐 왼쪽이 겹치면 재귀로 오른쪽 이 겹쳐지는 원이 나올때까지 재귀(큰 원 안에 원이 몇개 겹치나 조사하기 위함) import sys from bisect import bisect_left input = sys.stdin.readline sys.setrecursionlimit(400000) def next_circle(cur_c,next_c): global cnt if circles[cur_c][1] == circles[next_c][1]: cnt += 1 return tmp = bisect_left(circles,(circles[next_c][1],)) if tmp == len(circles): return if circles[tmp][0]==circles..

코드는 한방에 짰는데 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출력후 종료..

LRU cache O(1) 캐시는 불필요한 통신을 줄이고 기민한 UX를 제공 DB과부하를 막음.(query결과 저장) Proxy, CDN(유저와 가까운 CDN node) 메모이제이션 OrderedDict이용 from collections import OrderedDict MAX_SIZE = 2 cache = OrderedDict() def get_user(user_id): if user_id in cache: cache.move_to_end(user_id) return cache[user_id] if len(cache) == MAX_SIZE: cache.popitem(last=False) cache[user_id] = fetch_user(user_id) return cache[user_id] last=F..

hashmap에 tuple로 조합수를 구하는 것까지는 접근했는데 set으로 압축시키는 것은 생각을 못했음. 이러면 결국 tuple에 각 순위값이 들어가게 되는데 동일한 요소의 경우 묶여서 사라지기때문에 순위값의 갯수가 적어져 일일히 비교할 필요가 없어짐. 정렬과 indexing을 같이 사용해서 크기 비교를 해야할 때 유용하게 쓸 수 있을 것으로 보임 import sys input = sys.stdin.readline from collections import defaultdict m, n = map(int, input().split()) universe = defaultdict(int) for _ in range(m): planets = list(map(int, input().split())) keys ..

3. events const searchInput = document.querySelector(".search"); const suggestions = document.querySelector(".suggestions"); searchInput.addEventListener("change", displayMatches); searchInput.addEventListener("keyup", displayMatches); search클래스를 가진 input box가 변하거나 key가 눌릴때마다 displayMatches를 불러옵니다. keyup은 키보드를 이용한 입력만 감지함. (마우스 클릭으로 붙혀넣기하거나 자동완성 단어를 클릭해서 입력되는 이벤트 인식x) change는 외부를 눌렀을때만 인지함. 키보드 ..

적힌 숫자가 중복 없이 1씩 늘어나기 때문에 배열에 index로 쓸 수 있습니다. 그 후 index에 따라 이동 가능여부를 조사해주면 됩니다. 올해 하반기 라인 코테 3번 문제와 아이디어가 비슷합니다. for test in range(1, int(input()) + 1): N = int(input()) dp = [0] * (N ** 2 + 1) for i in range(N): row = list(map(int, input().split())) for j in range(N): dp[row[j]] = (i, j) delta = ((0, 1), (1, 0), (0, -1), (-1, 0)) max_length, cnt, start, answer = 1, 1, 1, 1 for num in range(1, l..

기본적으로 문자열을 쌓거나 줄이는 방법은 dfs가 기본이다. 1번풀이 : 하나씩 쌓는 방법 left, right로 하나씩 쌓아가며 이어붙힌다. 다 붙히면 중복 없어지고 종료 import sys input = sys.stdin.readline def dfs(left, right, string): if len(string) == target: answers.add(string) return if left > 0: dfs(left - 1, right, string + N[left - 1:right + 1]) if right < n: dfs(left, right + 1, string + N[left: right + 2]) N = input().rstrip() n = len(N) target = n * (n + ..

set으로 중복체크. import sys input = sys.stdin.readline while 1: try: N, M = map(int, input().split()) except: break ans = 0 for num in range(N,M+1): cnt = set() s_num = str(num) for char in s_num: cnt.add(char) if len(s_num) == len(cnt): ans += 1 print(ans)

Tree DP subtree에서 구한 해를 이용해 전체 트리의 해를 구하는 방식으로 진행이 됨. dp[i] = i를 루트로 하는 서브 트리의 ~같은 식으로 DP Table을 정의. dp는 보통 선형구조에서 이루어지지만 tree는 비선형 구조기 때문에 탐색 순서를 미리 정해주는게 일반적이다. / 그래프에서 우리가 dp를 사용하듯 트리도 dp를 사용하기 충분. 탐색 순서는 보통 dfs를 돌면서 나오는 트리인 dfs트리를 기준으로 한다. 트리 dp도 대부분 상태 dp가 들어간다. ex.) dp/[i]/[j] = i는 i를 루트로하는 subtree에서 i의 상태가 j일때. 보통 i번째 노드를 루트로 하는 서브트리에서 i번째 루트 노드를 포함했을 때와 포함 하지 않았을 떄 조건 중 최적값을 가져온다. 기본 구조 ..

CPU Scheduling 스케줄링 실행준비가 된 프로세스 중에서 하나를 선택해 CPU를 할당 하는 것. 결국 CPU를 잘 사용하기 위해 프로세스를 잘 배정하기 위함. 조건 : 오버헤드는 낮고, 사용률은 높고, 기아 현상은 낮을때. 목표 Batch System : 가능하면 많은 일을 수행한다. 시간(time)보다 처리량(throughout)이 중요하다. Interactive System : 빠른 응답 시간, 적은 대기 시간 Real-time System : 기한(deadline) 맞추기 선점 / 비선점 스케줄링 선점(preemptive) : OS가 CPU의 사용권을 선점 할 수 있는 경우, 강제 회수하는 경우 비선점(nonpreemptive) : 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행..

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(O(NlogN)) 아래는 2261번 문제에 대한 분할정복 풀이. import sys input=sys.stdin.readline INF=sys.maxsize # 두 점 사이의 거리를 구하는 함수 def dist(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2 def divide(start,end): # 점 하나면 버림 if start==end: return INF # 점 두개면 거리구해서 리턴 elif end-start==1: retur..

부동소수점에 대한 이해 : https://thrillfighter.tistory.com/349 Python의 부동소수점 보정 decimal 모듈 : https://docs.python.org/ko/3/library/decimal.html import decimal # 천자리까지 정확도 주기 decimal.getcontext().prec = 1000 N = int(input()) for _ in range(N): # Decimal 객체를 만듬.(float, int같은) # 자릿수 10자리까지 정확하게 입력해줌. d = decimal.Decimal(input().rstrip() + '.0000000000') pow = decimal.Decimal('1') / decimal.Decimal('3') d = de..

checking을 어떻게 할것이냐? 그날 이떡을 먹었었다. 에 대한 체킹. 먹었었다면 굳이 다시 먹을 필요 없다. import sys input = sys.stdin.readline def DFS(cnt,dduks,yesterday): global answer if cnt == N: for d in dduks: print(d) exit() for dduk in days[cnt]: if dduk != yesterday and not ate[cnt][dduk-1]: ate[cnt][dduk-1] = True DFS(cnt+1, dduks + [dduk],dduk) N = int(input()) days = [] answer = [] for _ in range(N): m,*dduk = map(int, inpu..

디자인 패턴(객체를 어떻게 구성할 것인가?) 이름의 중요성 디자인 패턴 이전에는 명칭이 없어서 같은 내용의 구조를 서로에게 설명해주기위해 수십시간을 낭비. 이름이 곧 개념을 정의한다 디자인 패턴도 이런 자주 사용되는 개념에 이름을 정의한 것. *비슷한 문제 상황을 해결했던 해결책을 잘 기억하고 다시 적용할 수 있다면 유용할 것이다. * 동료 개발자들과 잘 공유하기 위한 방법이 곧 ‘이름’을 지어주는 것이다. 소프트웨어 공학에서 디자인 패턴(Design pattern)은 프로그램 개발 시에 자주 부닥치는 애로 상황에 대한 일반적이고 재사용 가능한 추상화된 해결책이다. 소프트웨어 공학적으로 디자인 패턴은 패러다임과 알고리즘과는 다르다. OOP 패러다임으로 개발을 하든, 함수형 프로그래밍 패러다임으로 개발을 ..

Cut Vertex ( 절단점 찾기 ) Cut Vertex(절단점) 그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다. 이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다. (러프한 방법. 직접 삭제해본다. 섬나누기 or 연구소 같은 방법.) 느낌상 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다. 그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니다. 그러나 이 방식은 각 정점마다 알고리즘을 돌려야 하니 정점이 많아 질수록 매우 불리해 집니다. 2) 무향그래프의 DFS Spanning tree를 보면 cross edge가..

강한 연결 요소(SCC) 무향 그래프에서 절단점이 존재하지 않는 그래프를 우리는 Biconnected component라고 부릅니다. 절단점이 없다면 그래프 상의 어떤 점을 삭제하더라도 임의의 두 정점은 서로로 가는 경로가 존재하게 됩니다. Biconnected Component Undirected Graph에서 절단점이 존재하지 않는 그래프 Strongly Connected Component 만약 그래프의 임의의 한 정점에 대해 다른 모든 정점으로 가는 경로가 존재한다면 그 그래프를 SCC(Strongly Connected Component)라고 한다. SCC(Strongly Connected Component)특징 같은 SCC내에서 뽑은 임의의 U, V 점에서 U->V 혹은 V->U의 경로(직/간접적..

크누스 최적화(Knuth's optimization) 특수한 DP 점화식에 대해 적용할 수 있는 최적화. 조건 어떤 2차원 배열 C DP를 사용하는 2차원 배열 dp C는 i부터 j까지 합치는데 드는 비용. 여기서 비용은 이전 비용에 현재 비용을 누적해서 계산하는 문제이다. quadrangle inequeality : 사각부등식으로 (a,b,c) + (b,c,d)

LCA 기본 형에 dists배열만 만들어주어 루트노드에서 각 정점까지의 거리를 저장해준 구조이다. dfs를 이용해 각 노드 본인의 depth를 기록함과 동시에 top-down으로 거리도 dp_dists에 기록한다. (여기까지의 거리 = 부모노드까지의 거리 + cost값이다.) 그럼 dists와 depth는 끝. sparse table을 통해 각 노드에서 2의 0승,1승,2승 위의 부모노드 번호에 대해 수집한다. LCA함수를 통해 2의 n승 단위로 부모를 빠르게 타고 올라가며 공통조상의 위치를 찾는다. 공통조상만 알면 거리 배열의 연산을 통해 각 정점 간 거리를 구할 수 있다. # 정점들 사이의 최단거리는 dist[a] - dist[lca] + dist[b] - dist[lca] # LCA를 지나는 거리가..

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

점에서 각 집까지 최소거리 = 대놓고 다익스트라. 처음엔 조건 못보고 dp그려야하나 고민하고 있었는데 다시보니 가까운 순서로 방문이라고 대놓고 써줘서 다익스트라 결과값 정렬때린다음 반복문 으로 쉽게 해결했다. import sys input = sys.stdin.readline from heapq import heappop,heappush # 1. 0번에서 각 집에 가는 최소거리. -> 다익스트라 def dijkstra(start): heap = [] dp_dists[start] = 0 heappush(heap,[dp_dists[start],start]) while heap: cur_dist,cur_node = heappop(heap) for next_node,next_dists in graph[cur_n..

최단 경로 알고리즘. 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알고리즘 (Dijkstra Algorithm) 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm) 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 전체 쌍 최단 경로 문제, 다수출발, 단일도착 하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 A*알고리즘이 적합하다. 다익스트라 특정 노드에서 다른 모든 노드로 가는 최단경로를 갱신. 음의 간..

틀렸습니다 : output이 틀렷을 경우. testcase 초기화를 잘해줘야함. 시간초과 : 시간복잡도 제한을 못맞췄을 경우. => 보통 추상화 알고리즘을 잘못썼거나, 변하지 않는 dp값을 여러번 계산했을 경우(계산값 저장을 하지 않는 경우), 내장함수 계산값을 저장해두지 않고 반복문마다 돌리는 경우 => 파이썬에서 어떤 값이 같은지 비교할 때 == 대신 is를 사용하면 안됨. ++list를 큐 또는 덱으로 사용하면 절대 안됨. 반드시 collection.deque를 써야함. 런타임 에러 : 실행 시 나타나는 type, index접근 등 에러, 재귀함수가 있는 경우에는 재귀 깊이 제한인 sys.setrecursionlimit(100000)을 써줘야함. 메모리 초과 : sys.setrecursionlimi..

Max,Min => O(N) sort => O(NlogN) https://cotak.tistory.com/6?category=450881#%EB%A-%AC%EC%-A%A-%ED%-A%B--List- 참고. list dict set 메소드다있음.