오답 노트 & 새로 알게 된 점 이 문제는 규칙성이 중요하다. 제일 처음 시작한 문자가 B일 경우와 W일 경우 아래와 같은 규칙이 나타난다. 홀수 + 홀수 = 짝수 홀수 + 짝수 = 홀수 짝수 + 짝수 = 짝수 처음 시작 문자가 B일 때 생각해보자. 홀수일 경우에는 W가 와야하고, 짝수일 경우에 B가 와야한다. 그래서 i+j가 홀수인데 W가 아니면 cnt를 늘리고, i+j가 짝수인데 B가 아니면 cnt를 늘린다. 이 때, 처음 시작 문자가 W일 때와 반대이기 때문에 64 - cnt를 하면 W일 때를 구할 수 있다. 그래서 cnt와 64-cnt 중 최소값을 리턴하면 된다. 그리고 모든 행과 열을 탐색하면서 최솟값을 찾으면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

오답 노트 & 새로 알게 된 점 문제를 보면 A에다가 앞, 뒤로 a~z까지 일일이 한 개씩 삽입한 뒤, 비교하려면 코드가 더러워지고 엄청 복잡할 것 같아서 다른 방법을 생각했다. 그래서 B를 가지고 문제를 해결해보려했다. B를 가지고 A의 길이가 될 떄까지 모든 경우의 수를 조사해보면 된다. 즉 A = abcde B = aabcdefgf일 때, (앞에서 뺀 갯수, 뒤에서 뺀 갯수)로 표현하면 (0,4) (1,3) (2,2) (3,1) (4,0)이 이다. 이 때 초기에 설정해야할 최댓값은 모든 문자가 다 다를 경우이다. 즉 A의 길이이다. 코드 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 3..

오답 노트 & 새로 알게 된 점 시뮬레이션은 문제를 이해하는 것이 중요한 것 같다. 이 문제에서 중요한 부분은 맞물리는 곳이 같으면 움직이지 않고, 다르면 움직인다. 옆에 것이 움직이지 않으면 맞물리는 곳 상관없이 움직이지 않는다. 맞물리는 곳을 비교할 때는, 회전하고 비교하는 것이 아니라 한 번에 비교하고 한 번에 회전해야한다 기능 별로 메서드를 만든다면 문제를 푸는 데 더욱 수월할 것이다. 시계 방향으로 회전하는 메서드, 반시계 방향으로 회전하는 메서드, 어디 방향으로 회전해야하는지 알려주는 메서드, 어떻게 회전해야하는지 알려주는 메서드가 있다. 어떻게 코드를 줄여야하는지 몰라서, 일단 맞고나보자하고 하드코딩을 했다. 그리고 톱니 하나를 일반화시킨다고 생각하여 재귀를 이용하여 풀었다. 코드1(재귀) ..

오답 노트 & 새로 아게 된 점 이 문제는 완탐으로 풀어도 아마 풀릴 것 같다. 그러나 정렬을 사용한다면 시간복잡도를 많이 줄일 수 있다. 여기서 색깔이 같은 점 중에 거리가 가장 가까운 점과 연결한다. 그래서 color가 같은 점들을 한 곳에 모아두고, 정렬을 시킨 뒤, 왼쪽 점과의 거리와 오른쪽 점과의 거리 중 최소를 구해 더하면 된다. 코드 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 import java.io.*; import java..

오답 노트 & 새로 알게 된 점 해당 문제를 그냥 완탐으로 풀게 된다면 (O(N^2)로) TLE가 난다. 그래서 정렬을 하고 나서, 앞에서부터 순서대로 탐색을 한다. 현재 index에 있는 값과 앞의 값을 비교하여 같으면 curCnt를 늘려주고, 다르게 되면 curCnt를 1로 해준다. 새로운 값이 나왔으므로 1로 초기화를 시켜줘야한다. 그리고 curCnt가 maxCnt가 보다 크면 이 때 횟수가 가장 많은 수를 바꿔줘야한다. 코드 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 package Sort; im..

오답 노트 & 새로 알게 된 점 문제를 읽으면서 숨바꼭질 문제와 비슷한 느낌을 받았다. bfs를 이용하여 N에 도달할 때 에너지 최솟값을 구해주면 된다. 다만 풀면서 실수한 점이 작은 점프, 큰 점프, 매우 큰 점프를 하면서 n의 값 또한 더 증가된다. 코드 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 import java.io.*; import java.util.*; public clas..

