kthng

boj 2696 : Running Median https://www.acmicpc.net/problem/2696 총 3가지 방법으로 해보았다. 첫번째 : 가장 단순한 방법으로 sorting + 중간값 출력...n * n * logn역시나 시간초과 ㅎㅎ 두번째 :selection 알고리즘.예전에 코드를 직접 짜보았었던게 생각나서 해보았다.첫번째 방법이 n * n * logn 이라면 이방법은 n * n만에 가능.직접 짜는것보다 nth_element를 이용..ㅎㅎㅎ 44ms로 AC 세번째 : left, right 2개의 힙 이용.a[i]가 mid보다 클 경우 right에 push, 작거나 같은경우 left에 push.(작거나 같을 경우나 크거나 같을 경우는 따로 고려해주지 않아도 된다.)홀수번째마다 3가지 경..

boj 2698 : Adjacent Bit Counts https://www.acmicpc.net/problem/2698 생각한 시간은 길었지만 점화식은 간단하게 나온다. 1. A[n][k][e] : e로 끝나고 k개의 인접비트를 가지는 길이 n인 string의 수2. A[1][0][0] = 1, A[1][0][1] = 13-1. A[n][k][0] = A[n - 1][k][1] + A[n - 1][k][0]3-2. A[n][k][1] = A[n - 1][k][0] + A[n - 1][k - 1][1]

boj 9518 : MISA https://www.acmicpc.net/problem/9518 (Mirko의 최대 악수 수) + (Mirko없을 때의 악수 수)를 출력해주면 된다.(Mirko 없을 때의 악수 수)는 sum(각 사람들이 할 수 있는 악수 수)/2

boj 2487 : 섞기 수열 https://www.acmicpc.net/problem/2487 각 cycle 길이의 lcm을 출력해주면 된다.예를들어 섞기수열이 3 2 5 6 1 4인 경우cycle(1) = 3 (1->3->5->1),cycle(2) = 1 (2->2)cycle(3) = 3cycle(4) = 2 (4->6->4)cycle(5) = 3cycle(6) = 2이므로 lcm(cycle(1),cycle(2), ..., cycle(6))인 6을 출력해주면 정답.각각 숫자에 대한 cycle 수를 구하는 것 보단 1의 cycle을 구하고 cycle의 경로에 있는 1,3,5의 cycle 수도 모두 같은 값으로 해주면 훨씬 빠르다.

boj 2559 : 수열 psum을 이용하여 해결psum[i] 배열은 1부터 i까지의 합을 저장한다

boj 10835 : 카드게임 이것도 간단한 DP문제. a : 왼쪽카드뭉치 수열b : 오른쪽 카드뭉치 수열f(i, j) : 왼쪽 i번째, 오른쪽 j번째 카드일 때의 앞으로 얻을 수 있는 최대값이렇게 두면. 1. f(i, j) = max( f(i + 1, j + 1), f(i + 1, j), f(i, j + 1) + b[j])1.1 f(i + 1, j + 1) : 카드를 둘다 버릴 때1.2 f(i + 1, j) : 왼쪽 뭉치만 버릴 때1.3 f(i, j + 1) + b[j] : 오른쪽 뭉치만 버릴 때(이때는 왼쪽 카드보다 오른쪽 카드 값이 작아야함)

boj 2302 : 극장 좌석 쉬운 DP문제. 쉬운 DP는 그만 풀어도 되는데 손이 자꾸 가네... f(i) : vip가 없을 때 i번까지 자리를 바꿀 수 있는 경우의 수이렇게 두면1. i = 2 일 때 : f(i) = f(i - 1) + f(i - 2)2.1 f(i - 1) : i가 가만히 있는 경우2.2 f(i - 2) : i가 자리를 바꾸는 경우 vector에 0, vip1, vip2, ... vipM, N + 1을 담은 후결과값은 f(N + 1 - vipM) * ... f(vip2 - vip1) * f(vip1) 을 출력.

boj 1932 : The Triangle 전형적인 DP문제...sum[i][j] = max(sum[i - 1][j - 1], sum[i - 1][j]) + a[i][j]

boj 10164 : 격자상의 경로 많이풀어봤던 형식.O표시된 위치인 K의 값으로 y, x 좌표만 잘 해주면 되는데 여기서 실수 ㅜㅜDP로 해결.1. y = 0 or x == 0 이면 f(y,x) = 1.2. f(y,x) = f(y - 1,x) + f(y, x - 1).

boj 2513 : 통학버스 1. School을 기준으로 왼쪽 오른쪽은 서로 독립적.2. greedy로 가장 멀리사는 친구들부터 태우면 최단거리. 가장 멀리있는 친구부터 태우는게 최단거리라는건 직관적으로 이해되는데 어떻게 증명할 수 있을까?