오답 노트 & 새로 알게 된 점 문제의 식을 써보면 G + 기억몸무게^2 = 현재몸무게^2 으로 나타낼 수 있다. 따라서 G = (현재몸무게^2) - (기억몸무게^2) = (현재몸무게+기억몸무게) * (현재몸무게 - 기억몸무게) getMul 투포인터를 이용하여 곱이 G가 되는 두 수를 구합니다. get getMul을 통하여 얻은 두 수를 가지고 나눠 떨어지는지 확인합니다. max = (현재 몸무게 + 기억 몸무게) min = (현재 몸무게 - 기억 몸무게) max + min = 2 * 현재 몸무게 max - min = 2 * 기억 몸무게 둘 다 2로 나누어 떨어지지 않으면 자연수 G가 나올 수 없기 때문에, (max + min) % 2 == 0 && (max-min) % 2 == 0 가 필요하다. 현재 ..

오답 노트 & 알게 된 점 문제를 보면 가중치가 1이라고 했으므로 최단 경로를 구하는 알고리즘 중 BFS를 사용하면 된다고 생각했다. 문제에서 건물이 2개가 지어지고, N이 최대 100이다. 따라서 시간복잡도는 100C2 * 100 * 100으로 1억이 안된다. 즉, N개 중에 2개를 중복X, 순서X인 조합을 구하여, 2개의 노드에서 나머지 노드들 간의 거리를 구하면 된다. static void dfs(int start, int cnt) { if(cnt == 2){ bfs(); return; } for (int i = start; i sum){ ans = sum; build1 = select[0]; build2 = select[1]; } 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

오답 노트 & 새로 알게 된 점 이 문제는 전에 풀었던 불!과 비슷한 단계형 bfs 문제다. 파도가 한 번 칠 때마다 모래성을 부수고 완전히 온전한 상태가 될 떄까지 파도의 횟수를 구하는 것이다. 처음에 문제를 이해하는데 어려움이 있었다. 온전한 상태가 무슨 말일까? 아무리 파도가 쳐도 무너지지 않는 모래성이다. 9는 무조건 온전한 상태이며, 주위에 있는 9의 개수에 따라서 8, 7 등 다른 숫자들도 온전한 상태가 될 수 있다. 처음 문제 풀이 처음 문제를 풀 때는 bfs를 돌릴 때, 9나 . 이 아닌 숫자들을 다 넣어주었다 그리고 각각 위치에서 8방향으로 탐색한 뒤, 부숴질 모래성이면 nonstable 배열에 저장하여 위치를 저장한 뒤에 bfs가 끝나면 그 때 . 을 넣어주었다. 하지만 위와 같이 문제..

오답 노트 & 새로 알게 된 점 이런 유형의 문제를 단계별 bfs문제라고 생각한다. 한 번에 bfs를 돌려서 문제의 답을 구하는 것이 아니라, 한 타임 돌리고, 또 한 타임 돌리면서 답을 구하는 것이다. 이 문제도 보면 불이 이동하고 -> 지훈이가 이동한다. 이게 한 사이클이다. 문제에서 동시에 이동한다고 했으니, 불이 먼저 이동할까 지훈이가 먼저 이동할까를 생각해봤다. 동시에 이동한다고 했을 때, 불이 있는 곳에 지훈이가 가면 어떻게 될까 라는 생각을 했고, 이로 인해 불이 먼저 움직여야겠다는 결론을 내렸다. 불이 이동하는 bfs, 지훈이가 이동하는 bfs를 따로 만들어줬다. 둘의 bfs에는 공통점이 있다. 각각의 큐가 empty 될 때까지 돌리는 것이 아니라, 한 사이클만 돌린다. 즉, 현재 시점에서..

오답 노트 & 새로 알게 된 점 풀이는 BFS를 이용하여 최소 경로를 구했다. 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸까지 범위를 모두 탐색하면서 1이 있는지 없는지 판단했다. 처음에는 bfs를 아래와 같이 짰다. for (int i = 0; i < 4; i++) { int X = info.x + dx[i]; int Y = info.y + dy[i]; if(!isRangeTrue(X, Y)) continue; if(visit[X][Y]) continue; q.offer(new Info(X, Y, info.cnt + 1)); visit[X][Y] = true; } static boolean isRangeTrue(int x, int y) { int X = x + hei - 1; int Y = y + wid..

오답 노트 & 새로 알게 된 점 처음 풀이 빨간색 1을 만날 때 모든 방향을 다 조사해야하나 라는 생각이 들었다. 하지만 1이 있는 곳 모두 완탐을 하게 되면 오른쪽 아래(초록색) 부분만 하면 된다는 생각을 했다. 완전 탐색을 하는데 처음엔 bfs를 사용하여 구현해보려했다. 하지만 색종이를 붙였다 떼었다 하는 과정이 필요할 것 같아서 백트래킹까지 생각했다. A배열을 건들지 않으면서 백트래킹을 진행했다. checkPaper메서드에서는 범위를 넘지 않고, A배열의 값은 1이면서 visit하지 않은 곳이 존재하면 색종이를 붙일 수 없다 판단했다. 하지만 시작점을 넣고 그 다음점을 어떻게 찾을지 계속 고민했다. 왜냐하면 위에서 완전 탐색을 할 것이기 때문에, (1,1)에서 dfs를 시작하고 나서 그 다음엔 처음..

오답 노트 & 새로 알게 된 점 문제를 풀 때, 시간 제한으로 Stack을 사용해야겠다라는 생각까지 들었다. 그러나 구현 부분에서 막혀 풀지 못했다. 처음엔 stack의 개수가 (bomb길이 - 1) 일 때 길이 만큼 pop + 이제 넣을 문자 와 bomb을 비교하였다. 그러나 위와 같이 풀게 된다면 stack Size가 bomb의 길이보다 커지게 될 때 비교할 수 없게 된다. 또한, Stack의 참조형을 String으로 하게 되면 메모리 초과가 난다. 그래서 Character로 바꾸었더니 AC를 받았다. 아마 문제의 메모리 제한이 타이트해서 String을 하게 되면 틀리는 것 같다. stack은 index의 접근이 안되는 줄 알았다. 그러나 get이라는 메서드가 있었고 index를 통해 stack에 접..

오답 노트 & 새로 알게 된 점 처음에 로봇을 움직일 때 회전과 이동을 같이했다. 이동을 하면서 회전을 같이하면 코드가 복잡하지 않고, 문제를 해결하는데 영향을 끼치지 않을 거라 생각했다. 하지만 이동과 회전을 같이하게 된다면 목적지에 도착했을 때, 최소 거리라는 보장을 할 수 없다. 풀이 1 ~ 3을 차례대로 이동하고 큐에 넣기 2나 3을 이동할 때, 중간에 1이 있지만 뛰어넘을 경우를 대비하여 순차적으로 이동하면서 1을 만나면 break함. 이동하지 않고 방향만 바꿔주고 큐에 넣기 180도 회전할 경우에는 cnt가 2 증가하기 때문에 규칙성을 찾음 180도 회전할 경우는 동, 서 와 남, 북 이므로 둘을 더했을 땐 고유하게 3과 7의 값이 나오게 됨 코드 1 2 3 4 5 6 7 8 9 10 11 1..

오답 노트 & 새로 알게 된 점 처음 문제 접근할 때, 백트레킹을 사용하여 조건을 세우면 문제가 풀릴 것이라고 생각했다. 그러나 아래와 사진과 같이 T자 형이나 +자 형은 백트래킹으로 구하는데 어려움이 있다. 그러면 어떠한 방법을 사용해야할까 생각을 했다. 문제에서 25명의 학생이 고정이라고 했으므로 각각의 학생에게 0~24의 번호를 부여한다. 중복을 허락하지 않은 조합을 이용하여 25명 중에 7명을 뽑고, 7명이 모두 이어져있는지 bfs로 확인하면 된다. 그렇다면 여기서 0~24를 어떻게 행과 열로 나타낼 수 있을까라는 생각을 해야한다. 위의 사진과 같은 테크닉을 사용하면 행과 열로 나타낼 수 있다. 이 문제에서 가장 중요한 방법이라고 생각이 든다. 그래서 bfs조건 중에 방문했냐, 범위를 넘느냐 조건..

오답 노트 & 새로 알게 된 점 뱀 문제를 읽자마자 Deque가 떠올랐다. 시뮬레이션은 문제를 정말 잘 읽고 요약하는 습관이 필요한 것 같다. 요약하면서 어떻게 구현하면 좋을지 생각을 같이 하는 연습이 필요하다. 문제는 아래와 같이 정리하면 된다. 끝날 경우 2번을 보면 자기 자신과 몸이 부딪힐 경우이다. 이 때는 현재 머리를 놓은 위치를 dq의 element들과 비교해주면 된다. order 배열은 시간에 따라 방향이 바뀌는 값을 저장한다. D는 +1, L은 -1로 생각하여 order 배열에 넣어준다. 방향은 아래의 사진과 같이 생각하면 된다. 사진과 맞춰 dx, dy 배열도 방향 설정을 해주어야한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

오답 노트 & 새로 알게 된 점 처음에 문제를 잘못 이해하여 엉뚱하게 풀었다. 1초마다 미세먼지 확산 후 공기청정기가 작동되는데, 나는 처음에 미세먼지 확산이 되고 T초동안 공기청정기를 돌렸다. 즉, 미세먼지 확산되고, 공기청정기 작동후에, 또 다시 미세먼지 확산되고 공기청정기를 돌려야한다. 전체적인 흐름은 미세먼지 큐에 넣기 -> 미세먼지 확산 -> 공기청정기 돌리기 이다. A배열에서 양의 정수를 모두 큐에 넣어준다. real 배열을 이용하여 미세먼지를 확산시킨다. A배열로 미세먼지를 확산시킬 때, 중복으로 더해지는 값이 있을까봐 real 배열을 사용했다. 제일 중요한 rotate 메서드이다. rotate메서드는 크게 공기청정기의 윗 부분, 아랫 부분으로 나눴다. 그리고 방향으로는 -->, = 1; i..

오답 노트 & 새로 알게 된 점 처음에 완전탐색을 생각했다. 그러나 N이 최대 15로 2^15 * 2^15 = 2^30으로 완탐하면 무조건 TLE가 난다. 시간 복잡도를 줄일 방법이 없을까 생각을 했다. 크기가 2*2만큼 커지기 때문에 2*2를 재귀를 이용하여 줄이면서 짜면 될 것 같았다. 문제를 풀면서 생각해야할 점은 두가지이다. 1. 어느 사분면에 속해있는가 2. 2*2만큼 크기를 줄일 때, 좌표는 어떻게 변화되는가? 1번을 알아야하는 이유는 사분면마다 방문횟수를 더해주는 값이 다르기 때문이다. 1번 해결방법은 문제에서 찾을 수 있었다. r과 c가 0부터 시작한다고 했다. 즉, 주어진 한 변의 길이를(2^N) 절반으로 나눴을 때 왼쪽, 오른쪽에 있는지 구분만 하면 된다. N = 4이면 0, 1은 왼쪽..