행복하개!

처음에 반복문 두개 겹쳐서 하다가 효율성에서 떨어졌다. 리스트로 해보려다가 어차피 효율성에서 떨어지다가 두 배열을 정렬하고 다른거 찾으면 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 =..

먼저.. 인간은 다 비슷한 동물이고 일정 지능이 되면 결국 비슷한 경험을 하게 되는 것 같다. (!!!) 이 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부터 시작해서..

public class BaekJoon_16_1932 { 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()); int[][] tree = new int[501][501]; int[][] dp = new int[501][501]; StringTokenize..

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class BaekJoon_16_1003 { private static int[][] dp; private static void fibonacci(int n) { for (int i = 2; i

1. 메모리 신경 안쓴 버전 public class CountingSort { public static void countingSort(int[] a, int[] b) { int[] c = new int[10001]; for (int i = 0; i = 0; i--) { b[--c[a[i]]] = a[i]; } } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReade..

public class QuickSort { //// 1. //static void quickSort(int[] nums, int left, int right) { //int pl = left; //int pr = right; //int x = nums[(pl + pr) / 2]; // //do { //while (nums[pl] x) //pr--; //if (pl = array[i]) { // i는 왼쪽에서 오른쪽으로 피봇보다 큰 값을 찾는다. //i++; //} //swap(array, i, j); // 찾은 i와 j를 교환 //} //// 반복문을 벗어난 경우는 i와 j가 만난경우 //// 피봇과 교환 //array[left] = array..

public class MergeSort { // a 배열에서 start 에서 end 사이의 값을 정렬한다. static void mergeSort(int[] a, int start, int end) { if (start == end) return; // 정렬할 부분의 길이가 1 이면 그냥 리턴한다. int middle = (start + end) / 2; // start와 end 사이 중간지점을 계산한다. mergeSort(a, start, middle); // 앞부분을 정렬하기 위한 재귀 호출 mergeSort(a, middle + 1, end); // 뒷부분을 정렬하기 위한 재귀 호출 merge(a, start, middle, end); // 앞부분과 뒷부분 병합 } // a 배열에서 앞부분(sta..