오답 노트 & 새로 알게 된 점 문제를 풀면서 처음에는 메모리 초과, 다음에는 시간 초과가 났다. 그래서 도저히 어떻게 풀지 감이 안 와서 구글링을 통하여 문제를 해결했다. 카테고리를 보니 DP와 BFS로 되어있었다. DP는 어떻게 사용되는지 보였다. 그러나 엥? BFS는 어디있는거지라는 생각을 했다. 아마 문제를 풀 때 최소를 구하기 위한 탐색 방법 중 하나인 BFS 모양(?)과 비슷하여 분류가 그렇게 된 건가 싶었다. 나는 BFS를 생각하면 BFS == 큐라고 생각하고 있었기 때문이다. 그런데 이 문제를 보면서 꼭 큐를 사용해야만 BFS 다는 아닌가 보다 라는 생각이 들었다. 난 DP를 제대로 공부하지 않고, 단지 메모이제이션(?) 그 부분만 알고 있다. 전에 했던 것을 저장하여 앞으로 나아가는 것이..

오답 노트 & 새로 알게 된 점 이 문제는 BFS의 제대로 된 개념만 알면 쉽게 풀 수 있는 문제이다. outside는 첫 번째 행이므로 입력을 받으면서 큐에 첫 행을 모두 집어넣는다. 그리고 bfs를 돌리고 inside는 마지막 행으로, 마지막 행이 하나라도 visit에서 true가 있다면 침투를 했다는 것이다. 코드 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 72 73 74 75 76..

오답 노트 & 새로 알게 된 점 처음에 문제 접근하여 코드를 작성했을 때, 마지막 예제를 고려하지 않았다. 그래서 해당 index에 접근하면 무조건 index의 day만큼 다음 index를 접근하게 했다. 그러나 4번 예제에서는 1번 날, 6일 날, 8일 날 접근하여 총 90이 나온다. 제일 이해하지 못했던 것이 과연 N+1날에는 상담을 할 수 있는 것이냐 없는 것이냐가 헷갈렸다. 예제 2번을 보면, 답이 55이다. 그렇다면 1 ~ 10을 모두 더했다는 것이다. 그러면 마지막 9번째 index는 1일이 걸리는데, 1일은 그다음 N+1번째까지 포함한다는 뜻이다. 그래서 N+1날까지 상담을 진행하는 뜻인 것 같다. 문제 풀이는 재귀를 사용하여 풀었다. 다른 블로그들을 보면 dp로 풀었는데 아직 dp쪽은 공부..

오답 노트 & 새로 알게 된 점 해당 문제는 전에 풀었던 카드 놓기와 비슷하지만, 카드 놓기는 중복을 제외한 순열이었다면, 이번 문제는 중복 가능한 순열이다. 그래서 if(visit[i]) continue 구문만 빼준다면 중복 가능한 순열이 된다. 똑같은 방식으로 String형으로 set에 중복 가능한 순열들을 모아놓은 뒤에 list에 Integer형으로 변환하여 저장한다. 그리고 max값을 지정하여 if 조건식을 만족하게 한 뒤 max 값을 출력하면 된다. 하지만 여기서 중요한 부분이 있다. 위와 같이 풀면 perm1만을 포함하는데, 여기서 반례가 생긴다. 14 2 7 8 을 하게 되면, N은 두자리 숫자인데 값은 8이 나와야 한다. 반례가 생기는 것이다. 그래서 perm2라는 메소드를 새로 만들어 N..

오답 노트 & 새로 알게 된 점 문제를 보고 순열을 사용하여, 가능한 경우의 수를 모두 뽑은 뒤에, 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의 자료형이 ..