오답 노트 & 새로 알게 된 점 문제를 보고 순열을 사용하여, 가능한 경우의 수를 모두 뽑은 뒤에, Set을 사용하여 중복된 것을 제외시키면 되겠다는 생각이 들었다. 그래서 재귀를 이용하여 순열을 사용( perm 메소드 ) 하고, set의 size를 구하여 출력시키면 AC이다. 코드 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 package BruteForce_Search; import java.io.*; import java.util.*; public class Main { static ..

오답 노트 & 새로 알게 된 점 이 문제는 어려운 자료구조, 알고리즘을 사용하여 어려운 문제가 아닌, 나에게 너무나 논리적은 사고를 요하는 문제로서 정말 난이도가 높았다. 해당 문제를 푼 분들은 이러한 원리를 깨닫고 푼 것이면 정말 대단하다고 느꼈다. 문제 설명을 듣고 이해했을 때 감명받고, 어려운 문제였다고 생각한다. 해당 문제 설명은 오카방에서 여쭤봤고, 내가 기록한 모든 풀이들은 류호석(https://github.com/rhs0266/FastCampus)님께서 말씀해주셨다.. 너무 감사했다.. 문제 풀이 순서 1. 1과 3, 3과 5, 5와 6, 6과 10의 차이를 diff배열에 넣는다. 2. 이것들을 오름차순하여 index가 [ 0, N-K ) 까지 더한다. 여기서 1번부터 보겠다. 난 어떤 원리..

오답 노트 & 새로 알게 된 점 해당 문제는 그렇게 어렵지 않게 풀었다. 두 개의 arraylist를 만들어서 R를 구분자로, B를 구분자로 파싱하여 각각의 arraylist에 넣어줬다. 그래서 arraylist의 원소의 갯수를 비교하여 더 많은 원소의 개수를 가진 것을 한 번에 다 깔고, 적은 원소를 가진 것을 중간에 덧 입히는 식으로 생각했다. 왜 파싱을 생각하게 됐나? 처음에는 큐나 스택을 이용해서 현재 value와 다음 value가 같으면 String에 더해줘서 arraylist에 추가해준다 이런 생각을 했다. 그러나 생각해보니 R과 B를 구분자로 하여 파싱을 하면 그러한 귀찮음을 덜 할 수도 있고, 반례들이 존재하지 않을 것이라 생각했다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 1..

오답 노트 & 새로 알게 된 점 해당 문제는 생각하는데 오래 걸렸다. 처음에는 로직이 틀려 틀렸습니다가 나왔고, 나중에는 배열 index 때문에 런타임 에러가 나왔다. 문제 풀이를 설명하자면, 처음부터 -가 나올 때까지 숫자들은 모두 더해주고, 그 뒤에는 -든 +든 앞에서 더해준 숫자에서 빼주면 된다. 해당 원리는 -, + 상관없이 괄호를 쳐주게 되면 +를 무용지물로 만들 수 있기 때문이다. 예를 들어 100 - 100 + 100 - 100 + 100 - 100에서 +부분을 괄호로 묶어주면 무슨 말인지 알게 된다. 따라서 문제를 풀 때, -를 delim(구분자)로 설정하고 나눠주었다. 구분자를 - 로 하는 이유는 -가 나올 때까지의 숫자들을 구하기 위해서이다. 따라서 분리해놓은 문자열들을 arraylis..

오답 노트 & 새로 알게 된 점 해당 문제는 런타임 에러로 수 없이 많은 제출을 했다. 처음에는 배열 index 문제로 런타임 에러가 난 줄 알았다. 그래서 배열 index 문제는 없는 것 같은데 왜 런타임 에러가 발생했을까라는 생각으로 문제를 다시 천천히 읽어보았다. 그랬더니 운동기구 근손실 정도가 10^18까지 있는 것이다. 그래서 아,, long을 사용해야 하구나 라는 것을 깨달았다. 그래서 코드를 보면 StringTokenizer를 사용하기 때문에 string을 long이나 Integer로 변경해주는 메소드가 두 개 있는 것을 볼 수 있다. size( 배열의 길이 )는 int로 해주어야 하고, 안의 value들의 type은 long으로 해줘야한다. 길이가 홀수, 짝수일 경우 index를 조정해주고..

오답 노트 & 새로 알게 된 점 해당 문제는 이해가 어려웠지 구현은 어렵지 않았다. 가장 큰 양을 가진 에너지 드링크를 제외한 나머지를 /2 하여 가장 큰 양을 가진 에너지 드링크에 넣으면 된다. 중요한 게 소수점을 사용하기 때문에 double을 사용하고, 계산하는 중에 /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 package Greedy; //BOJ 20115 에너지 드링크 import java.io.*; import java.util.*; public class Main { static int atoi(Strin..

오답 노트 & 새로 알게 된 점 전에 풀었던 강호? 그 문제와 비슷했다. 내림차순을 하고 최솟값을 구하는 문제였다. 이 문제를 풀면서 항상 내림차순 정렬할 때는 comparator를 사용하곤 했는데, 람다식을 배우고 나서는 해당 문제에 람다식을 적용해보았다. 람다식은 쓸 줄 안다면 매우 편한 것 같다. 해당 문제 설명은 주석을 참고하자. 코드 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 package Greedy; //BOJ 11508 2+1 세일 import java.io.*; import java.util.*; ..

오답 노트 & 새로 알게 된 점 해당 문제는 꽤나 애를 먹었다. 문제를 제대로 읽지 않아 손님의 순서를 적절히 바꿨을 때 이 부분을 읽지 않았다. 그래서 문제를 제대로 읽고 음수가 되면 어차피 0원이니까 제일 적은 팁을 주는 사람이 가장 뒤에 있어야 최댓값이 나온다는 생각을 했다. 그래서 Comparator로 내림차순을 사용하려고 하는데, 여기서 또 문제가 생겼다. Comparator는 기본 자료형에서는 호출되지 않고 Wrapper 클래스에서 호출이 가능하다. (객체) 그래서 이 부분을 잘 몰라 계속 Comparator를 시도했고, 알게 된 후에는 배열을 Integer로 선언하여 문제를 풀었다. 또, 여기서 이제 다 맞은 줄 알고 제출을 했는데 틀렸습니다가 나왔다. 그 이유는 결괏값인 sum의 자료형이 ..

오답 노트 & 새로 알게 된 점 해당 문제는 백트래킹을 사용하지 않아도 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 ..