전체 글195 #2933 미네랄 문제 링크 : https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 문제를 이해하는 것만 해도 시간이 오래걸렸다. 뭔가 이런 류의 문제들은 방법이 생각나더라도 너무 노가다의 향이 진해 다른 더 좋은 방법은 없을까 계속해서 고민하게 된다. 로직을 짜고 코딩을 하는데 잔실수들이 많기도 하고 미처 고려해주지 않은 오류들이 자꾸 발생한다. 익숙해질만큼의 시간이 필요해 보인다. 양 옆으로 막대기를 던져 걸리는 미네랄을 지우는 것은 쉽다. 하지만 그 후 떨어질 수 있는 cl.. 2022. 1. 8. 동적 계획법 Dynamic Programming (DP) Divde & Conquer 과 같이 문제를 작은 부분문제들로 쪼개는 과정을 거친다. 하지만 DP는 memoization을 사용한다는 차이점이 있다. 여기서 memoization이란 한 번 계산한 값을 저장해 두었다 재활용하는 기법을 의미한다. 종합하자면, Divide & Conquer은 부분 문제들이 서로 겹치지 않을 때 사용하기 좋다. 만약 동일한 부분 문제들이 계산 과정에서 여러 번 등장한다면, 중복 계산을 피하는 DP를 사용하는 것이 좋다. 이항 계수 (binomial coefficient) 계산을 예로 들어보자. $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = (\binom{2}{0} + \binom{2}{1}) .. 2022. 1. 7. 분할 정복 Divide & Conquer 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 일반적인 재귀 호출은 문제를 한 조각과 나머지 전체로 나누는 반면, 분할 정복은 거의 같은 크기의 부분 문제로 나눔. 세 가지의 구성 요소 문제를 더 작은 문제로 분할하는 과정 (Divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (Merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (Base case) 가장 대표격이라 할 수 있는 문제는 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사.. 2022. 1. 7. 무식하게 풀기 Brute-force, Exhaustive search 가장 기초적이고 기본적인 패러다임이다. 그리고 가장 간단하기에 어떤 문제든 brute-force로 먼저 접근한 후 complexity를 계산해보고 주어진 자원 내에 가능한지 빠르게 생각해보는 것도 좋다. Recursion은 로직의 복잡함을 줄여준다. 내가 recursive function을 짜는 방법은 이러하다. recursion이 가능한, 내가 결과값을 정의한 마법의 함수 f을 생각하고 f(n-1)을 이용해 함수 f(n)을 짠다. (대략적으로) 기저 사례를 고려한다. 예를 들어 1부터 n까지 더해주는 함수를 구현한다면, f(n)이 1부터 n까지의 값들을 전부 더한 값을 리턴하는 함수라 생각한다. 그렇다면 f(n-1)을 이용하여 f(n) = f(n-.. 2022. 1. 6. 이전 1 ··· 44 45 46 47 48 49 다음
