알고리즘

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의 배수를 모두 지운다.🔹위의 과정을 반복하면 구하는 구간의 모든 소수가 남..

✅ 문제https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr✅ 접근 방법🔴 첫번째 시도(틀림)찾고자 하는 단어를 '?'를 중심으로 자르고 keyword에 저장한다음 이진 탐색으로 탐색하는 방법으로 시도했다. 해당 키워드를 words 배열에서 찾았을 때 `start += 1` 해서 다시 words에 키워드가 있는지 검사하는 방법으로 했는데 이렇게 하면 동일한 가사가 검색 될 경우도 있어서 당연히 틀렸다. 아래 코드와 같이 작성함def binary_sea..

틀린 코드첫번째 시도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  단어 길이를 순차적으로 탐색하면서 길이가 가장 긴 문자열한테 큰 수부터 차례대로 할당해주고 그다음 길이간 긴 문자열한테 할당해주고... 이런식으로 했는데 이렇게 접근하니까 답도 안나오고, 너무 복잡하게 생각했나 싶어서 다른 코드를 찾고하였..

문제https://school.programmers.co.kr/learn/courses/30/lessons/178870시행착오맨 처음에 이중 for문을 사용해서 완전 탐색으로 찾으려고 했다. sequence[0]부터 끝까지 탐색, 다시 sequence[1]부터 끝까지 탐색.. 이렇게 하려고 했다.그러면 시간초과 (sequence최대 배열 길이가 100만이니까 이중 for문을 쓰면 10억을 훨씬 넘어간다.  이코테에서 연산 횟수가 10억을 넘어가면 c언어를 기준으로 1초를 넘어가니까 파이썬은 더 오래걸리겠지..?  그래서 문제에 나와있는 '비내림차순' 이라는 조건을 활용해서 O(n)으로 풀어보자했다. 근데 전혀 방법이 생각이 나질 않아서 프로그래머스에 질문목록을 참고했고 아래 코드를 보았다def solut..

시행착오기둥과 보를 설치하거나 삭제할 경우 is_possible(x, y, a, answer)를 이용해서 answer에 x, y 좌표에 a(기둥/보)를 설치할 수 있냐 없냐를 반환하려고 했다.  1. 설치할 경우 answer.append(x,y,a)로 설치한 후 , is_possible(x, y, a, answer) 실행하고 함수가 false를 반환하면 answer.remove(x,y,a)해서 설치한거 제거     2. 삭제할 경우 answer.remove(x,y,a)로 제거한후, is_possible(x, y, a, answer) 실행하고 함수가 false를 반환하면 answer.remove(x,y,a)해서 설치한거 제거 근데 is_possible에 x,y,a를 넘겨줘서 그걸 기준으로 설치할 수 있느냐..

구현 중 고민되었던 부분첫번째뱀의 이동 방향에 따라 왼쪽, 오른쪽 회전 방향이 달라지는데 그걸 어떻게 구현해야하나나 같은 경우 딕셔너리를 사용해서 하나씩 다 정의해 주었다.dic = {"상":{"L":"좌", "D":"우"}, "하":{"L":"우", "D":"좌"}, "좌":{"L":"하", "D":"상"},"우":{"L":"상", "D":"하"}}  두번째뱀이 머리를 옮기고 꼬리를 이동하는 중에 중간에 몸통은 어떻게 옮겨야하나 이 부분에서 막혀서 문제를 풀지 못했다 고민 해결책이코테 책을 보고 해결하였다.첫번째처음에 오른쪽을 보고 있다고 문제에서 주어졌다.#시계 방향, 반시계방향으로 돌아가게 하기 위한 세팅(처음에 오른쪽을 보고 있으므로 동,남,서,북으로 초기화)dx = [0, 1, 0, -..