오답 노트 & 새로 알게 된 점 해당 문제를 풀면서 중요한 부분을 배웠다. 알고리즘은 절대로 정형화해서 풀지 말자. 원래 일반적으로 dfs를 풀 때, dfs함수를 호출하고 방문 체크를 해주는데 해당 문제는 그러면 안됐다. 예제2) 1. 1 -> 4 -> 5 -> 1 처럼 cycle이 있는 것은 1 4 5에 모두 1이 있어야하지만, 2. 2 -> 7 -> 3 처럼 cycle이 없는 것은 7 3에만 1이 있어야한다. 그래서 위와 같이 일반적으로 dfs를 푸는 것처럼 바로 방문체크를 하게 된다면, 1번은 맞게 되지만, 2번에서 2도 1이 된다. 그래서 틀리게 된다. 해결 방법은 dfs를 재귀 호출할 때 방문 체크를 해주면 된다. 두 가지 방법을 사용하여 문제를 풀었는데, 위 얘기는 1번 코드와 관련있다. 2번..

오답 노트 & 새로 알게 된 점 전에 풀었던 문제는 일차원 배열로 해결했다. 이번에는 이차원 배열을 이용하였다. 해당 문제는 강의를 통해 풀었던 문제이다. 이런 생각은 어떻게 할까,,, 라는 생각이 들었던 문제이다. dp[i][0]은 i-1번째 계단을 밟지 않고 i번째 계단을 밟을 경우, dp[i][1]은 i-1번째 계단을 밝고 i 번째 계단을 밟을 경우이다. 그래서 dp[i][0]을 구하기 위해서는 i-1번째 계단을 밟지 않을 경우에는 연속 세 계단을 어차피 오를 수 없기 때문에 dp[i-2][0]과 dp[i-2][1]중 최댓값을 고르면 된다. dp[i][1]은 i-1번째 계단을 밟을 경우이므로, i-2번째 계단을 밟으면 안 된다. 그래서 dp[i-1]계단에서 i-2계단을 밟지 않아야 하므로, dp[i..

오답 노트 & 새로 알게 된 점 해당 문제는 규칙성을 찾기 너무 어려웠다. 뭔가 알 것 같으면서도, 보이질 않았다. 26이라는 숫자가 중요한 것 같은데 어떻게 구현할지 생각이 1도 안 났다. 처음에 풀 때는, 반대로 풀었다. 즉, 예로 25114를 보면 4 -> 14 -> 114 -> 5114 -> 25114 이렇게 접근했다. dp를 배울 때, dp[N]이 원하는 답이라 하였는데, 위의 방법처럼 풀게 되면 반대로 풀게 되어 dp[1]인가 여기를 구해야했었다. 그래서 규칙성은 보이는데 어떻게 구현할지를 모르겠다고 말한 것이다. 구글링을 하여 힌트를 보니, 2 -> 25 -> 251 -> 2511 -> 25114로 접근하여 dp[N]이 원하는 답이 됐던 것이다. 규칙성은 숫자 하나를 비교하고, 그 다음에는 ..

오답 노트 & 새로 알게 된 점 오르막 수는 규칙성이 쉽게 보였다. 다만 이차원 배열을 사용해야 한다는 것을 늦게 알게 되어, 문제를 푸는데 시간이 좀 걸렸다. dp[i][j]라 할 때, i 길이 수에서 j 숫자로 시작하는 숫자들의 개수를 의미한다. 즉, dp[2][3]은 길이가 2인 숫자들 중, 앞이 3으로 시작하는 오르막 수들의 개수이다. 2자리 부분을 봐보자. 0으로 시작하는 곳은 1자리인 0~9가 반복, 1로 시작되는 숫자는 1~9, 2로 시작되는 숫자는 2~9 등등 된다. 3자리 부분에서는 2자리 총합부터 시작하여 점점 하나씩 빼게 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3..

오답 노트 & 새로 알게 된 점 이 문제를 풀려고 한 5~6시간 쓴 것 같다. 처음에 dp공부하는 것은 너무나 많은 생각과 시간을 투자한다. 하지만 중요한 부분이니 견디고 견뎌서 dp를 정복해야한다,, 그리고 문제 풀이에 매우 큰 도움을 주신 류호석님께 너무 감사한다,, 첫 번째, 문제 접근을 잘못하여 파티션을 제대로 나누지 못했다. 류호석님 dp강의를 보면 dp를 풀기 위해서는 파티션을 나눠야 한다. 하지만 문제에서 1+2+2, 2+1+2, 2+2+1은 항상 같은 값으로 나오기 때문에 처음 나는 중복된 것을 뺐다. 그래서 파티션을 나눠서 공통점을 찾으려는 과정에서 어려움을 겪게 되고, 찾지 못하게 된다. 그래서 질문을 하게 되었고, 위의 중복된 값을 같이 써야 한다고 말씀해주셨다. 왜냐하면 빼놓고 쓰게..

오답 노트 & 새로 알게 된 점 문제 점화식은 구글링을 통해 알 수 있었다,, dp는 너무 어렵다,, 초기값은 dp[0] ~ dp[5]까지 있었다. 여기서 dp[0]은 원래대로라면 0이지만, 위의 조건을 만족시키기 위해 1이라고 했다. 위의 조건을 만족시키기 위해 dp[0]을 1이라고 내 마음대로 설정해도 되냐고 물어보았다. 아무것도 안 더하는 방법이 있다고 생각하면 dp[0]은 1이 될 수 있다. 그래서 문제를 어떻게 설명하냐에 따라 풀이가 달라지는 것 같다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 package Dynamic_Programming; //BOJ 159..

오답 노트 & 새로 알게 된 점 해당 문제는 1, 2, 3 더하기 1을 풀면 똑같은 점화식을 가진다는 것을 알 수 있다. 하지만 이 문제의 함정은 n의 범위이다. 1에서는 아마 n의 범위가 11보다 작은 정수였는데, 해당 문제는 n이 1,000,000보다 작거나 같은 정수(양수)이다. 그리고 1,000,000,009로 나눈 나머지를 출력한다고 한다. 처음에 문제를 똑같이 풀 때에는 당연히 1과 똑같이 코드를 제출했다. 그냥 n의 범위가 다른가 보다 하고 말이다. 하지만 당연하게 틀렸습니다가 나왔다. 나는 저 10억으로 나눈 나머지를 출력한다 이 부분을 간과하였다. 이 말은 즉, 어디가 10억이 넘는 곳이 있다라는 말이었고, 배열의 범위를 int로 하면 안 되는 것이었다. 만약 점화식에서 dp[i-3], ..

오답 노트 & 새로 알게 된 점 문제를 처음에 접근할 때는 클래스를 구성해서 x, y좌표를 따로 저장한 뒤에 무조건 사다리를 건너야하며 등등 어렵게 생각을 했다. 그리고, 1~6일 때 모두 큐에 넣는다면 터질 것 같아서 도저히 풀이 방법이 생각나질 않았다. 그러나 구글링을 통하여 힌트를 얻었고, 문제를 풀 수 있었다. 이차원 배열을 사용하지 않고 사다리나 뱀이 있는 경우 시작점을 배열의 index, 도착점을 배열의 value로 설정한다. 그래서 해당 배열의 값이 0이 아니게 되면 도착점을 큐에 넣어준다. 사다리나 뱀이 없는 경우 그냥 count만 1 늘려준다. 오답 노트 & 새로 알게 된 점 ( 2021.10.24) 문제를 다시 풀어보았는데 틀렸다. 처음에 생각한 점이 뱀은 무조건 지나면 안된다였다. 주..

오답 노트 & 새로 알게 된 점 문제를 풀면서 처음에는 메모리 초과, 다음에는 시간 초과가 났다. 그래서 도저히 어떻게 풀지 감이 안 와서 구글링을 통하여 문제를 해결했다. 카테고리를 보니 DP와 BFS로 되어있었다. DP는 어떻게 사용되는지 보였다. 그러나 엥? BFS는 어디있는거지라는 생각을 했다. 아마 문제를 풀 때 최소를 구하기 위한 탐색 방법 중 하나인 BFS 모양(?)과 비슷하여 분류가 그렇게 된 건가 싶었다. 나는 BFS를 생각하면 BFS == 큐라고 생각하고 있었기 때문이다. 그런데 이 문제를 보면서 꼭 큐를 사용해야만 BFS 다는 아닌가 보다 라는 생각이 들었다. 난 DP를 제대로 공부하지 않고, 단지 메모이제이션(?) 그 부분만 알고 있다. 전에 했던 것을 저장하여 앞으로 나아가는 것이..

오답 노트 & 새로 알게 된 점 이 문제는 BFS의 제대로 된 개념만 알면 쉽게 풀 수 있는 문제이다. outside는 첫 번째 행이므로 입력을 받으면서 큐에 첫 행을 모두 집어넣는다. 그리고 bfs를 돌리고 inside는 마지막 행으로, 마지막 행이 하나라도 visit에서 true가 있다면 침투를 했다는 것이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76..

오답 노트 & 새로 알게 된 점 처음에 문제 접근하여 코드를 작성했을 때, 마지막 예제를 고려하지 않았다. 그래서 해당 index에 접근하면 무조건 index의 day만큼 다음 index를 접근하게 했다. 그러나 4번 예제에서는 1번 날, 6일 날, 8일 날 접근하여 총 90이 나온다. 제일 이해하지 못했던 것이 과연 N+1날에는 상담을 할 수 있는 것이냐 없는 것이냐가 헷갈렸다. 예제 2번을 보면, 답이 55이다. 그렇다면 1 ~ 10을 모두 더했다는 것이다. 그러면 마지막 9번째 index는 1일이 걸리는데, 1일은 그다음 N+1번째까지 포함한다는 뜻이다. 그래서 N+1날까지 상담을 진행하는 뜻인 것 같다. 문제 풀이는 재귀를 사용하여 풀었다. 다른 블로그들을 보면 dp로 풀었는데 아직 dp쪽은 공부..

오답 노트 & 새로 알게 된 점 해당 문제는 전에 풀었던 카드 놓기와 비슷하지만, 카드 놓기는 중복을 제외한 순열이었다면, 이번 문제는 중복 가능한 순열이다. 그래서 if(visit[i]) continue 구문만 빼준다면 중복 가능한 순열이 된다. 똑같은 방식으로 String형으로 set에 중복 가능한 순열들을 모아놓은 뒤에 list에 Integer형으로 변환하여 저장한다. 그리고 max값을 지정하여 if 조건식을 만족하게 한 뒤 max 값을 출력하면 된다. 하지만 여기서 중요한 부분이 있다. 위와 같이 풀면 perm1만을 포함하는데, 여기서 반례가 생긴다. 14 2 7 8 을 하게 되면, N은 두자리 숫자인데 값은 8이 나와야 한다. 반례가 생기는 것이다. 그래서 perm2라는 메소드를 새로 만들어 N..