오답 노트 & 새로 알게 된 점 해당 문제는 약 2, 3일 고민하면서 풀었던 것 같다. 물론 혼자 힘으로 풀지 못하고, 오카방에 여쭤봐서 힌트를 얻고, 문제를 해결했다. 처음 문제 접근은 bfs, dfs에서 고민을 당연하게도 했다. bfs를 진행하다가 뭔가 아닌 것 같아서 dfs를 사용했다. 그래서 처음에는 dfs를 들어갈 때마다 새로운 visit배열을 만들고(왜냐하면 먹었던 고구마를 또 먹을 수 없기 때문) 이상하게 코드를 짰다. 도대체 어떻게 하면 먹었던 고구마를 다시 먹지 않으면서 그 길을 지나갈 수 있을까? 라는 생각을 했다. 나는 항상 백트레킹이나 dfs를 풀면 무조건 visit 했으면 continue 하고 봐 이런 식이였다. 그러나 이 문제를 통해 틀에 박힌 생각을 깼다. 이 문제에서는 vis..

오답 노트 & 새로 알게 된 점 해당 문제를 이해하는 순간 제일 중요한 점 3가지를 깨달아야 한다. 노드들이 사이클을 이루는 순간 같은 팀이 됨 한 사람당 지목할 수 있는 팀원은 단 한 명 자기 자신을 선택할 경우 바로 처리해주기 ex) 1 -> 3 2 -> 1 3 -> 3 4 -> 7 5 -> 3 6 -> 4 7 -> 6 지나왔던 경로(팀원 수를 구하기 위해)를 알기 위해 순서가 보장되고 동적인 ArrayList를 사용하였다. 4 -> 7 -> 6 -> 4로 사이클이 이루어질 때, ArrayList에는 4, 7, 6이 저장되어있다. 그래서 재방문한 값의 index 위치를 찾아 해당 위치부터 ArrayList.size()까지 빼주면 지나왔던 경로들의 개수를 알 수 있다. 그래서 result값에서 해당 c..

오답 노트 & 새로 알게 된 점 처음에 이 문제를 봤을 때, 0과 1을 나누면서 어떻게 처리해줘야 할지 생각을 많이 했다. value가 1일 때, 주변에 0이 하나라도 있으면 0이 되고, value가 0일 때, 주변에 1인 index를 0으로 만들어준다. 이런 식으로 생각을 했는데, 중앙에 딱 반례가 바로 생기는 것이다. value가 0일 때, 주변에 1이 있는데 1시간 뒤에 녹지 않고 있다. 그래서 계속 어떻게 풀어야 할지 고민을 했다. 그래서 0,0부터 시작해서 bfs를 사용하여 제일 바깥 쪽 공기를 -1로 만들어준 다음, -1을 만난 1만 0으로 바꾸려고 했다. 그러나 뭔가 안될 것 같아 하지 않았다. 그래서 하루정도 생각을 했다. 그래도 문제가 풀리지 않아 힌트를 보았다. 힌트를 보니 두 번째 생..

오답 노트 & 새로 알게 된 점 첫 그리디 문제이다. 이 문제는 그냥 쉽게 생각했다. 오름차순으로 입력해주기 때문에 제일 뒤에서부터 K원보다 크면 넘어가면서 더 작은 가치의 동전으로 넘어가고, K원보다 작거나 같으면 빼주면서 다시 while문을 돌렸다. 코드 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 package Greedy; import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br ..

오답 노트 & 새로 알게 된 점 이 문제는 이중 포문을 이용하여 배열의 값을 0으로 바꿨다가 bfs 돌리고 다시 1로 바꾼다면 TLE가 뜬다. 그래서 다른 로직이 전혀 떠오르지 않아 구글링을 하여 힌트를 얻었다. 지금 이해가 약 95% 되었지만, 5% 부분은 visit에서 3번째 index가 0일 때, 1일 때를 다른 차원으로 생각해야 하는지이다. 이 부분 때문에 4시간 동안 구글링을 하고 했지만, 아직까지 이해가 되질 않는다. 나중에 꼭 다시 풀어볼 것이다. 나중에 풀 때 참고하면 좋을 것 같다 https://www.acmicpc.net/board/view/27386 코드 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 2..

오답 노트 & 새로 알게 된 점 문제를 자세히 읽고 이해했다면, 1 2 3을 색칠할 때, 2는 1과 3 색깔과 같을 수 없다. 즉, 1과 3은 색깔이 같아도 된다는 말이다. 그래서 처음에는 위에서 아래로 문제를 읽었다. 즉, 1은 2,3을 가고 또, 2는 1,3을 가면서 규칙성을 찾아보려고 했다. 그래서 중복이 있는 것 같기도 해서 4번째까지 손으로 표를 작성해서 만들어보았는데 점점 가지 수가 많아지면서 규칙성을 찾기 어려웠다. 그래서 문제를 어떻게 접근하는지 힌트를 찾아보았는데, 아래에서 위로 보면 문제가 바로 쉬워진다. 두 번째 행에서(코드에서는 i = 1일 때) 빨간색을 칠할 경우, 그 전 행(첫 번째 행)에서는 빨간색을 칠할 경우엔 j가 1,2만 접근 가능하고, 초록색을 칠할 경우엔 j가 0, 2..

