one Book a Day

뭔가 줄일수 있을 것 같긴한데 일단 통과. 3차원 배열은 뭔가 3차원값들에 대해 늘 초기화해줘야 한다는게 좀 짜증난다. 얕은복사라 그런가 자꾸 초깃값을 가져와서 새로 덮어씌우는 바람에 아직 설계가 손에 익지 않는다. 오늘 좀 더 설계에 대해 연습해 볼 것. 3차원 배열 내 값의 수정과 반복문에 대해서. import sys input = sys.stdin.readline # 세로 M 가로 M M,N = map(int,input().split()) K = int(input()) maps = [list(input().rstrip()) for _ in range(M)] dp = [[[0,0,0] for _ in range(N)] for _ in range(M)] # 정글 J 바다 O 얼음 I for i in r..

다른 스터디원들 보면 뭔가 짧게 풀었던데 일단 나는 0,0기준 고쳐야하는것 체크하고 그 값 범위마다 따로sum구해서 비교했다. import sys input = sys.stdin.readline N,M = map(int,input().split()) chess = [list(input().rstrip()) for _ in range(N)] dp = [[0]*M for _ in range(N)] for i in range(N): for j in range(M): if i%2 == j%2: if chess[0][0] != chess[i][j]: dp[i][j]=1 else: if chess[0][0] == chess[i][j]: dp[i][j]=1 min_change = float('inf') for i i..

1.잔디 옵션이 프라이빗으로 바뀌어있는지 확인한다. => public으로 바꾼다. 2. 깃헙에 등록되어있는 메일이 바뀌어서 local git의 메일주소와 불일치 하게 되었는지 확인한다. => 깃 메일을 일치시키던가 깃헙에서 삭제한 메일을 다시 등록한다. 3. 특정레포의 강제푸시 혹은 merge로 commit기록이 전부 초기화 됐다!! 이러면 정말 눈물나지만 해결 방법이 있다. github api를 이용해 과거로 회귀하는것. 1. Access Token을 발급받는다. https://github.com/settings/tokens 에 가서 토큰 생성을 누르고 repo전체 선택 후 발급 받는다. 2. 강제 푸시 전 혹은 레포가 정상일 적 마지막 커밋 SHA값을 확인한다. curl -H "Authorizatio..

Tree 탐색등등 종종 나오는 경우의수를 따지는 DFS문제이다. idx 값을 1개 늘리냐 2개 늘리냐의 분기로 재귀를 실시. 실질적인 4방탐색이나 숨바꼭질 같은 문제와 다를게 없다. 재귀로 값을 누적시키며 달릴것이냐 큐나 스택을 이용할 것이냐의 차이. 선택의 문제. 경우의 수. 종료조건은 max값이 수열 길이와 같은 것. 왜 못풀었을까 생각해보자. import sys from collections import deque def DFS(idx): # idx 1부터 시작 kriii의 검사가 모두 끝나면 수열의 가장 큰 값을 찾는다. if idx == len(kriii): high = 0 for i in range(len(sequence)): high = max(high,int(sequence[i])) # 가..

0,1 knapsack 선택하느냐 마느냐의 문제는 greedy가 안되기 때문에 점화식을 세울 수 있다면 dp 아니면 완탐이다. K라는 무게값을 1~target값까지 증가시키며 최고 가치를 누적시키면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) wei_cost = [[0,0]] dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N): wei_cost.append(list(map(int, input().split()))) for i in range(1, N + 1): for j in range(1, K + 1): weight = wei_cost[..

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]*N for _ in range(N)] for i in range(N): for j in range(N): dp[0][0] = matrix[0][0] if i==0 and j>0: dp[i][j] = dp[i][j-1]+matrix[i][j] elif j==0 and i>0: dp[i][j] = dp[i-1][j]+matrix..

이해하는데 꽤 오래 걸렸다. dp를 대각선으로 그려야 답을 구할 수 있는 문제로 아주 신박하고 연습이 필요한 문제일 것 같다. dp[i][i+j]로 놓고 i를 증가시키면 양쪽이 1,1씩 증가해 대각선 배열을 먼저 연산 할 수 있으며 j가 늘어나면 가운데 대각선에서 한칸 더 멀어진 배열을 연산하게 되는 식이다. 즉 2개씩 묶은 행렬을 계산하고(AB,BC,CD,CE) 그 값을 가지고 3개씩 묶은 행렬을 계산. min(AB*C or A*BC) 그걸 가지고 4개씩 묶은 행렬을 계산min(A*BCD,AB*CD,ABC*D) N*N 인접 행렬에서 대각선으로 배열을 채우는법을 이해할 수 있었고 차후 다른 문제에서도 쓸만한아이디어인 것 같다. 행렬의 곱셈이 이루어지는 숫자는 [앞행렬의 행값 * 앞행렬의 열값(==뒷행렬의..

경우의 수를 만들어 연산자를 대입하는 문제였다. 보자마자 DFS가 생각나서 설계했는데 처음에는 +-보다 */연산을 먼저 처리하는 줄 알고 문자열로 calculate를 쌓고 eval answer에 삽입햇으나 테케 통과 못하고 문제 다시일어보니 앞에서부터 순차 연산... str에서 int로 바꾸고 진입시마다 계산해주면서 들어갔다. import sys input = sys.stdin.readline def DFS(idx,calculate): if idx==N: answer.append(calculate) return num = seqs[idx] for operator in '+-*/': if operator == '+'and opers[0]: opers[0] -=1 DFS(idx+1,calculate+num)..

너무나 명백하게 플로이드 워셜을 쓰라고 문제에 주어졌다. 플로이드 워셜을 통해 거리배열을 얻어내고 치킨집 2마리를 조합으로 묶어내면서 각 거리의 합을 미니멈으로 비교하는 문제이다. 인접리스트를 사랑하는 입장에서 인접행렬문제는 늘 까다롭다. 아직 코드가 손에 안익어서 그럴수도.. import sys input = sys.stdin.readline N,M = map(int,input().split()) graph = [[float('inf') for _ in range(N)] for _ in range(N)] for i in range(M): a,b = map(int,input().split()) graph[a-1][b-1] = 2 graph[b-1][a-1] = 2 for i in range(N): gra..

문제해결에 선행또는 후행 하는 순서가 있으면 위상정렬을 이용하면 쉽게 풀 수 있다. 위상정렬이란 위상이 0 즉 앞뒤에 뭐가 없는 node부터 위로 찬찬히 쌓아 나가는 것. 위상0인 문제를 해결했으면 그 바로 연결된 노드들의 위상을 1씩 낮추면서 계산해 나간다. 나는 배열에 쌓기 위해서 앞에 나와야 하는 노드를 위상0으로 두었지만 반대로 뒤가 없는 노드들을 먼저 쌓고 역순으로 출력할 수도 있을 것이다. import sys from collections import defaultdict,deque input = sys.stdin.readline def topological_sorting(): queue = deque() for i in range(1, N+1): if level[i] == 0: queue.a..