delta
deltaTest
package basic.delta;
import java.util.Arrays;
// 2차원 배열 (문자)
// if - else 구조의 4방 탐색은 개발자의 실수를 많이 유발
// 상, 하, 좌, 우 이동에 대한 변화량을 미리 배열로 계산
// 상(-1, 0) 하(+1, 0) 좌 (0, -1) 우 (0, +1)
public class DataTest1 {
static char[][] map = new char[5][5];
public static void main(String[] args) {
char ch = 'A';
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[i][j] = ch++;
}
}
// 출력
for (int i = 0; i <5; i++) {
System.out.println(Arrays.toString(map[i]));
}
// System.out.println(Arrays.deepToString(map).replace("],", "]\n"));
// y = 3, x = 3 자리의 상,하,좌,우 출력
// print4_no_delta(4, 4);
// for (int i = 0; i < 5; i++) {
// for (int j = 0; j < 5; j++) {
// print4(i, j);
// }
// }
// for (int i = 0; i < 5; i++) {
// for (int j = 0; j < 5; j++) {
// print4x(i, j);
// }
// }
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
print8(i, j);
}
}
}
static void print4_no_delta(int y, int x) {
// 상
if (y - 1 >= 0) {
System.out.print(map[y - 1][x]);
}
// 하
if (y + 1 < 5) {
System.out.print(map[y + 1][x]);
}
// 좌
if (x - 1 >= 0) {
System.out.print(map[y][x - 1]);
}
// 우
if (x + 1 < 5) {
System.out.print(map[y][x + 1]);
}
System.out.println();
}
// delta
// 상, 하, 좌, 우
// 순서가 있다. (문제에 따라 순서를 고정시켜야 하는 경우도 존재)
static int dy4[] = {-1, 1, 0, 0};
static int dx4[] = {0, 0, -1, 1};
static void print4(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 4; d++) {
int ny = y + dy4[d];
int nx = x + dx4[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
System.out.print(map[ny][nx]);
}
System.out.println();
}
// 대각선
// 좌상, 우상, 좌하, 우하
static int dy4x[] = {-1, -1, 1, 1};
static int dx4x[] = {-1, 1, -1, 1};
static void print4x(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 4; d++) {
int ny = y + dy4x[d];
int nx = x + dx4x[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
System.out.print(map[ny][nx]);
}
System.out.println();
}
// 8방
static int dy8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
static int dx8[] = {0, 0, -1, 1, -1, 1, -1, 1};
static void print8(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 8; d++) {
int ny = y + dy8[d];
int nx = x + dx8[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
System.out.print(map[ny][nx]);
}
System.out.println();
}
}
package basic.delta;
import java.util.Arrays;
// 2차원 배열 (문자)
// if - else 구조의 4방 탐색은 개발자의 실수를 많이 유발
// 상, 하, 좌, 우 이동에 대한 변화량을 미리 배열로 계산
// 상(-1, 0) 하(+1, 0) 좌 (0, -1) 우 (0, +1)
// 한 칸이 이동이 아닌 갈 수 있을 때까지 계속 이동
public class DataTest2 {
static char[][] map = new char[5][5];
public static void main(String[] args) {
char ch = 'A';
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[i][j] = ch++;
}
}
// 출력
for (int i = 0; i <5; i++) {
System.out.println(Arrays.toString(map[i]));
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
print8(i, j);
}
}
}
// delta
// 상, 하, 좌, 우
// 순서가 있다. (문제에 따라 순서를 고정시켜야 하는 경우도 존재)
static int dy4[] = {-1, 1, 0, 0};
static int dx4[] = {0, 0, -1, 1};
static void print4(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 4; d++) {
// 반복문으로 구성, ny = y.. -> ny = ny ..
int ny = y;
int nx = x;
while (true) {
ny = ny + dy4[d];
nx = nx + dx4[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) break;
System.out.print(map[ny][nx]);
}
}
System.out.println();
}
// 대각선
// 좌상, 우상, 좌하, 우하
static int dy4x[] = {-1, -1, 1, 1};
static int dx4x[] = {-1, 1, -1, 1};
static void print4x(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 4; d++) {
int ny = y;
int nx = x;
while (true) {
ny = ny + dy4x[d];
nx = nx + dx4x[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) break;
System.out.print(map[ny][nx]);
}
}
System.out.println();
}
// 8방
static int dy8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
static int dx8[] = {0, 0, -1, 1, -1, 1, -1, 1};
static void print8(int y, int x) {
System.out.print(map[y][x] + " : ");
for (int d = 0; d < 8; d++) {
int ny = y;
int nx = x;
while (true) {
ny = ny + dy8[d];
nx = nx + dx8[d];
if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) break;
System.out.print(map[ny][nx]);
}
}
System.out.println();
}
}
Recursive
RecursiveCallTest
package basic.recursive;
public class RecursiveCallTest {
public static void main(String[] args) {
// m1();
// m1_2(0);
// m2();
// m3();
// m4();
m5(5);
}
// static int m1_cnt = 0;
// static void m1() {
// // local 변수와 값은 항상 초기화
//// int i = 0;
//// System.out.println("m1 " + i);
////
// System.out.println("m1 " + m1_cnt++); // static 변수는 공유
// m1();
// }
//
// static void m1_2(int i) {
// System.out.println("m1_2 " + i); // parameter 공유
// i++;
// m1_2(i);
// }
static int m2_cnt = 5;
static void m2() {
System.out.println("앞 m2 cnt : " + m2_cnt);
if (m2_cnt > 0) {
m2_cnt--;
m2();
}
System.out.println("뒤 m2 cnt : " + m2_cnt);
}
static int m3_cnt = 5;
static void m3() {
System.out.println("앞 m3 cnt : " + m3_cnt); // 기저조건 check 전에 항상 수행
// 기저 조건
if (m3_cnt == 0) {
return;
}
m3_cnt--;
m3();
System.out.println("뒤 m3 cnt : " + m3_cnt); // 기저조건 check 후에 있어서 기저조건에 의해 return 되면 수행 X
}
static int m4_cnt = 5;
static void m4() {
// 기저 조건
if (m4_cnt == 0) {
return;
}
// 앞, 뒤 출력을 쌍으로 맞추려면 기저 조건이 맨 위로 이동해야 한다.
System.out.println("앞 m4 cnt : " + m4_cnt);
m4_cnt--;
m4();
m4_cnt++; // 재귀 호출 전후에 동일한 static 변수의 값을 가지려면 변화량의 반대로 처리를 해줘야 한다.
System.out.println("뒤 m4 cnt : " + m4_cnt);
}
// static 대신 파라미터 공유
static void m5(int m5_cnt) {
// 기저 조건
if (m5_cnt == 0) {
return;
}
// 앞, 뒤 출력을 쌍으로 맞추려면 기저 조건이 맨 위로 이동해야 한다.
System.out.println("앞 m5 cnt : " + m5_cnt);
// 1. 줄였다 원복.
// m5_cnt--;
// m5(m5_cnt);
// m5_cnt++; // 재귀 호출 전후에 동일한 static 변수의 값을 가지려면 변화량의 반대로 처리를 해줘야 한다.
// 2. 줄이지 않고 줄이는 연산을 통해서 전달
// m5(m5_cnt - 1);
// 3. -- 연산자
// m5(m5_cnt--); // stack overflow
// 4. -- 연산자 앞
m5(--m5_cnt);
m5_cnt++; // 원복이 필요
System.out.println("뒤 m5 cnt : " + m5_cnt);
}
}
FactorialTest
package basic.recursive;
public class FactorialTest {
public static void main(String[] args) {
factorial(5); // 5x4x3x2x1
int result = factorial2(5);
System.out.println(result);
factorial3(5, 1);
}
// 계산 결과를 static 변수를 이용
static int result = 1;
static void factorial(int n) {
// 기저조건
// 1. 재귀호출을 끝내야 한다.
// 2. 문제에서 원하는 상태가 완료되었다.
if (n == 1) {
// 계산 결과 출력
System.out.println(result);
return;
}
// 계산
result = result * n;
// 재귀 호출
factorial(n - 1);
}
// 5 <- 4 <- 3 <- 2 <- 1
static int factorial2(int n) {
// 기저조건
if (n == 1) {
// 계산 결과 출력 대신 재귀 호출 종료 처리
return 1;
}
// 계산
// 3 단계 입장은 4 에게 2 X 1 의 결과에 3 자신을 곱해서 리턴
// 나보다 1 적은 재귀 호출을 수행하고 그 결과에 나를 곱한 다음 리턴
return n * factorial2(n - 1);
}
static void factorial3(int n, int result) { // result : 이전 단계에서 계산되어 전달된 값
// 기저 조건
if (n == 1) {
System.out.println(result);
return;
}
// 계산
// result 에 자신을 곱한다.
// int temp = result * n;
// 재귀 호출
// factorial3(n - 1, temp);
// 재귀 호출 + 계산
factorial3(n - 1, result * n);
}
}
Sort
ArraySortTest
package basic.sort;
import java.util.Arrays;
import java.util.Comparator;
// 자바는 정렬 API 를 제공
// 문제에서 정렬이 필요한 경우, 적절하게 대응
public class ArraySortTest {
public static void main(String[] args) {
// 정수 정렬
// int[] intArray = {3, 5, 2, 7, 9, 4};
// Arrays.sort(intArray);
// System.out.println(Arrays.toString(intArray));
//
// 문자열
// String[] strArray = {"Hello", "ABC", "World", "UPLUS"};
// Arrays.sort(strArray);
//// Arrays.sort(strArray, Collections.reverseOrder());
// System.out.println(Arrays.toString(strArray));
Item[] itemArray = {
new Item(3, "666"), new Item(2, "777"), new Item(5, "444"), new Item(3, "111")
};
// implements Comparable
// Arrays.sort(itemArray);
// Arrays.sort(itemArray, Collections.reverseOrder());
// System.out.println(Arrays.toString(itemArray));
// Comparator interface 객체 전달
// 정렬 하기 위한 방법 2 : Comparator 객체 전달(익명) // 대상 객체에 Comparable 구현 없어도 된다.
// Arrays.sort(itemArray, new Comparator<Item>() {
//
// @Override
// public int compare(Item o1, Item o2) {
//// return o1.itemId - o2.itemId;
// return o1.itemNm.compareTo(o2.itemNm);
// }
//
// });
// System.out.println(Arrays.toString(itemArray));
// 정렬 하기 위한 방법 3 : Comparator 객체 전달(Lambda) // 대상 객체에 Comparable 구현 없어도 된다.
Arrays.sort(itemArray, (o1, o2) -> o2.itemId - o1.itemId);
System.out.println(Arrays.toString(itemArray));
}
// 정렬이 되기 위한 방법 1 : Comparable interface 를 구현
static class Item implements Comparable<Item> {
int itemId;
String itemNm;
Item(int itemId, String itemNm) {
this.itemId = itemId;
this.itemNm = itemNm;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemNm=" + itemNm + "]";
}
@Override
public int compareTo(Item o) {
// return this.itemId - o.itemId; // itemId asc, 음수 this 가 앞.
// return this.itemNm.compareTo(o.itemNm); // itemNm 기준
// itemId 우선 비교 같으면 itemNm 비교
return this.itemId == o.itemId ? this.itemNm.compareTo(o.itemNm) : this.itemId - o.itemId;
}
}
}
CollectionSortTest
package basic.sort;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionSortTest {
public static void main(String[] args) {
List<Item> list = new ArrayList<>();
list.add(new Item(3, "666"));
list.add(new Item(2, "777"));
list.add(new Item(5, "444"));
list.add(new Item(3, "111"));
// new Item(3, "666"), new Item(2, "777"), new Item(5, "444"), new Item(3, "111")
System.out.println(list);
// Collections.sort(list);
// System.out.println(list);
Collections.sort(list, (el1, el2) -> el1.itemId - el2.itemId);
System.out.println(list);
Collections.sort(list, (el1, el2) -> el1.itemNm.compareTo(el2.itemNm));
System.out.println(list);
Collections.sort(list, (o1, o2) -> o1.itemId == o2.itemId ? o1.itemNm.compareTo(o2.itemNm) : o1.itemId - o2.itemId);
System.out.println(list);
}
static class Item implements Comparable<Item> {
int itemId;
String itemNm;
Item(int itemId, String itemNm) {
this.itemId = itemId;
this.itemNm = itemNm;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemNm=" + itemNm + "]";
}
@Override
public int compareTo(Item o) {
// return this.itemId - o.itemId; // itemId asc, 음수 this 가 앞.
// return this.itemNm.compareTo(o.itemNm); // itemNm 기준
// itemId 우선 비교 같으면 itemNm 비교
return this.itemId == o.itemId ? this.itemNm.compareTo(o.itemNm) : this.itemId - o.itemId;
}
}
}
Perm
package basic.perm;
import java.util.Arrays;
import java.util.Iterator;
// 5 개 수 중 3 개의 수로 만들 수 있는 순열의 종류 그 구성
public class Perm_Basic {
static int[] src = {1, 2, 3, 4, 5};
static int[] tgt = new int[3]; // __ __ __ <- tgtIdx
static boolean[] select = new boolean[src.length]; // src 1,2,3,4,5 각각에 대한 이전 사용 여부
public static void main(String[] args) {
perm(0); // 첫 번째 자리를 채우면서 시작
}
static void perm(int tgtIdx) {
// 기저조건
if (tgtIdx == tgt.length) {
// 순열 한 가지가 완성
System.out.println(Arrays.toString(tgt));
return;
}
// tgtIndex 자리에 채울 수를 고려
for (int i = 0; i < src.length; i++) {
// tgtIdx 앞자리에 이미 사용된 수만 제외, 사용된 수는 select[] 에 기록
if (select[i]) continue;
tgt[tgtIdx] = src[i];
select[i] = true;
perm(tgtIdx + 1);
select[i] = false; // for 문의 i가 이전 재귀호출에서 선택되서 고려되었으므로 다음 i 를 고려하기 위해 i 선택 해제
}
}
}
Comb
package basic.comb;
import java.util.Arrays;
public class Comb_Basic {
static int[] src = {1, 2, 3, 4, 5};
static int[] tgt = new int[3]; // __ __ __ <- tgtIdx
// 조합은 select 필요 x
// src 의 맨 앞에서부터 tgt 의 각 자리를 순차적으로 고려하면서 채운다.
public static void main(String[] args) {
comb(0, 0);
}
static void comb(int srcIdx, int tgtIdx) {
// 기저조건
if (tgtIdx == tgt.length) {
// 순열 한 가지가 완성
System.out.println(Arrays.toString(tgt));
return;
}
if (srcIdx == src.length) return;
tgt[tgtIdx] = src[srcIdx]; // tgtIdx 자리에 srcIdx 의 수를 채운다. 선택
comb(srcIdx + 1, tgtIdx + 1); // 위 선택을 받아들이고 다음 자리를 채우러 재귀 호출
comb(srcIdx + 1, tgtIdx); // 위 선택 무시 (비선택) srcIdx 증가시켜서 다음 수를 고려하되 tgtIdx 는 그대로 현재 자리를 고려
}
}
Subset
package basic.subset;
// 부분집합은 조합의 합
public class Subset_Basic {
static int[] src = {1, 2, 3, 4, 5};
static boolean[] select = new boolean[src.length];
public static void main(String[] args) {
subset(0);
}
static void subset(int srcIdx) {
// 기저조건
if (srcIdx == src.length) {
printSubset();
return;
}
// 현재 srcIdx 에 대해서 선택, 비선택 이어간다.
select[srcIdx] = true; // 선택
subset(srcIdx + 1);
select[srcIdx] = false; // 비선택
subset(srcIdx + 1);
}
static void printSubset() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < select.length; i++) {
if (select[i]) sb.append(src[i]).append(" ");
}
System.out.println(sb);
}
}
인자약velog