[10일 차] 알고리즘 (Basic2)

---

25/02/07 (금)

금요일입니다!

일주일 중 가장 활력이 넘치는 날입니다!

주짓수 스파링하는 날이기도 하고, 곧 주말이라 놀기 제일 좋은 날이기도 합니다.

직장인들이 왜 불금 불금 하는지 이해가 갑니다.

내일은 여자친구와 1주년 기념 코엑스에서 서일페를 가기로 했습니다. 너무 기대되는군요.

저녁으로 미슐랭 빕구르망을 받은 딤섬을 예약했는데 이것도 기대됩니다!

일요일에는 CS공부한것 정리와 알고리즘 공부, 기사 공부를 해야하는데.. 할 수 있을까요..?

---

1.  WorkShop 발표

1) 요세푸스 문제

큐

FIFO 자료구조

Front에서 dequeue, Rear에서 enqueue

 

2.  강의

2.1.  Basic

1) delta2

package basic.delta;

import java.util.Arrays;

// 특정 위치에서 4방 탐색을 진행하는 경우, if-else if -else if - ... <= 코드의 길이가 길어지고, 가독성이 떨어지고 나누어서 생각하고
//  => 실수하기 쉽다.
// 한 방향으로 탐색할 수 있을 때까지 계속 탐색
public class DeltaTest2 {
    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]));
        }

        // 4방 탐색 - 상-하-좌-우
        print4x(2, 2);

    }

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

    static void print4x(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;  // while 문 종료

                System.out.println(map[ny][nx]);
            }
        }
    }
}

 

2) recursive

package basic.recursive;

public class Test {
    public static void main(String[] args) {
//        m1();
//        m1_param(0);
//        m2();
        m3();
    }

    //변수
    static int m1_i = 0;

    static void m1() {
        //local 변수 <= 재귀호출마다 stack에 새로 만들어지고 초기화 됨
//        int i = 0;

        //static 변수 <= 재귀호출마다 공유
//        System.out.println("m1() : " + m1_i++);
//        m1();
//        m2();
//        m3();
        m4(5);
    }

    static void m1_param(int i){
        //파라미터 변수
        System.out.println("m1_param() : " + i++);
        m1_param(i);
    }

    //기저 조건
    static int m2_cnt = 5;
    static void m2() {
        System.out.println("앞 m2() : "+ m2_cnt);
        //기저조건
        if(m2_cnt > 0) {
            m2_cnt--;
            m2();
        }
        System.out.println("뒤 m2() : "+ m2_cnt);
    }

    //Static 변수 이용
    static int m3_cnt = 5;
    static void m3() {
        if(m3_cnt == 0) return;

        System.out.println("앞 m3() : "+ m3_cnt);

        m3_cnt--;
        m3();
        m3_cnt++; //없으면 0으로 감소 한 후 계속 0 유지, 원복 필요

        System.out.println("뒤 m3() : "+ m3_cnt);
    }

    //파라미터 이용
    static void m4(int m4_cnt) {
        if(m4_cnt == 0) return;

        System.out.println("앞 m4() : "+ m4_cnt);

        m4(m4_cnt - 1); //호출 시 전달받은 m4_cnt는 변화X

        System.out.println("뒤 m4() : "+ m4_cnt);
    }
}

---

factorial

package basic.recursive;

public class Test2 {

    // factorial 계산을 재귀호출을 이용해서 처리, 결과값 처리 다양하게
    public static void main(String[] args) {
        factorial(5);

        int result = factorial2(5);
        System.out.println(result);

        factorial3(5, 1); // 두 번째 파라미터 값에 누적 곱으로 처리
    }

    // #1. 결과값을 static 변수
    static int result = 1;
    static void factorial(int n) {
        // 기저조건
        if( n == 1 ) {
            System.out.println(result); // 원하는 결과가 완성된 시점
            return;
        }

        // 계산
        result = result * n;

        // 재귀호출
        factorial(n - 1);
    }

    // #2. 결과값을 재귀호출의 return 값으로
    // 바닥부터 계산되어서 bottom up 으로 처리
    static int factorial2(int n) {
        // 기저조건
        if( n == 1 ) return 1;

        // n == 3 일 때,
        // 2 x 1 의 의 결과에 자신 3 을 곱해서 4 에게 리턴
        return n*factorial2(n - 1);
    }

    // #3. 결과값을 재귀호출의 parameter 값으로
    static void factorial3(int n, int result) {
        // 기저조건
        if( n == 1 ) {
            // result 에 이전 계산값이 존재
            System.out.println(result);
            return;
        }
        factorial3(n - 1, result * n); // 넘어온 이전 계산 값에 자신을 곱한다.
    }
}

 

