pinary[i] = i 자리 이친수를 만들 수 있는 경우의 수pinary[i]는 i-1 자리 이친수 패턴을 그대로 적용할 수 있다.그리고 위 사진을 잘 보면 i 자리 이친수는 i-2 자리 이친수 패턴이 적용된 i -1 자리 이친수에 2가지 경우 (0, 1)가 가능하다. 예를 들어서 i = 5 라고 하면,10000, 1000110101, 10100빨간색으로 칠한 부분이 i = 3 자리인 이친수이다.pinary[i] 는 pinary[i-1]의 경우의 수를 그대로 가져가고, 추가로 pinary[i-2]의 경우의 수가 추가된다. 결국 pinary[i] = pinary[i-1] + pinary[i-2] 가 성립
플로이드 워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구히야하는 경우다익스트라는 한 지점에서 다른 특정 지점까지의 최단 경로구하는 알고리즘 문제 보자마자 걍 다익스트라, 플로이드 어쩌구 알고리즘 사용해야지! 떠올렸는데... 구현을 못함 시도플로이드 워셜 알고리즘 구현시 고려할 점이 "거쳐 가는 노드" 를 기준으로 구현하면 되는데, 거처가는 노드 k 를 for루프 맨 처음에 시작해서 계속 실패함n, m = map(int, input().split())#인접행렬data = [[5001] * n for _ in range(n)]for i in range(n): for j in range(n): if i == j: data[i][j] = 0for _ i..
파란색 구간이 구해야하는 구한 합이라면 빨간색 부분과 초록색 부분을 제외하면 된다고 생각시도1맨 처음에 가로 구간합, 세로 구간합으로 나눠서 구했음. (파란색 구간의 누적합 - (빨간색 누적합 + 주황색 누적합 + 빨,주 겹치는 부분)) 으로 구하면 될 줄 알았다근데 그림에서도 보이다시피 파란색에 끝부분과 주화색 끝 부분도 계산식에 포함돼서 결과가 제대로 나오지 않음 시도2저 양쪽 끝을 포함하지 않도록 하기 위해 행별로 누적합을 구하기로 했다.코드import sysn, m = map(int, input().split())data = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]#가로형태?로 누적합 구한것sum_col ..
이 문제의 핵심은 소수를 어떻게 효율적으로 찾을것인가 문제였던거 같다..✅ 에라토스테네스의 체알고리즘 설명🔹2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.🔹2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)자기 자신을 제외한 2의 배수를 모두 지운다.🔹남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)자기 자신을 제외한 3의 배수를 모두 지운다.🔹남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)자기 자신을 제외한 5의 배수를 모두 지운다.🔹남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)자기 자신을 제외한 7의 배수를 모두 지운다.🔹위의 과정을 반복하면 구하는 구간의 모든 소수가 남..
틀린 코드첫번째 시도n = int(input())alpha = []length = []for _ in range(n): s = input() alpha.append(s) length.append(len(s))alpha.sort(key=lambda x:len(x), reverse=True)dict = {}num = 9def alpha_to_int(a, next): global num length = len(a) for i in a: if next 단어 길이를 순차적으로 탐색하면서 길이가 가장 긴 문자열한테 큰 수부터 차례대로 할당해주고 그다음 길이간 긴 문자열한테 할당해주고... 이런식으로 했는데 이렇게 접근하니까 답도 안나오고, 너무 복잡하게 생각했나 싶어서 다른 코드를 찾고하였..
구현 중 고민되었던 부분첫번째뱀의 이동 방향에 따라 왼쪽, 오른쪽 회전 방향이 달라지는데 그걸 어떻게 구현해야하나나 같은 경우 딕셔너리를 사용해서 하나씩 다 정의해 주었다.dic = {"상":{"L":"좌", "D":"우"}, "하":{"L":"우", "D":"좌"}, "좌":{"L":"하", "D":"상"},"우":{"L":"상", "D":"하"}} 두번째뱀이 머리를 옮기고 꼬리를 이동하는 중에 중간에 몸통은 어떻게 옮겨야하나 이 부분에서 막혀서 문제를 풀지 못했다 고민 해결책이코테 책을 보고 해결하였다.첫번째처음에 오른쪽을 보고 있다고 문제에서 주어졌다.#시계 방향, 반시계방향으로 돌아가게 하기 위한 세팅(처음에 오른쪽을 보고 있으므로 동,남,서,북으로 초기화)dx = [0, 1, 0, -..
이코테에서 효율적인 화폐 구성 문제와 비슷해서 비슷한 풀이로 풀 수 있었다.첫번째 코드n = int(input())#설탕이 최대 5000이므로 data = [5001] * (n+1)bag = [3, 5]for i in bag: if i > n: continue data[i] = 1#배열 n에...3키로,, 5키로for k in bag: for i in range(k, n+1): if data[i-k] != 5001: #가방 단위로 배달 가능하면... data[i] = min(data[i], data[i-k]+1)if data[n] != 5001: print(data[n])else: print(-1) 이전에 이 문제를 푼 코드가 있어서 확인해 봤더니 이전에 푼 코드가 더 빠르고..
접근 방법2차원 배열에 입력을 저장하고 더하자.n, m이 입력되면 [m][n]인 이중 배열을 선언하고i, j, x, y가 입력되면 이중 반복분으로 [j][i] ~ [y][x]를 더하자. 1차시도 (시간초과)2차시도 (pypy로 컴파일, 성공)import sysn, m = map(int, sys.stdin.readline().split())lst = [[0]*n for _ in range(m)]for i in range(n): for idx, k in enumerate(sys.stdin.readline().split()): lst[idx][i] = int(k)num = int(sys.stdin.readline())result = [0]*numfor idx in range(num): i,j,x,y ..
