알고리즘

1. 분류다이나믹 프로그래밍 2. 풀이 첫 몇 항을 제외한 나머지 모두가 규칙에 맞춰 증가하는 형태를 이루고 있다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 3이 쓰여진 삼각형의 한쪽 변에 1, 2 삼각형, 4가 쓰여진 삼각형의 한쪽 변에 1, 3 삼각형, 5가 쓰여진 삼각형의 한쪽 변에 1, 4 삼각형, ... D[N] = D[N-1] + D[N-5]의 규칙에 맞춰서 증가한다. 첫 몇 항만 초기화해주고 나머지는 저대로 구하면 답을 쉽게 찾아낼 수 있다.

1. 분류다이나믹 프로그래밍 2. 풀이 파스칼의 삼각형이 이항계수를 나타낸다는 것을 알고 있었다면 쉽게 풀리는 문제이다. 최상단 1을 초기화하고 이후부터 좌측, 우측 끝단을 1로 만든 후 가운데 숫자를 만들어내면 끝이다. 2차원 배열 d[y][x]가 이항계수에 들어갈 숫자들을 저장한다. 가장 윗 줄부터 하나씩 채워넣으며 N, K를 구하면 된다.

1. 분류다이나믹 프로그래밍 2. 풀이 규칙만 찾으면 금방 풀리는 문제이다. 나는 이런 류의 문제에서 규칙성이 있겠다 판단되면 엑셀을 켜고 하나하나 대입하여 확인한다. 대부분의 경우에 규칙이 적용되면 금방 구할 수 있기 때문이다. N, K에 숫자를 0, 0부터 대입하여 몇 개 구하면 바로 알 수 있다.

1. 분류이분탐색 2. 풀이 먼저 N개의 숫자를 입력받은 뒤 이어서 입력받는 M개의 숫자가 먼저 받은 N개 숫자들 중 있는지를 찾는 문제. N, M 둘다 최대 10만 개까지 입력이 가능하기 때문에 O(N^2) 이상은 무조건 시간 초과가 난다. 입력받은 숫자를 오름차순으로 정리한 뒤 이분탐색으로 찾는다면? N개 입력 : O(N)정렬 : sort 함수 이용 - O(NlogN)탐색 : O(MlogN) 이 정도면 제한시간 내에 무리없이 찾아낼 수 있을 것이다.

1. 분류수학, 분할정복 2. 풀이 A를 B만큼 제곱한 수를 C로 나누어 나머지를 구하는 문제이다. 입력 범위가 int 한계치(2^32 - 1)기 때문에 자료형은 unsigned long long형으로 잡았다. 입력 한계치가 매우 큰 만큼 B번 거듭제곱할 때 O(N)으로 구하면 무조건 시간 초과가 나게 된다. B를 반씩 나누어가며 분할정복으로 거듭제곱을 구하면 시간 내에 풀 수 있다.

https://www.acmicpc.net/problem/1780 1. 분류분할정복 2. 풀이 대놓고 분할정복으로 풀라는 문제이다. 3의 제곱으로 입력이 주어진 입력을 계속 9등분하여 영역을 구해야 한다. 중앙부터 시작하여 조건이 충족되었는지 검사하고, 9등분으로 나뉜 각 영역의 중앙으로 이동하여 다시 검사한다. 재귀함수와 각 영역을 검사하는 함수를 만들었다. 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 1. 재귀함수는 위의 두 가지 조건을 충족시켜야 한다. 1의 조건이 만족하지 않는 영역을 분할하며 각 영역의 중앙을 매개변수로 다시 재귀함수를 실행한다..

https://www.acmicpc.net/problem/1654 1. 분류이분탐색 2. 풀이 14627번 파닭파닭과 굉장히 유사한 문제이다(http://private-space.tistory.com/11). 파닭파닭 문제에서 조금 변형하여 해결했다. 3. 소스코드 #include typedef unsigned long long ull; ull wire[10000]; ull bs(int k, int n, ull max) { ull low = 1, high = max, mid = (low + high) / 2; while (low = n) low = mid + 1; else high = mid - 1; mid = (low + high) / 2; } return mid; } int main() { int k..

https://www.acmicpc.net/problem/14501 1. 분류다이나믹 프로그래밍 2. 풀이 퇴사하기 전 최대한 뽕을 뽑고 가는 방법을 구하는 문제이다. 한 번의 상담에 소모하는 기간이 있으며 그 동안에는 다른 상담을 진행하지 못한다. 각 상담에는 받을 수 있는 금액이 정해져 있고 완전히 종료해야만 수령할 수 있다. 최대 입력이 15정도로 낮기 때문에 어지간한 방법으로는 시간 제한에서는 상당히 자유로워 보인다. 아래는 문제를 해결하는 데 생각했던 것들이다. 1. 상담을 시작하면 (오늘 + t)일에 p만큼 정산을 받는다. - 이번 상담을 진행하는 것이 이익인지를 판단한다. 2. 1일차부터 계산해가며 마지막 날의 최대 금액을 출력한다. 3. 소스코드 #include int dp[25]; int..