3) ArraySort

배열 정렬

package basic.Ch06_sort;

import java.util.Arrays;
import java.util.Comparator;

public class ArraySortTest {
    public static void main(String[] args) {
//        //배열 정렬
//        int[] intArray = {3, 5, 2 ,7, 9, 4};
//
//        //int
//        System.out.println(Arrays.toString(intArray));
//        Arrays.sort(intArray);
//        System.out.println(Arrays.toString(intArray));
//
//        //String
//        String[] strArray = {"Hello", "UPlus", "URECA", "World"};
//        System.out.println(Arrays.toString(strArray));
//        Arrays.sort(strArray);
//        System.out.println(Arrays.toString(strArray));
//        Arrays.sort(strArray, Collections.reverseOrder()); //역정렬
//        System.out.println(Arrays.toString(strArray));

        //사용자 정의 클래스
        Item[] itemArray = {new Item(3, "66"), new Item(3, "77"), new Item(5, "44"), new Item(8, "11")};

        //#1 클래스에 정의
//        Arrays.sort(itemArray);
//        System.out.println(Arrays.toString(itemArray));

        //#2 Comparator 인터페이스 이용 - anonymous 객체
        //정렬 대상 클래스에 comparable 인터페이스 구현하지 않아도, 정렬 시점에 정렬 기준을 구현한 객체를 전달
//        Arrays.sort(itemArray, new Comparator<Item>() {
//            @Override
//            public int compare(Item o1, Item o2) {
//                return o1.itemId - o2.itemId; //natural ordering
//            }
//        });
//        System.out.println(Arrays.toString(itemArray));


        //#3 Comparator 인터페이스 이용 - lambda
        //정렬 대상 클래스에 comparable 인터페이스 구현하지 않아도, 정렬 시점에 정렬 기준을 구현한 객체를 전달
        Arrays.sort(itemArray, (o1, o2) -> o1.itemId == o2.itemId ? o1.itemName.compareTo(o2.itemName) : o1.itemId - o2.itemId);
        System.out.println(Arrays.toString(itemArray));
    }

    //객체들을 정렬할 때 기준이 필요
    //#1 클래스에 정의
//    static class Item implements Comparable<Item>{
//        int itemId;
//        String itemName;
//
//        Item(int itemId, String itemName) {
//            this.itemId = itemId;
//            this.itemName = itemName;
//        }
//
//        @Override
//        public String toString() {
//            return "Item [itemId=" + itemId + ", itemName=" + itemName + "]";
//        }
//
//        @Override
//        public int compareTo(Item o) { //정렬 기준 제공
////            return this.itemId - o.itemId; //natural ordering
////            return o.itemId - this.itemId; //natural ordering
////            return this.itemName.compareTo(o.itemName);
//            //itemId 우성 비교하는데 같은 값이면 itemName 비교
//            return this.itemId == o.itemId ? this.itemName.compareTo(o.itemName) : this.itemId - o.itemId;
//        }
//    }

    //#2 Comparator 인터페이스 이용
    static class Item{
        int itemId;
        String itemName;

        Item(int itemId, String itemName) {
            this.itemId = itemId;
            this.itemName = itemName;
        }

        @Override
        public String toString() {
            return "Item [itemId=" + itemId + ", itemName=" + itemName + "]";
        }

    }
}

---

컬렉션 배열 정렬

package basic.Ch06_sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionSortTest {
    public static void main(String[] args) {
        //ArrayList를 이용한 정렬
        List<Item> list = new ArrayList<>();
        list.add(new Item(3,"66"));
        list.add(new Item(2,"77"));
        list.add(new Item(5,"33"));
        list.add(new Item(8,"44"));

        System.out.println(list);

        //#1. Comparable
//        Collections.sort(list); //implements Comparable한 객체가 아닌 경우 컴파일 에러 발생
//        System.out.println(list);

        //#2. Comparator 인터페이스 구현 - lambda
        Collections.sort(list, (o1, o2) -> o1.itemId - o2.itemId);
        System.out.println(list);
    }

    //#1. Comparable
        static class Item implements Comparable<Item> {
        int itemId;
        String itemName;

        Item(int itemId, String itemName) {
            this.itemId = itemId;
            this.itemName = itemName;
        }

        @Override
        public String toString() {
            return "Item [itemId=" + itemId + ", itemName=" + itemName + "]";
        }

        @Override
        public int compareTo(Item o) { //정렬 기준 제공
//            return this.itemId - o.itemId; //natural ordering
//            return o.itemId - this.itemId; //natural ordering
//            return this.itemName.compareTo(o.itemName);
            //itemId 우성 비교하는데 같은 값이면 itemName 비교
            return this.itemId == o.itemId ? this.itemName.compareTo(o.itemName) : this.itemId - o.itemId;
        }
    }
}

 

