yeony's story

> 재귀함수 n=3일 경우 1번 초기값을 제외한 7번의 과정을 통해 하노이 탑을 수행한다. 기둥은 총 3개 f , m , e 순서로 나열되어 있다. 우리는 f 에 있는 원판을 e로 옮겨야한다. 여기서 신경써야 할 조건은 작은 원판이 큰 원판 아래에 있을 수 없다는 것. 이동 횟수가 최소가 되어야 한다는 점. 아래 그림처럼 하나하나 조건을 다 나눠줘야하나 생각했다. 왜 알고리즘 문제를 풀때마다 세부적으로 세세하게 생각을 하는지 ㅠㅠ 큰 틀을 바라봐보기 위해 노력하였다. 그랬더니 맨 아래에 있는 가장 크기가 큰 원판을 제외한 나머지 원판이 m 위치의 기둥에 있어야 하고 f 기둥에 남아있는 원판이 e 기둥으로 옮겨져야 한다. 마지막으로 m 기둥에 있는 원판이 e 기둥으로 옮겨지면 끝! n=3 hanoi(3,1..

> 자료구조 > 덱 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 처음 떠올렸던 생각은 array의 값을 하나씩 지워주면 이미 터뜨린 풍선을 따로 뛰어넘는 로직을 만들어줄 필요가 없을 것 같았다. 그래서 풍선을 터뜨리는 순간 해당 풍선은 배열에서 값이 사라지게끔 했는데 이렇게 하니까 인덱스 번호를 어떻게 남겨야할지 고민이었다. 연산으로 할 수 있는지 이것저것 갖다 붙여봤는데 도저히 안돼서 결국,, 인덱스 리스트를 하나 새로 ..

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까지만 ..