오답 노트 & 새로 알게 된 점 해당 문제는 백트래킹을 사용하지 않아도 TLE가 나지 않을 것 같아 완전 탐색으로 풀었다. cannot이라는 배열을 사용하여 조합하면 안 되는 것들을 index로 하고 값을 true라고 저장해뒀다. 그래서 삼중 for문을 사용하여 가능한 경우의 수를 모두 탐색하는 중에 cannot 값이 false를 가지게 되면 ( = 조합해도 된다) result를 더해주었다. 여기서 가장 중요한 부분은 삼중 for문 안 주석문이다. 코드 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 import java.io.*; import jav..

오답 노트 & 새로 알게 된 점 해당 문제는 원리만 떠오르면 쉽게 풀 수 있는 문제인 것 같다. 나는 처음에 주어진 중량 중에 최솟값 * 로프의 개수와 주어진 주어진 중량 중에 최댓값을 구하고 최댓값을 가지는 로프의 개수를 구하여 Math.max(최솟값 * 로프의 개수, 중량 최댓값 * 최댓값을 자기는 로프의 개수) 로 구했다. 그러나 해당 반례를 통해 쉽게 틀렸습니다가 나왔다. 3 10 20 30 을 입력하면 답은 40이 나와야 한다. 그래서 이 반례를 보고 생각을 했다. 아마 문제에서는 중량 순으로 줄을 입력해주지 않기 때문에, 일단 오름차순으로 정렬을 한다. 그리고 뒤에서부터 해당 로프의 중량에서 개수를 곱한 값과 그 앞의 로프의 중량에서 개수를 곱한 값을 비교하였다. 이렇게 비교할 수 있는 이유는..

오답 노트 & 새로 알게 된 점 자바 Collections에 대해 공부를 한 적이 있는데, 이 부분을 지금 알아서 놀랬다. ArrayList를 Integer에 대해 선언하고, Collections.sort를 사용하면 그냥 오름차순이 정렬된다. 그래서 나는 제네릭 부분에 클래스형으로 선언하고 sort를 사용해도 오름차순 정렬될 줄 알았다. 그러나 오개념이었다. 클래스형을 제네릭으로 ArrayList를 선언하고, Collections.sort를 사용하게 되면 컴파일 에러가 뜬다. 그래서 해당 클래스는 Comparable이나 Comparator 인터페이스를 구현하여 해당 메소드를 오버라이딩 해줘야한다. 그러면 문제로 넘어가보자. 이 문제를 읽자마자 최대한 회의를 많이 진행하기 위해서는 회의가 가장 짧은 시간으..

새로 알게 된 점 & 오답 노트 해당 문제를 처음에는 dfs로 문제를 풀어보았다. 하지만 이번에 문제집을 밀면서 있길래 bfs로 풀어보자라는 생각이 들어서 bfs로 풀었다. 6달 만에 본 문제여서 아예 풀이법이 생각이 나지 않아 처음 본 문제처럼 풀었다. 헷갈렸던 부분이 일단 x, y좌표이다. 아무 생각 없이 이 문제 쉽다 하고 원래의 x, y좌표대로 하면 바로 틀리기 때문이다. 여기서는 행이 y이고 열이 x이기 때문에 생각하면서 입력을 받아야 한다. 그리고, 분명히 좌표는 7까지 있는데, index크기는 6까지 있다. 그러면 Index 예외가 생기지 않을까라는 생각이 들었다. 그러나 직사각형이 차지하는 부분을 색칠하면서 끝점들은 포함하지 않기 때문에 이 부분은 자동적으로 제외할 수 있다. 코드 1 2 ..

오답 노트 & 새로 알게 된 점 해당 문제는 약 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으로 바꾸려고 했다. 그러나 뭔가 안될 것 같아 하지 않았다. 그래서 하루정도 생각을 했다. 그래도 문제가 풀리지 않아 힌트를 보았다. 힌트를 보니 두 번째 생..

StringBuilder와 StringBuffer를 공부하다가 StringBuilder에서의 equals 출력 값과 String에서의 equals 출력 값이 다르다는 것을 발견했다. 그래서 왜 다른지 열심히 구글링 하고 오카방에 여쭤보았다. 원래 equals() 는 주소를 비교한다. 아래 코드는 자바에서 equals() 메소드 구현한 코드이다. 보면 ==을 이용하여 비교를 한다. 즉, 오버라이딩 되지 않은 equals는 ==를 사용하여 주소 값을 비교한다. public boolean equals(Object obj) { return (this == obj); } 그러면 왜 아래 코드는 이러한 값을 출력할까? StringBuilder sb1 = new StringBuilder("abc"); StringBu..

String을 비교할 때 왜 .equals()를 사용할까에 대해 궁금해하면서 공부를 하게됐다. 새로운 줄에서 + 연산 public class Main { public static void main(String[] args) throws IOException { String str1 = "a"; str1 += "bc"; String str2 = "abc"; System.out.println(str1 == str2); //false System.out.println("str1 = " + str1); //abc System.out.println("str2 = " + str2); //abc String str3 = "a" + "bc"; System.out.println(str2 == str3); //true S..

자바 공식 문서에서 Object 메소드에 equals와 toString이 있다. public String toString() 모든 Wrapper 클래스는 객체를 문자열로 변환하는 toString() 메소드를 가지고 있음 Integer i = Integer.valueOf(11); 1) System.out.println( i.toString() ); 2) System.out.println(i); 1)과 2)의 결과값은 같다. public boolean equals(Object o) 객체 내부의 값을 비교함 Integer x1 = 6; Integer x2 = 7; Integer y1 = 6; int y2 = 6; System.out.println(x1.equals(x2)); //false System.out...

Integer.valueOf() public static type valueOf(type t or String str) 기본형 또는 String --> Wrapper 반환형이 Integer 매개변수에 String, Integer 올 수 있음 매개변수로 문자가 올 경우 해당 유니 코드 값을 반환 java.lang 패키지에 속하는 정적 메소드 Integer.parseInt() public static type parse type (String str) 문자열 --> 기본형 반환형이 int 매개변수에 String만 올 수 있음 매개변수로 문자가 올 경우 에러 발생 Integer클래스에 속함 VAL.typeValue() Wrapper 클래스의 VAL 변수를 type형으로 (기본형) 바꾼다 Integer a = ..

오답 노트 & 새로 알게 된 점 첫 그리디 문제이다. 이 문제는 그냥 쉽게 생각했다. 오름차순으로 입력해주기 때문에 제일 뒤에서부터 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 ..