오답 노트 & 새로 알게 된 점 보자마자 백트래킹 생각이 나는 문제였다. 문제를 잘 읽어야한다. 최소 한 개의 모음 + 최소 두 개의 모음으로 이루어진 사전식으로 가능한(=정렬) 암호이다. 처음에 나는 암호 중에 모음이 하나라도 있으면 되는거네 라고 생각을 했다. 그러나 생각해보니 모음만 있으면 그것도 조건을 만족할 수 없다... 생각을 좀 깊이하는 버릇을 들여야겠다.. 아무튼 그래서 암호가 될 수 있는 경우의 수를 구하고, 위 조건을 만족시키는 것만 구하면 된다. 백트래킹을 잘 알고 있다면 어렵지 않은 문제이다. 코드 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..

오답 노트 & 새로 알게 된 점 이 문제는 숫자는 가만히 놔두고, 중간에 연산자를 끼워넣어 앞에서부터 계산하는 방식이다. 숫자는 최대 11개이다. 그렇다면 연산은 최대 10개이다. 여기서 시간복잡도를 생각해보면, 자리 10개 중에 사칙연산 중에 하나를 선택해야한다. 그리고 중복을 포함하지 않는다. 그렇다면 아마 시간 복잡도는 10P4라고 생각이 든다.(나의 예상) 그리고 문제에서 계산 중간이나 결과값은 int범위라고 나와있다. 보편화된 백트레킹 풀이인 것 같다. 단지 visit배열이 아닌 op배열을 이용하여 연산자의 개수를 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 ..

오답 노트 & 새로 알게 된 점 이 문제는 회의실 배정이라는 문제와 같이 풀어보면 좋을 것 같다. 문제에서 강의실을 최소로 사용하면서 모든 강의를 해야한다고 했다. 여기서 어떻게 하면 최소로 강의실을 사용할지 생각해봤다. 일단 강의와 강의 사이의 간격이 좁아야한다. 왜? 예로 1 3과 3 5을 보듯이 이렇게 이어지는 게 강의실을 최소로 사용한다고 생각했다. 그래서 시작시간을 기준으로 정렬을 한다. 이 때, 종료시간은 우선순위 큐에 넣는다. 이렇게 하기 위해서는 제일 처음에 있는 강의의 종료시간을 우선순위 큐에 미리 넣는다. 그래서 다음 강의 시작시간이 큐의 제일 앞에 있는 숫자(강의가 가장 빨리 끝나는 시간)과 비교하여 시작시간 >= 큐.peek이면 큐에 있던 수업을 poll하고 현재 강의의 종료시간을 ..

오답 노트 & 새로 알게 된 점 이 문제는 개인적으로 정말 어려웠다. 처음에 그냥 완탐은 TLE가 날 것 같다. 이 정도만 알고 있었다. TLE가 나면 이제 시간 복잡도를 줄이면서 풀 생각을 해야하는데 풀이법이 떠오르지 않았다. 풀이법을 설명하자면, 보석이 들어있는 배열을 가격 순으로 오름차순 정렬한다. 또한, 가방이 들어있는 배열을 무게 순으로 오름차순 정렬한다. 그리고 pro 메서드를 보면 while문이 있다. while문에서는 가방 배열을 기준으로, jew 배열을 탐색한다. 거기서 가방보다 무게가 낮은 보석들을 모두(가방에 담을 수 없는 보석을 만날 때까지) pq에 넣는다. 이 때, pq는 오름차순 정렬이다. 그렇다면 무게가 2인 가방(2가방이라함) 65와 99의 보석을 모두 담을 수 있다. 다만 ..

오답 노트 & 새로 알게 된 점 해당 문제를 풀면서 정말 스트레스를 많이 받았다. 하지만 그만큼 얻는 것이 많은 문제였다. 이 문제를 풀지 못해 구글링을 해서 힌트를 얻었는데 계속 96퍼에서 틀렸다고 나오는 것이다. 그래서 왜 틀렸는지 오카방에 물어봐서 해결할 수 있었다. 우선순위 큐를 사용하면서 최대 힙을 만들기 위해 람다식으로 return o2 - o1을 했는데 여기서 문제가 생겼다. 문제에서 32비트 정수 즉, int 범위의 끝에서 끝까지를 말했다. 근데 여기서 o2 - o1을 하면 오버 플로우가 난다. 그래서 제대로 된 최대 힙을 만들 수 없었다. 그래서 앞으로는 o2.compareTo(o1)을 자주 사용할 것이다.. 위 문제를 해결하고 나서 다른 코드들을 보았는데 TreeMap을 사용하여 너무나..

오답 노트 & 새로 알게 된 점 이번 문제는 우선순위 큐 문제이다. N { return o2.compareTo(o1); }); static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = atoi(st.nextToken()); std = atoi(st.nextToken()); limit = atoi(st.nextToken()); for (..