주어진 문제는 위와 같다.이 문제를 풀면서 중요한 점이 2가지 있는데, 이것을 생각해보자. 첫번째로, $R(n,m)$을 계산함에 있어 $if m > n$ then $R(n,m) = 0$ 이라는 점이겠다.두번째로, 문제에서 주어진 식인 $R(n+1, m+1) = (R(n,m) \cdot R(n,m +1) + 1) / R(n-1, m)$ 여기서, $R(n,m)$가 사실은 다음과 같은 모양을 하고 있다고 가정해보자. $$ R(n, m) = (n - m) \cdot m + 1$$ 이러한 식을 세웠다면 먼저 검증해야할 것이 있다. 소위 말하는 수학적 귀납법이 되겠다.i) 초기 조건에서 성립하는지?ii) 임의의 상황에서도 성립하는지? 초기조건인 $n = 0, m = 0$에서는 자명하게 성립하는 것을 알 수 있다.그..

도중까지 읽다가, 아 이거 위상정렬이군 하고 있었는데, 가능하면 쉬운 문제부터 풀어야한다는 점이 상당히 핵심적그럼에도 불구하고 어렵지 않은 이유는,  topological sorting에서 indegree가 0이 되는 것들을 우선적으로 넣고, 그 이후에 node를 방문하며 하나씩 간선을 제거해나가는 (indegree를 1씩 줄이는 방식)을 취하는 것인데 이 부분에서 Indegree가 0 이 되는 것을 heap에다가 넣어두면 되겠다. Heap은 항상 최솟값을 뱉어내기 때문에, 3번 조건인 쉬운 문제부터 풀어야 한다를 풀기 최적화되어있는 알고리즘이겠다.반대로, 어려운 문제부터 풀어야한다라면, 최대힙 (즉, 마이너스를 붙여서 저장하는 것)부터 활용하면 되겠다. 아래는 답안 코드import sysimport h..

이전에 풀었던 예쁜 수 였던가? 굉장히 유사했던 것 같다.결국은 Dynamic Programming이 얼만큼 이전 정보를 유용하게 활용할 것인지? 를 묻는 상황이므로,이 부분을 잘 컨트롤 할 필요가 있겠다.  이 문제 같은 경우에는, 2가지 스텝으로 나눠서 풀면 된다. 첫번째로, 사면체로서 가능한 패턴인 숫자들을 구해주는 것이 되겠다.이를 구하기 위해서는 각 step의 삼각형을 구성하기에는 몇개의 대포알이 필요한지 알아낼 필요가 있겠다. 이는 생각보다 쉽다. $n$번째 단의 삼각형을 만드는 것에 필요한 대포알은 $n(n + 1) / 2$개이라는 것을 쉽게 알 수 있다.1, 3, 6, 10... 이런 Typical한 패턴을 주는 것에 유의하자. 그렇다면 사면체는 어떠한가? 1~n번째 단을 만드는데 필요한 ..

풀어놓고서도 오늘의 한심함이 가득가득 몰려왔었다.BOJ 게시판에 쓰려다가 말았지만 (스스로의 안일함과 멍청함에 대하여) 여기서라도 남긴다면, 주어지는 수의 범위를 잘 볼 필요가 있다. 정말 잘 볼 필요가 있다.(여기서만 한 4번 터졌다) 저 같은 경우에는 투포인터로 풀었습니다. 투 포인터라던지 이분탐색 같은 경우에는, 크기 순서대로 정렬 되어있어야한다가 전제인데요, 이 문제 같은 경우에는 겹치는 수치도 없거니와 이미 크기 순으로 정렬되어 있다는 점이 문제 풀기 딱 좋은 환경인 것 같네요. 정답 코드는 다음과 같습니다. import sysinput = sys.stdin.readlineN = int(input())liquid = list(map(int,input().split()))mix_val = int(..

코딩테스트를 준비하다보니 ... Medium을 제안 받았던만큼 스스로 풀었던 문제 복기를 좀 해볼까 한다.혹시나 싶어 코드를 보고 싶으신 분이라면 문제 번호나 타이틀로 검색하시면 좋을 것 같습니다. 238. Product of Array Except self풀이시간은 박살났지만 ..... 아이디어로는 dp 2개 (left_product, right_product) 2개 만들어서 교차 곱셈 class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: dp_left = [1 for _ in range (0, len(nums) + 1)] dp_right = [1 for _ in range (0, len(nu..

이전 스터디의 기억을 되짚어가며 .... 선수과목이라는 문제를 풀었습니다.옛날 LeetCode에서의 문제와 거의 유사한 것 같네요.indegree의 차수를 항상 유의하면서 카운팅을 하면 되겠습니다. import sysfrom collections import dequeinput = sys.stdin.readlineN, M = map(int,input().split())node_ind = [0 for _ in range (0, N+1)]answer = [1 for _ in range (0, N+1)]gp = [[] for _ in range (0, N+1)]for _ in range (0,M): a, b = map(int,input().split()) gp[a].append(b) node_..