[Java] 알고리즘 Day2

1. 델타 delta

- 상하좌우를 이동하는 기법

static int dy[] = { -1, 1,  0, 0};
static int dx[] = {  0, 0, -1, 1};

주의할 점

상하좌우 이동하면서 배열의 인덱스 값 범위에서 벗어나는지 검사

델타 활용 예시

static void print(int y, int x) {
	for (int d = 0; d < 4; d++) {
		int ny = y;
		int nx = x;
			
		while(true) {				
			ny = ny + dy[d];
			nx = nx + dx[d];
				
			if( ny < 0 || nx < 0 || ny >= 5 || nx >= 5 ) break; //인덱스 범위 검사
				System.out.print(map[ny][nx]);
		}
	}
	System.out.println();
}

 

- dx, dy를 조절하여 대각선 이동도 가능

static int dy[] = { -1,-1,  1, 1};
static int dx[] = { -1, 1, -1, 1};

 

- 8방향 이동

static int dy[] = { -1, 1,  0, 0, -1,-1,  1, 1};
static int dx[] = {  0, 0, -1, 1, -1, 1, -1, 1};

 

2. 재귀(Recursive)

- 함수가 자기 자신을 호출하는 프로그래밍 기법

주의할 점

재귀가 끝나는 조건을 항상 명시할 것

예시 - 팩토리얼

static int factorial(int n) {
	if (n==1) return 1; // 재귀 종료 조건
	else return n*factorial(n-1); // 재귀 호출
}

static void factorial(int n, int result) {
	if (n==1) {
		System.out.println(result);
		return;
	}
	factorial(n-1, result*n);
}

3. 정렬(Sort)

배열(array) vs 컬렉션(collection)

• 배열은 크기가 정해져있을 때 -> 배열의 크기는 고정
• 컬렉션은 크기를 모를 때 -> 컬렉션은 동적으로 크기 변경
• 속도 자체는 배열이 빠름
• 컬렉션이 유연성을 가짐

배열(Array) 사용

정수 정렬

int[] intArray = { 3, 5, 2, 7, 9, 4 };
Arrays.sort(intArray); // intArray 오름차순정렬
System.out.println(Arrays.toString(intArray));

문자열 정렬

String[] strArray = {"Hello", "ABC", "World"};
Arrays.sort(strArray, Collections.reverseOrder());
Arrays.sort(strArray);

정렬

방법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) {
		// itemId 우선 비교 같으면 itemNm 비교
		return this.itemId == o.itemId ? this.itemNm.compareTo(o.itemNm) : this.itemId - o.itemId;
	}			
}

 

방법2: Comparator 객체 전달

Arrays.sort(itemArray, new Comparator<Item>() {
	@Override
	public int compare(Item o1, Item o2) {
		return o1.itemNm.compareTo(o2.itemNm);
	}		
});
System.out.println(Arrays.toString(itemArray));

• 익명 클래스를 사용하여 Comparator 인터페이스를 구현
• itemNm을 기준 오름차순 정렬

방법3: 람다활용

Arrays.sort(itemArray, [정렬 조건]);
Arrays.sort(itemArray, (o1, o2) -> o2.itemId - o1.itemId );
System.out.println(Arrays.toString(itemArray));	

• itemId 기준 오름차순 정렬

컬렉션(Collection) 사용

-> ArrayList

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"));

ArrayList<String> list = new ArrayList<>();
        list.add("Banana");
        list.add("Apple");
        list.add("Cherry");

        // 기본 정렬 (자연 순서)
        Collections.sort(list);

ArrayList<String> list = new ArrayList<>();
        list.add("Banana");
        list.add("Apple");
        list.add("Cherry");

        // 사용자 정의 Comparator로 정렬 (문자열 길이 순)
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(), s2.length());
            }
        });

ArrayList<String> list = new ArrayList<>();
        list.add("Banana");
        list.add("Apple");
        list.add("Cherry");

        // 람다 표현식을 사용하여 정렬 (문자열 길이 순)
        Collections.sort(list, (s1, s2) -> Integer.compare(s1.length(), s2.length()));

4. 순열(Permuatation)

n개의 원소를 가지는 집합에서 순서를 고려하여 r개를 선택

- 모든 순열 조합 출력 예시(n = 5, r = 3)

static int[] src = {1, 2, 3, 4, 5};
static int[] tgt = new int[3]; // 선택된 원소들로 만든 순열을 담을 배열
static boolean[] select = new boolean[src.length]; // 선택되었는지 알려주는 배열
	
public static void main(String[] args) {
	perm(0);
}
	
static void perm(int tgtIdx) {
	if (tgtIdx == tgt.length) {
		System.out.println(Arrays.toString(tgt));
		return;
	}
		
	for (int i = 0; i < src.length; i++) {
		if (select[i]) continue;
			
		tgt[tgtIdx] = src[i];
		select[i] = true;
		perm(tgtIdx + 1);
		select[i] = false;
	}
}

 

5. 조합(Combination)

n개의 원소를 가지는 집합에서 순서를 고려하지 않고 r개를 선택

static int[] src = {1, 2, 3, 4, 5};
static int[] tgt = new int[3];
// 조합은 select 필요 X
// 맨 앞에서부터 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;
	}
    // src 배열을 모두 확인한 경우
	if( srcIdx == src.length) return;
    
     // 선택된 경우 (현재 srcIdx의 원소를 tgt 배열에 추가)
	tgt[tgtIdx] = src[srcIdx];
	comb(srcIdx + 1, tgtIdx + 1); // 다음 위치를 채우기 위해 재귀 호출
    
    // 선택되지 않은 경우 (현재 srcIdx의 원소를 무시)
	comb(srcIdx + 1, tgtIdx); // 다음 원소를 고려하기 위해 srcIdx를 증가시키고 tgtIdx는 그대로 유지
}

6. 집합(Subset)

가질 수 있는 모든 부분 집합의 목록을 출력

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); // 다음 원소를 고려하기 위해 재귀 호출
    
    // srcIdx 원소를 선택하지 않는 경우
	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);
}