yeony's story

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net > 투 포인터 > 슬라이싱 윈도우 윽.. 이 문제 간단해보였는데 전혀 아니었다! 혽자선 도저히 못 풀 것 같아서 결국 고수님들의 풀이를 살펴보았다. 그래도 이해가 되지 않아서 계속 그림을 그려가며 이해하기 위해 노력했다. 일단 코드는 아래와 같다. 어떤 코드에서는 딕셔너리를 이용하라고 하는데 나는 cache라는 리스트를 이용하였음. n, d, k, c ..

> dp문제 으윽 dp문제 너무 시러.. ㅠ..ㅠ 그래도 좀전에 풀었던 문제들이 dp였어서 그나마 내 기준에서는 쉽게 풀었다!! n=1일때 -> 총 2가지 0, 1 n=2일때 -> 총 55가지 00, ... 09 : 10 11, .... 19 : 9 22, .... 29 : 8 33, ... 39 : 7 44, ... 49 : 6 55, ... 59 : 5 66, ... 69 : 4 77, ... 79 : 3 88, ... 89 : 2 99 : 1 1+2+...+10 = 55 n=3일때 -> 220가지 000 > 55가지 00, ... 09 11, ... 19 ... 100 > 45가지 11, ... 19 22, ... 29 33, ... 39 200 > 45-9=36가지 300 > 36-8=28가지 4..

> dp 문제 두 문자열의 공통 부분을 찾는 문제였다. 이 문제는 다이나믹 프로그래밍을 이용하여 구할 수 있다. a 문자열이 ADABRA b 문자열이 ECADADABR 이라고 하면 가장 긴 공통 부분 문자열은 ADABR이다. 즉 길이는 5가 된다. 이를 구하려면 아래와 같이 총 6개의 리스트를 필요로 함! 저번에 풀었던 기타리스트 1495번 문제와 비슷하다. https://eboong.tistory.com/449 [1495] 기타리스트 in python > dp (다이나믹 프로그래밍) dp문제는 너무너무 어렵다... 실버1이지만 실버1 같지 않은 문제.. ㅠ.ㅠ 열심히 더 노력하자! dp로 해야해서 리스트를 도대체 어떻게 만들라는건가 햇더니 dp 리스트가 eboong.tistory.com E C A D ..

> 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 - ..