링크 https://www.acmicpc.net/problem/11053 난이도(solved.ac 참고) 실버2 풀이 응용이 많이 되는 유형이다. 이 문제를 먼저 접한 이유는 원래 오늘 풀기로 했던 병사 배치하기를 풀 때 필요한 부분이라고 생각되었기 때문이다. n까지의 범위를 가지는 i와 i까지의 범위를 가지는 j를 돌면서, 증가하는 부분 수열의 길이가 증가하려면 a[i]의 값이 a[j]보다 커야한다. 이 경우 dp의 값은 더 작은 인덱스인 j의 dp 인덱스에 1을 더해준 것과, 기존의 dp[i]의 값중에 더 큰 값이 들어가야 한다. 전자에서 +1이 들어가는 이유는 증가하는 부분수열의 길이가 1 증가했기 때문이다.

링크 https://www.acmicpc.net/problem/14501 난이도(solved.ac 참고) 실버4 풀이 동적계획법은 알고리즘 수업때 풀어본 게 마지막이니까, 대충 2-3달만에 풀어봤는데 역시 쉽지 않다. 실버 4였지만.. 생각하는 힘이 좀 부족하다고 생각한다. 동적계획법 문제는 많이 풀어봐야겠다. dp를 100이나 둔 이유는 16(n의 최대값 + 1)으로 넣어서 했더니 자꾸 인덱스 오류가 나서 짜증나서 그냥 100으로 해버렸다. 물론 메모리 제한이 좀 있었다면 당연히 못 맞았다. dp 배열에 대해 i일 뒤에 받게 될 금액, 그러니까 dp[i] + p_list[i]가 현재 금액 (dp[i+t_list[i]])보다 크다면 큰 값을 반영해주는 방식으로 진행했다. 그리고, 현재 받게 될 금액이 다..

풀이 DP문제 중 계단 오르기와 더불어 기초에 해당하는 문제인데, 점화식을 찾지 못하면 좀 어려울 수도 있는 문제이다. DP의 핵심은 우선 부분해를 구한 뒤 그것을 일반화하는 것이라고 생각한다. 그래서, 우선 쉽게 구할 수 있는 2*1과 2*2 각각을 구한 뒤에 3부터 일반화하여 구했다. 한번 생각해보자. 2 * 3의 바닥을 채우는 방법은 2 * 2의 바닥을 채우는 방법(2*1 2개, 1*2 2개, 2*2 1개 해서 총 3가지)에서 옆으로 1*2의 칸이 더 추가가 된 것이다. 이는 즉, (2 * 2의 바닥 채우기 + 1 * 2의 바닥 채우기) 순서와 (1 * 2의 바닥 채우기 + 2 * 2의 바닥 채우기) 순서를 합한 것이 총 2 * 3의 바닥을 채우는 방법이 되는 것이다. 이것을 일반화하면 i-2번째 ..

링크 https://www.acmicpc.net/problem/1463 난이도(solved.ac 참고) 실버3 풀이 재귀형태의 다이나믹 프로그래밍으로 해결하였는데, 이렇게 푼 사람들이 많은 걸 보면 그냥 이렇게 풀라고 낸 문제 같다. 여기에서 dp배열의 값들은 1로 만드는 데 걸리는 횟수들이다. 여기에서 우선 dp[i] = dp[i-1] + 1은 그냥 1을 빼줬을 때에 해당한다. 그냥 빼기만 하면 이전 횟수에 비해 1회가 추가되는 것이 끝이기 때문. 2와 3으로 나눠질 경우, 횟수가 1회 추가되었으므로 dp[i//3]이나 dp[i//2]의 값에 +1을 해줬다. 그리고 그 값을 기존에 있던 dp[i-1]+1의 값과 비교를 해주었다.

링크 https://www.acmicpc.net/problem/1300 난이도(solved.ac 참고) 골드3 풀이 처음 봤을 때 골드 3이라는 난이도를 보고서 당연히 쉽게 풀 수 있는 방법대로 풀면 안된다고 생각했지만 그래도 한번 해봤고 역시 메모리 초과가 떴다. 쉽게 풀 수 있는 방법이란 2중 반복문을 돌리면서 [i][j]에 i * j를 넣어주는 것. 그렇게 하면 절대 안된다. 애초에 범위가 10억개였기 때문에 이 문제는 배열을 직접 만들지 않고 풀어야 한다. n * n 배열에서 k보다 작은 수들의 갯수를 구하자. 갯수를 전부 더해준 값을 k와 비교해서 이분 탐색을 진행하면 된다. 5 * 5 배열에서 10보다 작은 수의 갯수를 구하면.. 1 * 1 ~ 1 * 5 (10 // 1과 n중 작은 값) 2 ..

