행복하개!

처음에 반복문 두개 겹쳐서 하다가 효율성에서 떨어졌다. 리스트로 해보려다가 어차피 효율성에서 떨어지다가 두 배열을 정렬하고 다른거 찾으면 answer에 넣게 만들었다. public static String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); for (int i = 0; i < completion.length; i++) { if (!participant[i].equals(completion[i])) { answer = participant[i]; break; } } if (answer.equals("")) answer =..

일단 인형을 건져올려서 바구니에 담는 것은 쉽다. moves의 순서대로 board라는 2차원 배열에 해당 열에만 차례대로 0이 아닌걸 찾아내면 된다. 만약 0이면 바구니에 안담고 넘어가면 끝. 다만 바구니를 Array로 할 것인지, ArrayList로 할 것인지, Stack으로 할 것인지는 기호(?)에 따라 하면 되지만 Stack이 제일 알맞은 것 같다. 리스트로 구현한 코드 : public static int solution(int[][] board, int[] moves) { int answer = 0; List basket = new ArrayList(); for (int i = 0; i < moves.length; i++) { int tmp = 0; int location = moves[i] - ..

이 목표는 가장 많은 강의 수를 구하는 문제인데, 곰곰히 생각해보면 제일 먼저 따져야할 것은 끝나는 시간이 가장 빠른 것을 기준으로 정하면 되는 문제이다. 다만 중요한 점은 정말 당연한 이야기이지만 다음 강의의 시작시간이 현재 강의의 끝 시간보다 커야한다는 점이다. 왜? 강의는 겹칠 수가 없으니까. 문제에는 정렬되어서 나온다는 말이 없기 때문에 정렬을 해야한다. 기준은 끝나는 시간을 기준으로 정렬을 하되, 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬을 하면 된다. 이에 대한 정렬 코드는 아래의 코드이다. Arrays.sort(arr, new Comparator() { @Override public int compare(int[] start, int[] end) { if (start[1] == ..

처음에 풀 때는 1차원 배열에 인덱스를 무게, 값을 가치로 두고 풀었는데 원하는 방향으로 값이 나오지 않았다. 왜 안나오나 했더니 이전값과 비교하는 방식이 틀려먹어서였다. public class BaekJoon_16_12865_2 { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(reader.r..

이 문제는 11053문제 바로 뒤에 나오는 문제이다. 다만 가장 큰 값을 중심으로 왼쪽과 오른쪽으로 값이 작아지는 그 부분 수열의 길이를 알아야하는 문제이다. 처음에 접근 방식은 먼저 가장 긴 증가 부분 수열 방식으로 값을 셋팅해놓고, 큰 값과 그의 인덱스를 저장한 뒤, 그 인덱스부터 가장 긴 감소 부분 수열 방식으로 다시 검색하는 방식으로 진행했었는데, 될 법 한데 자꾸 예외에 부딪히고 코드가 읽기 힘들어졌다. 어찌어찌하면 될 것 같은데 동적프로그래밍의 특성을 제대로 활용하고 싶다고 가정한다면 좋은 접근 법은 아니다. 그렇다면 좋은 접근 법은 무엇이냐? 1. 가장 긴 증가하는 부분 수열을 통해 먼저 카운팅한다. 2. 가장 긴 감소하는 부분 수열을 통해 카운팅을 한다. 3. 합치고 -1한다. 코드를 보자..

정말 알것 같다 싶으면 새로운 유형이 나와버리는 동적프로그래밍이다! 조금씩 익숙해지고는 있지만 자잘한 조건에 난감한 경우가 많다. 이 문제는 LIS문제이다. 이걸 처음 접하면 이게 왜 동적 프로그래밍 문제지? 하고 의문을 가지고 내 식대로 풀다가 망하는 경우가 100% 된다. 망하는 이유는 문제를 정확히 이해하지 못했기 때문이다. 아래는 문제에서 주어진 조건이다. 6 10 20 10 30 20 50 이렇게 보면 그냥 처음부터 max값을 찾아서 10 20 넣고 10은 건너뛰고 30넣고 20은 건너뛰고 50넣고.. 이렇게 하면 될것 같다. 그래서 아래는 그렇게 짠 코드이다. public class BaekJoon_16_11053_2 { public static void main(String[] args) t..

먼저.. 인간은 다 비슷한 동물이고 일정 지능이 되면 결국 비슷한 경험을 하게 되는 것 같다. (!!!) 이 2156번 문제도 마찬가지다. ㅋㅋㅋㅋ 2579 문제랑 되게 유사하다. 다만 다른 점은 계단 문제는 규칙 안에서 무조건 하나는 밟게 되어 있는 반면, 이 포도주 문제는 그렇지 않다. 이 문제는 선택하지 않을 수 있다. 이게 무슨 말이냐면 .. 먼저 3가지 측면이 존재한다. 1. 현재 포도주와 직전의 포도주를 마신다. 2. 현재 포도주와 전전 포도주를 마신다. 3. 현재 포도주를 마시지 않고 전의 포도주를 마신 케이스를 선택한다. 그니까 1 2번은 2579 문제에서 풀어서 알겠는데.. 3번은 무슨이야기이냐. 예를 들어, (i=0) 20 (i=1) 50 (i=2) 5

public class BaekJoon_16_10844 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(reader.readLine()); long dp[][] = new long[n + 1][10]; for (int i = 1; i < 10; i++) { dp[1][i] = 1;..

솔직히 말해서 여태 풀었던 문제들은 점화식을 이용해서 이전 계산 값을 가지고 푸는 문제였는데, 이번 문제는 조금 달랐다. (물론 생각의 전환 차이였고 같은 유형임) 이 문제는 메모이제이션이라고 해서 값을 적어둔다 이런 느낌의 문제다. 이게 사람 사고가 문제가 뭐냐면 중고등학교때 학교 학원에서 익힌 기출(?)에 의한.. 주입식.. 크흠 아무튼 사고 자체를 확장하지 않으면 아닌걸 알면서도 if문 써서 풀어보다가 결국 빠꾸치는 문제가 된다. 이 문제를 사고하는 방식은 지름길을 뒤늦게 찾는(?) 문제라고 보여졌다. 0과 1일때는 어차피 계산할게 없으니 0을 넣어주고 2부터 진행하는데 이전의 연산 횟수를 계속 업데이트 하되, 1번씩 연산했다고 가정하고 진행하는 것이다. 여기서 1번씩 연산했다고 가정하는 방식은 +..

이 문제를 처음에 접했을 때는 어려움이 있었다. 그 이유는 다들 그렇겠지만 규칙 때문이다. 이 규칙이 DP유형이 덜 익숙하게 되면 조건을 걸고 풀어야하는 착각을 하게 된다. DP를 쓰는 이유를 알고 가면 더 쉬워진다. DP는 이미 계산 했던 것들을 계산하지 않고 가져다쓰는 일종의 캐시 개념으로 작동한다. 계산했던것을 몇번이고 다시 계산하면 당연히 느려질 수 밖에 없으니 이를 방지하는 기법이다. 그런데 DP를 사용하려면 중요한 점은 규칙을 찾아야 된다는 점이다. 피보나치수열과 같이 뒤로 1, 2번째 값을 더하는 간단한 것들은 바로 머리에 들어오는데 이 문제는 그렇지가 않다. 일단 규칙이 막 있으니까 조건걸어야되나? 싶게 보인다. 일단 딱보니 1차원 배열을 이용하면 될 것 같다. 그러면 먼저 1부터 시작해서..