오답 노트 & 새로 알게 된 점 이 문제는 이중 포문을 이용하여 배열의 값을 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 ..

오답 노트 & 새로 알게 된 점 처음에 이 문제를 접근할 때, 조건 2개를 계속 생각했다. 1. 가로수를 같은 간격에 심기 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

오답 노트 & 새로 알게 된 점 처음에 isConditionTrue를 작성할 때, 행, 열에서 검사하는 것은 쉽게 생각했지만 3*3일 때는 검사를 하기 위해선 총 9개의 범위를 나눠야 하는 생각이 들었다. 하지만 이 9개 범위를 다 나누는 것은 효율적이지 않고, 어떠한 방법이 있을 것이라 생각했다. 그래서 구글링을 하여 힌트를 얻었다. - 이러한 문제를 풀 때, 규칙성을 찾고 구현하는 실력을 쌓아야겠다. 처음에 backTracking을 돌릴 때, sdk ArrayList에 저장되어 있는 것을 어떻게 꺼내올지가 고민이었다. 이게 무슨 말이냐면, 내가 스도쿠를 입력할 때 숫자가 0 이면 따로 ArrayList에 저장을 했는데, 이 ArrayList 안에 있는 좌표를 어떻게 꺼내올까라는 것이 고민이었다. 반복..

오답 노트 & 새로 알게 된 점 문제를 처음 볼 때, StringBuilder를 사용해서 isConditionTrue를 만족하면 sb에 넣고, 틀리면 sb에 있는 제일 끝에 있는 문자를 지우려고 했다. 하지만 sb는 전역 변수로 사용해서 조건식에 넣을 때마다 무조건 문자를 넣게 되고, 삭제를 해도 그 문자 그대로였다. 그래서 코드를 싹 다 갈아엎고, 처음부터 시작했다. int형으로 선언할지, String으로 선언할지 고민하다가 문제에서 N이 80 이하라고 하여, int형으로는 80자리를 받을 수 없어 String을 이용하기로 했다. 그리고 백트래킹을 무조건 하나를 추가하고 검사하고 다시 하나를 삭제한다. 이런 생각은 안 갖는 게 이 문제를 통해 알게 되었다. 나는 백트래킹이 무조건 하나를 추가하고 다음으..

오답 노트 & 새로 알게 된 점 처음 접근 방식은 백트래킹을 이용하여 치킨집을 0으로 만들고 다시 2로 설정해서, 거리를 구하려고 했다. 하지만 여기서 어떻게 제일 가까운 거리를 구해야 할지 전혀 방법이 떠오르지 않았다. 물론, 포문을 여러 개 사용하여 거리를 구할 수 있지만 시간 복잡도를 보니 무조건 TLE가 나올 것 같아 새로운 방법을 생각해보았다. 하지만 방법이 떠오르지 않아 구글링을 하여 힌트를 얻었다. 이러한 거리 계산이 나온다면 Point 클래스를 선언해주는 방법을 생각하자. 그리고 꼭 이차원 배열 안에서 생각하지 말자. 예를 들어 chicken과 home ArrayList를 만들어주어 좌표를 저장하는 방법. 어떻게 이런 생각을 하는지 정말 기발하다고 생각했다. 그리고 입력 순서대로 chick..