yeony's story

역시나 처음에 조합부터 떠오른 1인.. 하지만 시간 초과 뜰 게 뻔해서 dp로 다시 방향을 바꾸었다! 이 문제는 피보나치 수열과 매우 유사하다. n=1일때 1개 n=2일때 2개 n=3일때 3개 (1+2) n=4일때 5개 (2+3) dp[n]=dp[n-1]+dp[n-2] 그래서 간단하게 답을 도출해낼 수 있었다. 정답코드는 아래와 같다 n=int(input()) dp=[0] * 1000001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=(dp[i-1]+dp[i-2])%15746 print(dp[n]) 위 코드 같은 경우에는 시간이 473ms가 떠서 더 좋은 방식이 있나 찾아봤더니 행렬곱셈을 이용하여 피보나치 수열을 하게 되면 더 빠르게 값이 도출된다는 것을 알게 되었다...

처음 생각해냈던 풀이는 시간초과가 났다. 백트래킹 방식으로 풀어봤는데 모든 경우의 수를 탐색해서 그런가보다 :( 그래도 ide에서 돌리면 값은 나오긴 하지만 시간 초과 문제를 해결해야 정답을 인정받을 수 있으므로 다른 방식으로 코드를 작성했다. # n = int(input()) # n

덱을 이용해서 양방향 배열 구현하기 연산의 종류 3가지 1. 첫 번째 배열 원소 빼내기 2. 왼쪽으로 배열 이동 3. 오른쪽으로 배열 이동 while i != array[0]: array.appendleft(array.pop()) cnt += 1 array.popleft() while문이 끝난 뒤 array.popleft()를 붙여주지 않아서 한동안 헤맸다! 문제 풀기 전에 미리 설계를 해두고 코드를 짜는 습관을 들여보자 :).. from collections import deque n, m = map(int, input().split()) array = deque([i for i in range(1, n + 1)]) location = list(map(int, input().split())) cnt =..

합 > x 1. 가장 짧은 막대기를 절반으로 나눈 막대기를 리스트에 넣는다. (원본 막대기는 삭제) 2. 리스트 오름차순으로 정렬 3. 가장 짧은 막대기의 절반을 제외한 나머지 합계가 x보다 크거나 같으면? 가장 짧은 막대기의 절반 하나를 제거한다. 이 과정은 합==x일 때 종료 x=int(input()) array=[64] while sum(array)>x: # 합>x # 1번 min_value=min(array) # 가장 짧은 막대를 절반으로 나눈다. array.remove(min_value) array.append(min_value//2) array.append(min_value//2) array=sorted(array) if sum(array)-min_value//2 >=x: array.remov..

파일의 목록에 원래의 비밀번호, 비밀번호를 역순으로 한 단어가 있다. n = int(input()) words = [input() for _ in range(n)] for word in words: if word[::-1] in words: len_word=len(word) mid=len_word//2 print(len_word, word[mid]) break

너무 어렵다 ㅠㅠ 어려어ㅜ... 혼자 끙끙 고민하다가 결국 인터넷에서 풀이를 찾아봤다! 바이러스 퍼지게 하는 건 재귀함수로 하면 될 것 같았지만, 벽을 어디에 세워야할지 정하는 기준을 몰라서 헤맸던 문제 일단 바이러스가 있는 위치를 리스트로 저장하기 벽 선택하는 함수 1개 바이러스를 퍼트리는 함수 1개를 구현 1. 벽 선택하는 함수 벽 count가 3 미만인 경우와 count가 3인 경우를 나눠서 생각해줘야한다. 벽 count가 3 미만이라면? > 벽을 선택하는 과정이 들어가줘야한다. 경우의 수가 많이 없으므로 처음부터 끝까지 for문을 돌린다. (총 횟수 : n*m-start ) 현재 위치가 빈 벽이면 벽을 세우고 재귀함수를 호출! (그 자리에서부터 다시 벽을 세울 자리를 탐색) 재귀함수의 수행이 끝나..

이 문제도 역시나 백트래킹 python3로 돌리면 시간초과가 나서 pypy3로 돌렷다 ㅠㅠ 그래도 시간이 많이 나오긴 하는데 효율적인 코드를 좀 뒤져봐야 할 것 같다! n = int(input()) array = list(map(int, input().split())) operator = list(map(int, input().split())) # +, -, *, // str_operator = [] for idx, i in enumerate(operator): if idx == 0: for j in range(i): str_operator.append('+') continue elif idx == 1: for j in range(i): str_operator.append('-') continue eli..

n = int(input()) array = list(map(int, input().split())) visited = [0 for i in range(n)] answer = 0 new_array = [] def dfs(cnt, new_array): global answer if cnt == n: answer = max(answer, sum(abs(new_array[i]-new_array[i+1]) for i in range(n-1))) return for i in range(n): if visited[i]: #방문한 곳이라면? continue visited[i] = 1 new_array.append(array[i]) dfs(cnt + 1, new_array) visited[i] = 0 new_array..

1535번 안녕 문제는 브루트포스 알고리즘, 배낭 문제에 해당한다. (처음에 내가 생각했던 풀이) itertools 라이브러리 combination을 이용하여 먼저 경우의 수를 찾고 그 수들 중에 조건을 만족하면서 값이 최대인 수를 출력하게끔 했다. answer에 아무 숫자가 들어가있지 않다면 조건에 해당하는 경우가 하나도 없다는 것을 의미한다. 그래서 0을 출력하게끔 처리해야 valueError가 발생하지 않는다. 제한 시간은 2초인데 실행 시간이 1.2초 나와서.. 내 코드보다 더 효율적인 코드를 찾아 떠나보았다. import itertools person = int(input()) loss = list(map(int, input().split())) smile = list(map(int, input..

dp = [1, 1, 1, 2] t = int(input()) for i in range(t): n = int(input()) if len(dp) < n: for _ in range(n - len(dp)): dp.append(dp[len(dp) - 3] + dp[len(dp) - 2]) print(dp[n - 1]) continue # 이미 값이 정해져있는 경우 print(dp[n - 1])