오답 노트 & 새로 알게 된 점 DP를 세 문제를 풀어보니 어떻게 푸는지 감이 오는 것 같다. 항상 문제를 풀 때, 3~4번째까지는 규칙성을 찾기 위해, 나열하는 것이 중요하다. 이 문제를 예로 들면, 7 10 = 7 + 3 count[1][0] = triangle[0][0] + triangle[1][0] 15 = 7 + 8 count[1][1] = triangle[0][0] + triangle[1][1] 18 = 7 + 3 + 8 count[2][0] = count[1][0] + triangle[2][0] 11 = 7 + 3 + 1, 16 = 7 + 8 + 1 count[2][1] = Math.max(count[1][0] + triangle[2][1], count[1][1] + triangle[2][1..

오답 노트 & 새로 알게 된 점 처음에는 문제를 이런 식으로 접근했다. 그러나 연속 3계단을 어떻게 제외할 방법이 생각나질 않았다. 그래서 구글링으로 힌트를 얻어 문제를 해결했다. 힌트를 보면서 어떻게 이런 규칙을 찾을 수 있지라는 생각이 들었다. dp는 특정 공식이나 풀이 방법이 있는 것이 아니라 반복된 연산을 피하기 위해서 사용하는 알고리즘이라 생각한다. 그래서 규칙성 찾는 것도 필요하다. 이 문제를 통해 아 이런 규칙도 있구나라는 경험을 하게 됐다. 사용 개념 DP 코드 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 package Dynamic_Programming; import java.u..

오답 노트 & 새로 알게 된 점 처음에 피보나치 문제여서 쉬울 줄 알았다. 그러나 일반적으로 많이 사용하는 재귀 함수를 통해 이 문제를 풀게 되면 TLE가 나온다. 그래서 시간제한이 0.25초인 것을 보고, 절대 재귀 함수를 사용하면 안 된다라는 생각이 들었다. 그래서 포문을 사용하여 문제를 해결해야 한다. 피보나치는 f(n) = f(n-1) + f(n-2)이다. 하지만 일반적인 숫자들 말고, 0과 1도 이 규칙성을 따른다. 그래서 이차원 배열을 만들어 최대 N이 40이기 때문에 40까지 0과 1의 개수를 다 구한 뒤, 입력 값에 맞게 0과 1의 개수를 출력했다. 사용 개념 피보나치, dp 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

오답 노트 & 새로 알게 된 점 이 문제는 옛날에 dfs를 이용하여 문제를 해결했다. 그래서 이번에는 bfs를 이용하여 문제를 풀어보았다. 문제를 풀면서 조금 애먹은 부분은 bfs 메소드를 구현하는 중에 while문에서 큐에 element를 언제 집어넣고 언제 빼는지, 또, dx[i]와 dy[i]를 언제 더해주는지 순서가 매우 헷갈렸다. 그러나 bfs의 개념을 제대로 생각하여 구현했다. 그리고 컴포넌트의 개수와 각 컴포넌트에는 몇 개의 element가 있는지 이것들을 어디에 저장해야지 출력 순서가 엇갈리지 않게 출력할 수 있을까라는 생각이 들었다. 그래서 배열 생각을 했다. 그러나 ArrayList를 사용하여 큐에 element가 추가될 때마다 count++를 해주고, bfs메소드가 끝나면 ArrayLi..

오답 노트 & 새로 알게 된 점 처음에 이 문제를 풀 때, 투 포인터라는 개념을 몰랐다. 그래서 에라토스테네스의 체를 이용하여 visit배열에 소수인 부분을 true로 하고, ArrayList에 소수인 index만 넣었다. 그리고 이중 포문을 이용했지만, n이 4,000,000이어서 당연하게 TLE가 날 것이라 생각하고 제출을 했다. 당연하게 TLE가 났다. 그래서 구글링 하여 힌트를 얻었고, 투 포인터라는 개념을 새로 알게 되었다. 다음번에 투 포인터에 대해 자세히 다뤄볼 것이다. 투 포인터 개념 설명 : blog.naver.com/PostView.nhn?blogId=kks227&logNo=220795165570&parentCategoryNo=&categoryNo=299&viewDate=&isShowP..

오답 노트 & 새로 알게 된 점 이 문제를 풀면서 다시 한번 에라토스테네스의 체에 대해 공부하게 됐다. 또한, n의 최댓값이 1,000,000이라고 했다. 그러면 visit배열의 크기를 1,000,001로 해주고, 소수 판별하는 이중 포문도 범위를 1,000,000까지 해줘야 한다. 제곱 수까지 범위를 구해야 한다고 생각하여 처음에 1,001까지 선언해줘서 런타임 에러가 났다. 그리고, printPrimeSum 메소드에서 인자로 받는 num부터 탐색하면 된다. 이것 또한 1,000,000부터 시작해주어 TLE가 났었다. 사용 개념 에라토스테네스의 체 코드 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 ..