4) 순열, 조합, 부분집합

자주 쓰니 외워두어야 합니다

---

순열(permutation)

package basic.Ch07_perm;

import java.util.Arrays;

public class BasicPerm {

    //기본 순열
    static int[] src = {1, 2, 3, 4, 5};
    static int[] tgt = new int[3]; //__ __ __ <= 현재 자리를 채우기 위해 src 전체를 고려하되, 현재 자리 이전 자리에 사용된 수 제외
    //현재 자리 이전 자리에 사용된 수
    static boolean[] select = new boolean[src.length]; // _f_ _t_ _f_ _t_ _f_

    public static void main(String[] args) {
        perm(0); //tgt의 맨 앞자리부터 시작
    }

    static void perm(int tgtIdx) { //tgtIdx => __ __ __
        //기저조건
        //이 조건 이전의 재귀호출로 이미 tgt 배열이 완성
        if(tgtIdx == tgt.length){
            System.out.println(Arrays.toString(tgt));
            return;
        }
        //현재 파라미터로 넘어온 tgtIdx 자리에 src로부터 채울 수를 선택, 고려
        //src 전체를 대상으로 하되, select 배열에 사용중인 것은 제외
        for (int i = 0; i < src.length; i++) {
            //앞자리에 사용된 수이면 skip
            if(select[i]) continue;

            tgt[tgtIdx] = src[i]; //선택

            select[i] = true; //선택 표시
            perm(tgtIdx+1); //다음 자리를 위한 재귀 호출
            select[i] = false; //선택 원복
        }
    }
}

---

조합(combination)

package basic.Ch08_comb;

import java.util.Arrays;

public class BasicComb {

    //기본 조합
    static int[] src = {1, 2, 3, 4, 5};
    static int[] tgt = new int[3]; //__ __ __ <= 현재 자리를 채우기 위해, src의 맨 앞에서부터 수를 선택/비선택 해가면서 tgt 개수를 채운다.
    //이전에 사용된 수 고려 X <= select 배열 X

    public static void main(String[] args) {
        comb(0, 0);
    }

    //조합
    //src의 srcIdx 자리의 수를 tgtIdx 자리에 선택? 비선택?
    static void comb(int srcIdx, int tgtIdx) {
        //기저조건
        if(tgtIdx == tgt.length) {
            System.out.println(Arrays.toString(tgt));
            return;
        }
        if(srcIdx == src.length) return; //기저조건 1개 더

        tgt[tgtIdx] = src[srcIdx]; //선택
        comb(srcIdx + 1, tgtIdx + 1); //위 선택을 받아들이고 다음 자리로 재귀호출
        comb(srcIdx + 1, tgtIdx); //위 선택을 받아들이지 않고 srcIdx만 증가시키는 효과
    }
}

---

부분집합

package basic.Ch09_subset;

public class BasicSubset {

    //기본 부분집합
    //부분집합의 경우의 수는 모든 가능한 조합의 수의 합

    static int[] src = {1, 2, 3, 4, 5};
    //tgt 배열 X <= 가능한 모든 경우를 선택하기 때문
    //조합은 src, tgt 맨 앞부터 선택/비선택을 해 가면서 tgt를 채우면 끝이지만
    //부분집합은 src의 맨 앞부터 선택/비선택을 끝까지 계속 한다

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

    //부분집합이 완성되면 select 배열을 기준으로 src의 선택된 수 출력
    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);
    }
}

 

추가) 디버그

인텔리제이(다른 IDE도 가능)에서 디버그가 가능합니다..! (처음 알음)

 

3.  마무리

1) WorkShop

• 점심시간 : ArraySort에서 만약 내가 ItemID 우선 비교하는데 같은 값이면 itemName 비교
• 만들어 보기 : 컬렉션 배열 정렬에서 Comparable 클래스 만들어보기
• WorkShop : 생활속에서 찾을 수 있는 순열, 조합, 부분 집합 찾기

오늘의 추천 문제

https://www.acmicpc.net/problem/15649
https://www.acmicpc.net/problem/1010
https://www.acmicpc.net/problem/2961

 

2) 더 공부할 것

• Override
• Overload
• this
• super
• Array sort
• toString
• StringBuilder
• BufferreadReader
• Tokenizer

(그냥 다 해야될것같은데)