yeony's story

> dp (다이나믹 프로그래밍) dp문제는 너무너무 어렵다... 실버1이지만 실버1 같지 않은 문제.. ㅠ.ㅠ 열심히 더 노력하자! dp로 해야해서 리스트를 도대체 어떻게 만들라는건가 햇더니 dp 리스트가 여러개 필요했다. start, 볼륨 리스트 개수... 하나의 dp 리스트로만 풀 수 잇을거란 생각을 깨자 이렇게 여러개로 하면 더 쉬울때도 있다.. 트리식으로 가지치기가 필요한 순간이라면 Dp를 떠올려보자! 두려워하지말기 :) n, s, m = map(int, input().split()) v = list(map(int, input().split())) dp = [[False for _ in range(m + 1)] for _ in range(n + 1)] # start, nList dp[0][s] =..

> 너비 우선 탐색 맥주 개수를 체크해줘야 하는 줄 알고 선언했는데 굳이 필요 없었다 헷.. 문제에서 넘길 부분은 과감하게 넘기자 .. from collections import deque t = int(input()) def bfs(): queue = deque() queue.append([hx, hy]) while queue: nx, ny = queue.popleft() if abs(nx - rx) + abs(ny - ry)

> 수학 알고리즘 규칙을 찾아 푸는 문제 https://danco.tistory.com/30 [1024] 수열의 합 https://www.acmicpc.net/problem/1024 처음에 나누는 수 L을 짝수일 때, 홀수일 때로 나눠서 나온 수를 수열의 가운데 있는 숫자라고 정하고, 그 수 앞뒤로 연속되는 숫자를 출력하는 방식으로 했는데 94%에 danco.tistory.com 위 블로그에 규칙 정리가 잘 되어 있어서 펌해왔음. n= 18, L=2일 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 출력값은 5,6,7 연속된 숫자의 합이 n과 같아져야 하고 그 연속된 숫자의 길이가 가장 짧아야한다. 위 과정을 수식으로 정리하면 아래와 같다. n=(x+1)+(x+2)+..

수 복원하기 문제는 소수를 통해 소인수 분해를 진행해야 했다. 소수를 구할땐 에라토스테네스의 체를 이용하면 빠른 시간 내에 소수를 구할 수 있다. 문제에서 주어진 최대의 수만큼 리스트를 생성하고 소수를 모아둔 리스트를 prime에 넣는다. -> 소수를 구하는 과정을 1번만 진행하기 위함. 소인수를 구할 때 소수를 이용한다. 만약 주어진 수가 6이라고 치면 6을 소인수 분해하면 2 1 , 3 1 이렇게 답이 나온다. 즉 2 x 3 = 6, 12를 소인수 분해하면 2 2 , 3 1 즉 (2x2) x (3x1) = 12 12이하인 소수들 가지고만 판별을 진행한다. 1) 소수(i) 2, num = 12 12 % 2 = 0일 경우 2를 인자로 가지고 있다. cnt+=1 num에는 2를 나눠야한다. 따라서 num ..

https://www.acmicpc.net/problem/2473 투 포인터를 활용하여 풀어야했던 문제! 빡구현으로 풀게 되면 당연히 시간초과가 발생한다. 이분 탐색을 이용하려면 일단 오름차순으로 리스트를 정렬한 뒤 투 포인터를 사용해야 한다. 세 용액의 합이 음수이면 left 포인터가 오른쪽으로 1칸 이동하고 양수이면 right 포인터가 왼쪽으로 1칸 이동한다. left 포인터가 오른쪽으로 움직이거나 right 포인터가 왼쪽으로 움직이게 되면 합의 절댓값이 0에 가까워진다. 지금 같은 경우에는 left의 위치가 i+1, right의 위치는 평소대로 n-1에 위치해있다. 왜냐하면 이 문제에서는 두 용액이 아닌 세 용액의 합을 더해줘야 하기 때문이다. 따라서 array[i]의 값은 0부터 n-2-1까지만 ..

https://www.acmicpc.net/problem/16678 문제에서 주어진 그대로 for문을 사용하여 구현하였으나 시간초과 흠... 그럼 어찌해야하나.. n = int(input()) array = sorted(list(int(input()) for _ in range(n))) answer = 0 for num in range(n): array = [array[i] - 1 for i in range(n)] if array[num] >= 1: answer += array[num] print(answer) 변수 t를 이용하여 손쉽게 해결할 수 있었다. t가 모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시키는 데 사용되는 변수다. n = int(input()) array = sorted(li..

윽 너무 어려웠다 ㅠㅠ... 일단 상승곡선이 하락곡선 또는 하락곡선이 상승곡선으로 바뀌는 구간이 2개 이상일 경우에는 -1을 출력해야 한다. 그리고 이미 주어진 배열 자체가 증가 또는 감소 수열이면 0을 출력한다. 두 가지를 제외했을 때가 직접 바꿔줘야 하는 때이다. 아래 코드 지저분함 주의.. # n = int(input()) # array = list(map(int, input().split())) # cnt = 0 # plus = False # minus = False # button = False # mid=False # answer = 0 # # for i in range(1, n): # if cnt > 1: # print(-1) # exit() # if array[i] >= array[i - ..

itertools에 있는 permutation 함수를 사용하여 문제를 풀었더니 당연히 메모리 초과,,, 큽.. import itertools n = int(input()) array = list(map(int, input().split())) temp = list(itertools.permutations(range(1, n + 1), n)) # array[0] = 소문제 번호 if array[0] == 1: # k를 입력받음 -> array[1]에 있음 print(*temp[array[1] - 1]) else: # 임의의 순열을 나타내는 n개의 수를 입력받음 # array[1:n+1] print(temp.index(tuple(array[1:n + 1])) + 1) 직접 구현해야하나 고민했지만, 이것도 마..

dfs만을 이용하면 시간초과가 나는 문제 다이나믹 프로그래밍을 이용해야 한다. 이중 for문으로 탐색을 진행한다. 오른쪽, 아래로만 이동가능하며 dp[n-1][n-1]에 경로의 수가 저장되어 있다. N=int(input()) array=[list(map(int,input().split())) for _ in range(N)] # 오른쪽이나 아래로만 이동 가능 # 0이 종착점 answer=0 dp=[[0]*N for _ in range(N)] dp[0][0]=1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cnt = array[i][j] # 오른쪽으로 가기 if j + ..

https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 처음엔 함수를 만들어서 하려고 했는데 굳이 그렇게 할 필요 없을 것 같아서 (사실 재귀함수보다 반복문이 더 편함..) 반복문을 사용하여 다이나믹 프로그래밍 기법으로 문제를 해결했다! t = int(input()) array = [0 for _ in range(68)] array[0] = 1 array[1] = 1 array[2] = 2 array[3] = 4 for _ in ..