일반적으로 c++에서는 초기화한 크기가 배열의 크기보다 더 작은 경우에는 나머지는 모두 0으로 초기화 된다. 하지만, 0이 아닌 다른 수로 초기화 하고 싶을 때는 다음과 같은 방법을 이용해주면 된다. (단, 아래의 방식은 반드시 using namespace std;를 선언해주고 이용해야 한다. 그렇지 않다면 아래에 나오는 내용을 사용하려면 앞에 꼭 namespace인 std::를 꼭 붙어야 한다.) 1. fill_n 함수를 이용한다. 이 방식은 배열을 선언한 이후에 함수를 호출하여 원하는 배열의 Index에 숫자를 집어넣어주는 것이다. 사용 방법은 다음과 같다. fill_n(원하는 배열 시작 주소, 변경을 원하는 배열 Index 갯수, 변경하기를 원하는 숫자) 시작 주소라는 표현이 낯설수는 있으나, c의..

최소값과 최대값을 반환해주는 함수 min()과 max()가 존재한다. 이 함수를 사용하기 위해선 3가지 유의할 점이 있는데 1. 이 함수는 algorithm 헤더 파일에 들어있기 때문에 #include 을 선언해줘야 한다 2. using namespace std;를 선언해줘야 한다. 3. 함수명과 같은 변수 (ex: min, max)를 같이 사용해선 안된다. 위 3가지만 지켜주면 파라미터로 넣은 두 수 중 작고 큰 값을 함수 한방에 알아낼 수 있다. 만약 배열에서 최대 최소를 구하고 싶은 경우에는 다음과 같은 방법을 활용하면 된다. max_element()와 min_element() 가 그 예시이다. 대신 유의할 점이 있는데 1. 이 역시 algorithm 헤더에 있는 함수라 #include 을 반드시 ..

어려워 보일 수 있으나 도형적으로 센스를 발휘하면 쉽게 구할 수 있다. 위의 발문에서 제시한 것처럼 각 다각형은 여러개의 삼각형으로 찢어서 생각할 수 있다. 그러한 측면에서 바라본다면 각각의 도형은 작은 도형의 모임으로 생각할 수 있고, 이 측면에서 DP를 읽었으면 충분하다. 그러면 각각의 경우에 대해서 상황을 재분석하면 다음과 같다. 꼭짓점이 홀수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 짝수인 도형의 합으로 생각할 수 있다. 꼭짓점이 짝수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 홀수인 도형의 합으로 생각할 수 있다. 그런데, 꼭짓점이 짝수인 경우에는 삼각형의 가장 맞은편에 꼭짓점이 존재하고 이를 기반으로 도형은 대칭적으로 나눠지고 ..

이 문제의 경우는 모든 떨어진 거리가 정수인 것에 대하여 등차수열 관계가 이루지 못하게끔 하는 최솟값을 물어보는 것이다. 최솟값을 구해야하기 때문에 불가능한 것들을 모두 지우고 나머지 중에 최소를 구하는 것이 가장 현실적인 것을 깨달아야 한다. 그러면 문제에서 0~ 1000까지라고 하였으므로 배열을 미리 0~ 1000까지 설정하고 에라토스테네스의 체 논리처럼 슥슥 지워나가는 방향으로 하는 것이 가장 타당하다고 생각해야 한다. 또한, 고등학교때 배운 것처럼 등차수열의 3개의 항의 관계는 중앙값의 2배가 양 옆 수열의 합과 같다는 것이다. 이를 기반으로 불가능한 후보를 확보할 수 있다. 이 과정에서 이전 수열들에 대한 정보가 필요하게 되므로 이 지점에서 DP가 유리하다는 것을 인식하면 된다. 이를 기반으로 ..

상당히 어려운 문제이다. 이 문제를 보고 DP를 느끼는 것이 매우 어려운데, 각각의 타이밍마다 선택하는 기준이 앞의 선행조건에 의해 영향을 받는다는 점에 착안하여 DP 문제임을 인지하면 된다. 예를 들면 N시에 어떠한 광물을 채굴할지의 여부는 일단 전체 집단에서 N시에 끝나는 지를 확인하고 없으면 N-1시 까지의 최대 최굴량과 동일하다. 만약 존재하는 경우, 해당 시작시간이 M이라 가정하면 N - M시의 최대 최굴량에서 추가되는 최굴량을 더해준 것과 같다. 만약 N시에 끝나는 경우가 많은 경우에는 최댓값을 기준으로 결정해주면 된다. 즉, N시에서의 최대 최굴량을 구하는 과정에서 N.- M시의 최대 최굴량이 들어가게 되므로 DP를 활용하면 쉽게 구할 수 있음을 이 과정에서 느껴야 한다. // 다만, N시에..

이 문제를 보고 가장 먼저 접근한 방식은 문제에서 시키는 것처럼 (1, 1)에서부터 하나씩 경우의 수를 새어나가는 것이다. 마치 초등학교때 격자 모양이 그려진 도착하는 경우의 수를 찾는 것처럼 새는 것이다. import sys def path_finder(x , y): global n cal = data[x][y] # Early exit if x == n and y == n: return data_store[n][n] # Normal process if x + cal

1. 사용법 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산할 수 있을 때 사용한다. 2. 구성요소 Divide: 커다란 상황을 작은 상황으로 구획한다. Conquer: 작은 상황에서의 정답을 토대로 커다란 상황에서의 답을 도출한다. Base case: 가장 기본적인 상황 (더이상 작은 상황으로 구획할 수 없는 경우를 설정해야 한다.) 3. 조건 문제를 부분 문제로 나눠 풀기가 수월해야 한다. 부분문제들의 답을 토대로 원래 문제의 답을 쉽게 도출할 수 있어야 한다. 4. 예시 1) 백준 1629번 곱셈 (거듭제곱에서의 활용) 만약 단순하게 A를 B번 곱하고 이를 C로 나누어 나머지를 구하는 방식으로 이 문..