알고리즘/BOJ 썸네일형 리스트형 2225번 2225번 - 합분해 처음에 0부터 N까지 수를 하나씩 뽑아보면서 완전 탐색을 실행하였다. 그러다보니 N의 K제곱이 되어서 너무나 많은 시간이 소요되었다. 그래서 DP로 구현하였다. 완전 탐색 할때 2차원으로 풀게되어 캐시 값도 이차원 배열로 지정하여 풀었다. (일차원으로 풀어보려고 했지만, 정보가 부족해서 캐시에 담을 수가 없었다. 일차원으로 궁금해서 풀어보려고 노력했지만 난 실패) D[K][N] = K개를 뽑아서 N을 만드는 경우의 수 라는 점화식을 세우고 D[K][N] 에서 어떤 수 A (단, A는 0~N 사이의 값) 을 뽑았다고 했을 때, D[K][N} = D[K-1][N-A] 가 된다는 점을 고려해서 문제를 풀 수 있었다. 근데 사실 아직 까지도 기저 사례를 명확히 하지 않아 몇번을 수정하는 안.. 더보기 9461번 9461번 - 파도수열 D[N] = N번째 삼각형의 변의 길이 이 문제를 풀기 위해서는 규칙을 찾아야했다. 처음에는 도형적인 측면에서 그룹핑을 하다가 잘 안되는 것을 발견하고 몇번째 삼각형이 몇번째에 영향을 미치는가 보기 위해서 하나씩 적어가면서 규칙을 찾기 시작했다. N이 1~4일 때는 규칙이 발생하지 않지만 N=5일 때부터 규칙이 발생하는 것이 보였다. 그림으로 찾는게 더 쉽다. N=5일때는 N=4일때와 N=0일 때의 변의 합이 되고 N=6일때는 N=5일때와 N=1일 때의 변의 합이 답이 된다. 이를 통해서 D[N] = D[N-1] + D[N-5] 라는 식을 도출해낼 수 있었다. (단, N이 5 이상일 때) 그래서 N 이 0~4 까지의 값은 따로 표현을 해 주었다. 하지만! 평상시처럼 int형을 쓰고.. 더보기 2133번 2133번 - 타일 채우기 D[N] = 3 x N 타일을 1 x 2 , 2 x 1 타일로 채우는 방법의 갯수 우선 이 문제의 경우 N의 최대값이 30이기 때문에 완전탐색으로도 정답이 나온다. 그래서 완전탐색으로 풀고, DP로 한번 더 풀어보았다. 그래서 N일 때 경우의 수를 따져보면 3 x 2 블럭을 만드는 경우와 3 x 4 , 3 x 6 , 3 x 8 , ... 3 x n 의 블럭을 만드는 경우로 나뉘어 질 수 있다. 나의 실수 => 처음에 3 x 2 와 3 x 4 로 만드는 블럭만을 생각해서 많은 케이스를 빼먹었는데 3 x 6, 3 x 8 블럭도 ... 3 x n 블럭도 모두 다 달라서 확인해야 했다. 그래서 따져보면 3 x 2 블럭을 만드는 방법은 3가지, 3 x n (단, n은 2가 아닌 짝수) .. 더보기 1699번 1699번 - 제곱수의 합 1.완전탐색 코드 - 시간 초과2. DP 코드 - 시간초과3. DP 코드 - 정답코드 D[N] = N을 제곱수의 합으로 나타낼 때, 최소갯수. 처음엔 완전 탐색을 통해서 풀었고, 역시나 시간 초과가 났다. 그리고 두번째로 DP 를 통해서 풀었는데 오류가 두가지가 생겼다. 그 두가지 모두 for 문 상에서의 코딩방식에 의해 생겼다. 1. 불필요한 범위를 계산함에 따라 int형 정수의 범위를 초과하는 수가 생기는 것을 인지하지 못했다. 2. 첫번째 문제점을 인지하고 고쳤으나, 불필요한 범위 때문에 시간초과가 발생하였다. go() 함수에서의 for문에서 문제가 발생하였음.처음에는 i * i 의 값이 만약 n 값이 100000일 경우 int 값을 벗어나는 것을 보고 오류 고쳤다 ! 하.. 더보기 2579번 2579번 - 계단 오르기 D[N] = N번째 계단을 오르는 최대 값 N번째 계단을 오르는 방법은 조건에 따라 두가지가 된다. 1. N-2칸에서 2칸 점프하여 오르는 경우.2. N-1칸에서 1칸 점프하여 오르는 경우. 하지만 2번째 경우일 때는 문제의 조건에 따라 연속된 3칸을 밟으면 안되므로N-3칸에서 N-1칸으로 2칸 점프한후, N-1칸에서 N칸으로 1칸 점프해야 한다.(N-2칸에서 N-1칸으로 1칸 점프한후, N-1칸에서 N칸으로 1칸 점프하는 경우 조건에 위배된다.) 따라서 D[N] = max(D[N-2]+stair[N] , D[N-3] + stair[N-1] + stair[N]) 이라는 점화식이 완성된다. 1달 전에 혼자 풀었을 때는 2차원 DP로 풀었는데 다시 풀어보니 그럴 필요까진 없었던 문.. 더보기 1912번 1912번 - 연속합 문제의 크기가 커서 완전 탐색 보다는 바로 DP로 풀어야 겠다고 생각했다. 점화식D[N]은 N을 마지막 수로 하는 부분수열의 최대 연속 합. 점화식을 풀면서 D[N]=max(A[N],maxsum(n-1)+A[N]); 을D[N]=max(D[N],maxsum(n-1)+A[N]); 과 계속 헷갈려서 풀었다. D[N]을 만드는 방법은 연속된 합일 때, 혹은 N번째 자릿 수 하나인 A[N]일 때 두가지 이므로 다음부터는 잘 따져서 생각해봐야 겠다. 이 문제를 풀면서 내 실수 및 중요한 점을 발견했다. 1. 분명 수열에는 음수가 존재하는데, 너무 문제 풀기만 하다 보니까 또 문제를 제대로 읽지않고 양수만으로 계산하여 비교할 ans , 배열 D 값들을 0으로 초기화 하다 보니 제대로 된 값이 처.. 더보기 11054번 11054번 - 가장 긴 바이토닉 부분 수열 D[N] N을 제일 끝으로 하는 감소하는 가장 긴 부분 수열의 길이U[N] N을 시작으로 하는 감소하는 가장 긴 부분 수열의 길이 로 점화식을 세웠다. 증가하는 가장 긴 부분 수열의 길이를 구하는 문제 11053번과감소하는 가장 긴 부분 수열의 길이를 구하는 문제 11722번의 짬뽕이라고 생각하고두 문제를 합쳐서 풀었다. goUp()과 goDown() 함수를 나눠서 각자 다른 값을 구하도록 하였고,중복되는 값 1개를 정답에서 빼주면서 정답을 구했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364.. 더보기 11722번 11722번 - 가장 긴 감소하는 부분 수열 D[N]을 N번째 자리 수를 포함하는 가장 긴 감소하는 부분 수열의 길이 로 점화식을 세웠다. 11053,11055 번과 아주 유사한 문제. 앞의 문제들은 완전 탐색 코드를 아래와 같은 방식으로 안 풀었지만 이건 이렇게 풀어봄. 123456789101112131415161718192021222324252627282930313233343536373839#include#includeusing namespace std; int A[1001];int ans;void go(int n,int len){ ans = max(len, ans); for (int i = 1; i A[n]) { go(i, len + 1); } } return; }int main(){ int N; .. 더보기 이전 1 ··· 34 35 36 37 38 39 40 다음