링크 https://www.acmicpc.net/problem/2470 난이도(solved.ac 참고) 골드5 풀이 이분 탐색 또는 투포인터로 풀 수 있는 문제인데 나는 투포인터로 풀었다. 둘 중에 어느 것으로 풀어도 상관 없을 것 같긴 하다. 이분 탐색을 잘 썼다면 그쪽 코드가 좀더 간결했을 것이다. 이 문제의 핵심은 부분합을 계속 구해가면서, 기존에 있던 부분합의 절댓값보다 작은 경우(즉 0에 가까운 경우) 부분합에 들어가는 요소와 그 합을 바꿔주는 방식으로 풀어야 한다는 점이다. 우선 배열의 첫번째와 마지막 값, 그리고 그 두개를 더한 값을 ans라는 리스트에 넣었다. 반복문을 도는데, 당연히 시작점과 끝점이 같으면 안되므로 그부분은 반복문에서 먼저 넣어준다. 현재 ans에는 (첫째값, 마지막값, ..

링크 https://www.acmicpc.net/problem/2110 난이도(solved.ac 참고) 실버1 풀이 이분 탐색 문제를 풀면서, start와 end를 어떻게 정해야할지가 중요한 부분이라고 생각하게 되었다. 여기서 start와 end는 집의 위치가 아니라 간격의 최소값 최대값으로 하였다. 간격이 같아질 때까지 반복하는데, 일단 기본적으로 맨 앞 집에는 설치를 한다고 가정하여 count를 1부터로 놓고 시작하였다. 그리고 기준값(candidate)을 첫번째 집으로 놓고 시작했다. for문을 돌면서(첫번째 집 이후부터 집을 다 돌면서), candidate + mid의 값, 그러니까 기준값에서 중간값을 더한 값보다 그 다음 집이 더 멀다면? 그러면 이 집은 추가를 해줘야한다. 왜냐면 .. 최대거리..

링크 https://www.acmicpc.net/problem/2667 난이도(solved.ac 참고) 실버1 풀이 음.. 일반적인 BFS문제라고 생각한다. 전체에 대한 for문을 돌면서 1인 경우에 bfs를 시작했는데, 여러번 반복하지 않기 위해 while문 내부에서 해당 값을 0으로 바꿔버렸다. 이렇게 되면 한번 BFS가 끝났을 때 그 부분은 전부 0으로 바뀌면서 1을 찾는 for문 조건에 충족되지 않게 된다. BFS 함수 내부에서는, 미로 찾을 때처럼 nx, ny로 좌표를 통해서.. (방문하지 않았고 값이 1인 경우)를 찾아 큐에 더해주는 방식으로 진행했다. bfs 함수를 실행한 결과로 나온 count를 ans_list라는 리스트에 넣었고, 그 리스트의 길이와 가장 작은 값부터 순서대로 출력하게끔 ..

링크 https://www.acmicpc.net/problem/1744 난이도(solved.ac 참고) 골드4 추가로 시도해보면 좋은 반례 입력 6 1 1 1 1 1 1 추가로 시도해보면 좋은 반례 출력 6 풀이 이 문제를 풀 때 내가 기본적으로 생각했던 것 1. 양수는 1개 남을때까지 전부 2개씩 묶어서 곱해주고, 마지막 하나는 더해준다. 2. 음수는 역으로 sort한 뒤 전체 음수가 홀수개라면 1개 남을때까지 전부 2개씩 묶어서 곱해주고, 마지막 하나는 더해준다. 2-1. 짝수개라면 전부 묶어서 곱해준다. 3. 그리고, 매 if문이 끝날 때마다 두 원소를 모두 pop해줬고, 그에 맞춰 감소하는 빈도도 -2로 맞췄다. 왜냐면 매 반복문을 돌때마다 값이 두개씩 사라지니까. 4. 0은? 일단 고려 안했음 ..

링크 https://www.acmicpc.net/problem/2606 난이도(solved.ac 참고) 실버3 풀이 흠 ㅋㅋ 걍 인접리스트 만들고, BFS 돌리면서 큐가 있으면 1 더해주면 되는.. 쉬운문제였다. 근데 인덱스 에러가 나길래 왜 나지 했는데.. visited의 개수가 잘못되었었다. 기존 C에서 C+1로 바꿔주니 해결되었다.