행복하개!

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

조금 원론적인 이야기를 하자면 .. 스도쿠를 해봤다면 알겠지만 인간이 이 게임을 할때 사실 어려운 문제는 간단하지 않다.. 여러 방면에서 공식을 대입해가면서 풀어야하고 초보자의 경우에는 실수도 많이 튀어나와서 연필로 수도쿠를 하고 있었다면 지우개로 지우다가 종이가 너덜너덜(?) 해지는 케이스가 있을 때가 있다. 사람의 두뇌는 사실상 모든 케이스를 판별하기보다는 공식에 혹은 경험에 의거하여 결론을 도출하는 경향이 크다. 하지만 컴퓨터의 경우는 다르다. 컴퓨터는 먼저 매우 빠르다.(!!) 그 빠름의 강점을 이용해서 모든 케이스를 판별하는 것이 가장 일반적인 혹은 기본적인 활용 방법 중 하나이다. 우리가 코딩을 할때는 조건문과 반복문을 통해서 어떤 코드를 짜는데 사실 그게 다이다.. 빠른 컴퓨터를 이용해서 빠..

백트래킹이란 dfs문제에서 깊이를 탐색하다가 요쪽(?)으로 계속가면 원하는 값을 얻지 못함을 미리 깨닫고 더이상 들어가지 않는 기법이다. 일명 가지치기라고 한다. dfs의 단점은 무한 반복될 수 있는 구간에서는 빠져나올 수 없다는 단점이 있다. 이를 적절하게 해결할 수 있는 하나의 기법이 되고, 그 외에 bfs를 통해서 빠르게 탐색하는 방법도 있지만 bfs는 인덱스가 진행될 수 록 메모리가 지수승으로 폭발 증가한다는 단점이 있다. 그래서 적절하게 dfs를 활용해서 앞서 미리 이 가지가 유효할지를 검사하여 잘라낼지 진행할지를 결정한다. N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오..

public class BaekJoon_14_1181 { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(reader.readLine()); Set hs = new HashSet(); // 해쉬 셋을 이용한 중복 제거 for (int i = 0; i < n; i++) { hs.add(reader.readLine()); } S..

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..

삽입 정렬 (Insertion Sort) 삽입하기 적절한 위치를 찾으면 그 위치에 삽입을 하되, 원래 있던 숫자들은 뒤로 한칸씩 민 후, 아이템을 추가한다. 1) 입력 17 14 11 19 13 15 2) 절차 i = 1 i 위치의 값을 앞 부분의 적당한 위치에 끼워 넣는다. 17 14 11 19 13 15 14 17 11 19 13 15 i = 2 14 17 11 19 13 15 11 14 17 19 13 15 i = 3 11 14 17 19 13 15 i = 4 11 14 17 19 13 15 11 13 14 17 19 15 i = 5 11 13 14 17 19 15 11 13 14 15 17 19 3) 요약 void insertionSort(int[] a) { for (int i = 1; i < a..

버블 정렬 (Bubble Sort) 1) 개요 최소 값을 선택해서 이동한다. 정렬된 데이터 정렬할 데이터 입력 데이터 17 14 11 19 13 1단계 11 17 14 19 13 2단계 11 13 17 14 19 3단계 11 13 14 17 19 4단계 11 13 14 17 19 5단계 11 13 14 17 19 2) 절차 입력 17 14 11 19 13 15 i = 5 0 부터 i - 1 까지, 두 쌍의 값을 비교하여, 왼쪽 값이 크면 서로 위치를 바꾼다. 17 14 11 19 13 15 14 17 11 19 13 15 14 17 11 19 13 15 14 11 17 19 13 15 14 11 17 19 13 15 14 11 17 19 13 15 14 11 17 13 19 15 14 11 17 13 1..