특히, 첫 번째 vue 모듈 평가는 내가 공부를 많이 안하기도 했었지만, 개념적으로 이해가 잘되지 않아 많이 어려웠는데 JDBC같은 경우엔 예전에 해본 경험도 있고 조금 더 익숙하다보니 수업하고 실습하는 것이 더 재밌었다. 그리고 그만큼 1차시험을 만회하기 위해 더 노력하긴했는데 아직 결과가 나오진 않았지만, 스스로 후회없는 시험을 친 것 같아 다행이다.. 그럼 이번 강의 후기에 대해 작성해보겠다.

이번 주제는 다이나믹 프로그래밍 ( Dynamic Programing ) 즉, DP라고 불리는 주제였다. 사실 DP에 대해 매번 말만 들어보고 음~하고 넘어갔었는데 이번 강의를 통해 개념을 좀 더 잡을 수 있었다.

DP는 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘으로써, 테이블 정의 / 점화식 찾기 / 초기 값 정하기 순서 등을 통해 해결할 수 있다.

강의 내용들을 들으면서 생각해보니, 예전에 싸피를 준비하면서 관련 문제들을 풀 때, 접해본적이 있던 유형이였다. 그 당시에도 재밌어하면서 풀었던 기억이 있었는데, 이를 프로그래밍으로 해결하니 좀 더 간편하면서도 어렵고 신기해서 재밌었던 것 같다.

문제 정리!

1. 백준 자바 1463 1로만들기
2. 백준 자바 1003 피보나치함수
3. 백준 자바 1932 정수 삼각형
4. 백준 자바 1699 제곱수의 합
5. 백준 자바 9251 LCS

이 문제도 예전에 수학문제로 풀었던 적이 있었는데, 알고리즘으로 해결하려고 하니 좀 익숙하면서도 헷갈려서 당황스러웠다. 우선, 이 문제는 입력받은 두 개의 단어를 서로 비교하면서 만들 수 있는 공통으로 겹치는 부분 수열의 최장거리를 구하는 것이다. 즉, 두 개의 단어를 각각 가로 세로에 두고, 겹치는 부분을 체크하면서 문제를 해결하였다

대충 결과물은 이렇고, 코드를 보면서 설명하겠다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q5_1 {

    static char [] char1;
    static char [] char2;

    // 백준 9251 G5 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 받은 문자열들 각각 단어배열로 변경
        char1 = br.readLine().toCharArray();
        char2 = br.readLine().toCharArray();

        // 공집합 생각해서 비교하는 판 1씩 크기 증가
        int [][] dp = new int[char1.length +1 ][char2.length+1];


        // 0은 공집합이니 넘기고 1부터 진행
        for(int i = 1; i<=char1.length; i++) {
            for(int j = 1; j<=char2.length; j++) {
                // 같은 경우 +1
                if(char1[i-1]==char2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                // 다른경우 (이전 행 or 이전 열) + 1
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }// for fin
        }// for fin

        // 제일 마지막 값 출력
        System.out.println(dp[char1.length][char2.length]);

    }
}

우선, 입력 받은 두 개의 문자열을 편하게 비교하기 위해 바로 단어열로 변경해주었다. 다음으로, 두 집합을 비교하여 최종 값을 구하는 배열을 생성하는데, 두 부분집합이 아예 안겹치는 경우도 존재할테니, +1하여 공간을 생성해주었다.

다음으로, 첫 번째 문자열을 기준으로하여 두 번째 문자열을 하나씩 비교하는데, 가로, 세로가 서로 같은 경우 그 기준 왼쪽 대각선 값 + 1을 해주고, 만약 다른 경우엔 해당 좌표를 기준으로 세로열과 가로행중 더 큰 값을 그대로 물려받아 지정하게끔 구현하였다.

문제를 해결한 후 다른 분들은 어떤 방식으로 해결했는지 궁금해서 좀 알아봤는데, 필자는 이 문제 같은경우엔 두 문자열의 최대길이가 각각 1,000이길래 그냥 이중 반복문을 해도 1,000,000 이므로 진행했었다. 단, 이와같은 방식은 길이가 더 길어지면 오류가 발생하므로, 값이 커질 땐 재귀를 활용해서 해결해야한다. 물론 그럴 경우 메모리를 많이 잡아먹기에, 지금처럼 주어진 값이 작은 경우엔 단순히 이중반복문을 진행하고, 값이 클 땐 재귀를 활용하면 좋을 것 같다.

굿

따라서, N이 주어졌을 때, n보다 작은 가장 큰 제곱 수를 구하고 이를 뺀 후, 남은 수 n 에서 가장 큰 제곱 수를 계속 반복해서 빼는 방식으로 구현하였다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q4_1 {
    static int count =0;
    // 백준 1699 S2 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        maxRoot(n);

        System.out.println(count);

    }

    public static int maxRoot(int n) {
        if(n == 0) {
            return count;
        }
        int maxN = 0;
        for(int i = 1; i*i<=n; i++) {
             if(i*i<=n) {
                 maxN = i;
             }
        }// for fin
        count++;
        maxRoot(n- maxN*maxN);
        return count;
    }

}

하지만, 오류가 발생했다. 반례를 찾아보니 n = 18 인경우 내가 푼 방식으로 해결하면 18 = 16 + 1 + 1 로 3 이 나오는데, 실제 답은 9 + 9 로 2여야한다.

따라서, 점화식을 활용해서 이 문제를 풀어야겠다고 생각했다. 예를들어 dp[i]의 값은 그냥 순수하게 i번째 값과, 중간에 제곱근이 있는경우 그 값을 뺀 dp번째 값의 +1을 계속 비교해줘야한다.

이게 무슨 소리냐면, 예를들어 i = 16인경우, ( dp[16], dp[16-4] +1 ) ( dp[16], dp[16-9] +1 ) ( dp[16], dp[16-16] +1)

이런식으로 비교하면 답을 구할 수 있다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q4_2 {
    // 백준 1699 S2 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int count = maxRoot(n);

        System.out.println(count);

    }

    // 계산하기
    public static int maxRoot(int n) {
        int dp [] = new int [n+1]; // 0부터 n까지 사용하기 위함
        Arrays.fill(dp, Integer.MAX_VALUE); // 초기에 제일 큰 값 세팅해서 최소 값 비교에 용이하게함
        dp[0] = 0;

        for(int i = 1; i<=n; i++) {
             for(int j = 1; j*j<=i; j++ ) {
                 dp[i] = Math.min(dp[i], dp[i - j*j] +1 );
             }
        }// for fin

        return dp[n];
    }// maxRoot fin


}

굿

이 문제는 제일 처음 삼각형의 층수인 n을 주고, 각각의 노드에 따라 더해서 제일 큰 값을 구하는 문제이다. 따라서, 입력 받은 값들을 배열에 깔끔하게 저장하기 위해 n에 따른 경우의 수를 구하는 checknum 메서드를 먼저 생성하여 값을 구하였고, 이후 calc 메서드를 생성하여 값을 구하였다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q3_1 {
    static boolean visited[];
    static int n;
    static int count;
    static Integer maxNum[];
    // 백준 1932 S1 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        n = Integer.parseInt(br.readLine());
        int checknum = checknum(n);
        visited = new boolean[checknum];
        List<Integer> arrList = new ArrayList<>();
        maxNum = new Integer[checknum];

        int dept = 2;
        // 값 받기
        for(int i = 0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<=i; j++) {
                arrList.add(Integer.parseInt(st.nextToken()));
            }
        }        
        calc(dept,checknum,arrList);
    }

    // 총 공간 체크
    public static int checknum(int n) {
        int sum = 0;
        for(int i=1 ; i<=n; i++) {
            sum+= i;
        }
        return sum;
    }
    public static void calc(int dept, int checknum, List<Integer> arrList) {
        maxNum[0] = arrList.get(0);    // 첫 번째 값 세팅
        int cnt = 1;
        for(int i = 1; i<n; i++) { // n개의 층
            for(int j = 0; j<dept; j++) {
                // 제일 왼쪽, 제일 끝
                if(j == 0 || j == dept-1) {
                    maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
                }

                else {
                    maxNum[cnt] 
                            = Math.max( maxNum[cnt-dept] + arrList.get(cnt),  maxNum[cnt-dept+1] + arrList.get(cnt));    
                }
                cnt++;
            }
            dept++;
        }// for fin

        for(Integer i : maxNum) {
            System.out.print(i + " ");
        }
        System.out.println();
        List <Integer> maxList = Arrays.asList(maxNum);
        System.out.println(Collections.max(maxList));

    }
}

결과값을보면

근데 입력받은 숫자 만큼 return은 되었으나. 이상하게 더해진다. 삼각형 기준 왼쪽 끝과 오른쪽 끝을 묶었기에 이상하게 나온 것 같아 이부분을 수정해주었다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q3_2 {
    static int n;
    static Integer maxNum[];
    // 백준 1932 S1 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        n = Integer.parseInt(br.readLine());
        int checknum = checknum(n);
        System.out.println(checknum);
        List<Integer> arrList = new ArrayList<>();
        maxNum = new Integer[checknum];

        int dept = 2;
        // 값 받기
//        for(int i = 0; i<n; i++) {
//            st = new StringTokenizer(br.readLine());
//            for(int j = 0; j<=i; j++) {
//                arrList.add(Integer.parseInt(st.nextToken()));
//            }
//        }
//        
        calc(dept,checknum,arrList);


    }

    // 총 공간 체크
    public static int checknum(int n) {
        int sum = 0;
        for(int i=1 ; i<=n; i++) {
            sum+= i;
        }
        return sum;
    }
    public static void calc(int dept, int checknum, List<Integer> arrList) {
        maxNum[0] = arrList.get(0);    // 첫 번째 값 세팅
        int cnt = 1;
        for(int i = 1; i<n; i++) { // n개의 층
            for(int j = 0; j<dept; j++) {
                // 제일 왼쪽, 제일 끝
                if(j == 0) {
                    maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
                }else if(j == dept-1) {
                    maxNum[cnt] = maxNum[cnt-dept] + arrList.get(cnt);
                }

                else {
                    maxNum[cnt] 
                            = Math.max( maxNum[cnt-dept] + arrList.get(cnt),  maxNum[cnt-dept+1] + arrList.get(cnt));    
                }
                cnt++;
            }
            dept++;
        }// for fin

        for(Integer i : maxNum) {
            System.out.print(i + " ");
        }
        System.out.println();
        List <Integer> maxList = Arrays.asList(maxNum);
        System.out.println(Collections.max(maxList));

    }

}

여기선 잘한 것 같은데 오류가 났다. 생각해보니 삼각형의 크기가 500, 수의 경우 9999까지 이므로 합계 같은 경우 Integer을 벗어날 가능성이 높다고 생각했다. 따라서, 누적된 값을 저장해주는 maxNum 의 타입을 Integer에서 Long으로 바꿔주었다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q3_3 {
    static int n;
    static long maxNum[];
    // 백준 1932 S1 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        n = Integer.parseInt(br.readLine());
        int checknum = checknum(n);
        List<Integer> arrList = new ArrayList<>();
        maxNum = new long[checknum];

        int dept = 2;
        // 값 받기
        for(int i = 0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<=i; j++) {
                arrList.add(Integer.parseInt(st.nextToken()));
            }
        }

        calc(dept,checknum,arrList);
    }

    // 총 공간 체크
    public static int checknum(int n) {
        int sum = 0;
        for(int i=1 ; i<=n; i++) {
            sum+= i;
        }
        return sum;
    }
    public static void calc(int dept, int checknum, List<Integer> arrList) {
        maxNum[0] = (long) arrList.get(0);    // 첫 번째 값 세팅
        int cnt = 1;
        for(int i = 1; i<n; i++) { // n개의 층
            for(int j = 0; j<dept; j++) {
                // 계속 작은 삼각형을 그리면서 비교하는 방식으로 이해하면 편하다.
                if(j == 0) { // 삼각형의 왼쪽이 해당 행에서 첫 번째인 경우, 가운데 값 + 현재값
                    maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
                }else if(j == dept-1) {// 삼각형의 오른쪽이 해당 행에서 마지막인 경우, 가운데 값 + 현재값
                    maxNum[cnt] = maxNum[cnt-dept] + arrList.get(cnt);
                }
                else {// 현재값 기준 11시방향, 1시방향 값 서로 비교
                    maxNum[cnt] 
                            = Math.max( maxNum[cnt-dept] + arrList.get(cnt),  maxNum[cnt-dept+1] + arrList.get(cnt));    
                }
                cnt++;
            }
            dept++;
        }// for fin
        // 경우에 따라 int의 한계치를 넘을 수도 있으므로 long으로 세팅
        long max = Arrays.stream(maxNum).max().getAsLong();
        System.out.println(max);
    }// calc fin

}

굿

이번 문제는 점화식과 관련있었던 것 같다. d[n] = d[n-1] + d[n-2]를 반복하면서 최종적으로 d[0]은 0, d[1] = 1 를 return한다. 0과 1을 호출한 횟수를 각각 구하는 문제이다.

미리 피보나치 메서드를 만들어 놓고, n의 최대값인 40까지의 경우의 수를 미리 다 구해 놨다. 이후 n의 값에 맞게 각각 출력하는 느낌으로 구현했다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q2_1 {
    static int [] zeroArr, oneArr ;
    // 백준 1003 S3 
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        zeroArr= new int [41]; // n의 최대가 40이므로 +1
        oneArr = new int [41];

        // n개의 테스트 케이스 실행
        for(int i =0; i<n; i++) { 
            int temp = Integer.parseInt(br.readLine());
            fibonacci(); // 모든 경우의 수 미리 계산
            // 해당 경우의 수 출력
            sb.append(zeroArr[temp] + " " + oneArr[temp] + "\n");            
        } // for fin

        System.out.println(sb.toString().trim());
    }
    // 모든 경우의 수 미리 구해두기
    public  static void fibonacci() {
        zeroArr[0] = 1;
        oneArr[0] = 0;
        zeroArr[1] = 0;
        oneArr[1] = 1;

        for(int i = 2; i<=40; i++) {
            zeroArr[i] = zeroArr[i-1] + zeroArr[i-2];
            oneArr[i] = oneArr[i-1] + oneArr[i-2];
        }
    }

}

0의 경우의 수는 zeroArr, 1의 경우의 수는 oneArr 배열에 계속 누적된다. 따라서, zeroArr은 zeroArr[0] = 1, zeroArr[1] = 0이고, oneArr은 oneArr[0] = 0, oneArr[1] = 1을 지정해주고, 나머지는 문제 그대로 반복하여 해결해주었다.

굿

이번 주제는 다이나믹프로그래밍, 즉 DP에 관한 내용이였다. 이런 스타일의 문제들은 예전에 싸피를 살짝 준비하면서 접한 경험이 있어, 재미있게 풀었던 것 같다.

우선, 이번 문제는 정수 x가 3의 배수면 3으로 나누고, 2의 배수면 2로 나누고 두 경우에 해당 되지않으면 1을 뺀다. 이 과정을 반복하여 1을 만드는 최솟값을 구하는 문제이다.

예를들어, x가 12이라면 D[12] 라고 했을 때, D[12]의 값은 min( D[6]+1 , D[4] +1, D[11] +1 )이다. 이런식으로 반복하여 D[1]~ D[12]까지의 각각의 최솟값들 체크하여 활용하는 문제이고, 초기 값으로 D[1]은 아무런 변화가 없으므로 0을 지정하여 문제를 진행하였다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q1_1 {
    // 백준 1463 S3 
        public static void main(String [] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());

            int cnt = 0;
            int [] arr = new int [n+1];

            // 초기 배열 값 세팅
            arr[1] = 0;

            for(int i =2; i<=n; i++) {
                arr[i] = arr[i-1]+1;
                if(i%2 == 0) {arr[i] = Math.min(arr[i], arr[i/2]+1);}
                if(i%3 == 0) {arr[i] = Math.min(arr[i], arr[i/3]+1);}
            }
            System.out.println(arr[n]);
        }
}

i = 1 에 해당되는 arr[1]은 기본적으로 0을 세팅해뒀으므로, 반복문은 2부터 n까지 진행한다. 다음으로 arr[i] 에 기본적으로 arr[i-1]+1 을 지정하고, 이 값과 arr[i/2]+1, arr[i/3]+1 을 각각의 경우에 맞게 비교하여 더 작은 값을 지정해주었다. 마지막으로, arr[n]의 값을 호출하면서 마무리했다.

아무래도 감을 익히는 문제이기에 수월하게 해결하였다.

굿

• Ice Breaking 및 코드 리뷰

1. Ice Breaking 주제: 어느덧, 우리의 수업 종료 까지 D-100 일 남았는데, 각자의 소감을 공유해보자

1) 우정

• 시간이 참 빨리 가는 것 같다.
• 배운게 많은 것 같으면서도, 없는 것 같다. 이를 활용해서 취업이 될지 걱정이 된다.
• 초반엔 열심히 한 것 같은데 약간 나태해진 것 같다.
• 프로젝트 한 달 남았는데, 좀 불안하다.

2) 재동

• 시간이 참 빨리 가는 것 같다.
• 프로젝트 기대된다.

3) 태용

• 오히려 초반보다 요즘 더 열심히 사는 것 같다.
• 자격증이나 공모전 등 개인적인 일정이 많아 바쁘다.

4) 현희

• 시간이 빠르게 가는게 소름끼친다.
• 자격증 준비하느라 스트레스 받는다.
• 스터디도 여러개 하다보니 바쁘다.

5) 준렬

• 시간이 참 빠르다.
• 지금까지는 벅찬 일정에 대해 어느정도 까지 감당가능한지 테스트 하는 시간이였다.
• 이젠 역량을 파악했으니, 다시 열심히 달려야겠다.

2. 코드 리뷰

1) HashMap, LinkedHashMap, Hashtable 비교

1-1) HashMap

• 기본 설명 : 가장 일반적으로 사용되는 Map 구현체
• 동기화: 동기화되지 않음. 멀티스레드 환경에서 안전하지 않습니다.
• 순서 보장: 삽입 순서를 보장하지 않음.
• null 허용: 하나의 null 키와 여러 개의 null 값을 허용합니다.
• 성능: 성능이 좋고, 기본적으로 O(1)의 시간복잡도를 가집니다.
• 사용 예: 단일 스레드 환경에서 키와 값을 빠르게 저장하고 검색해야 할 때.

1-2) LinkedHashMap

• 기본 설명: HashMap의 확장 버전으로, 삽입 순서를 유지합니다.
• 동기화: 동기화되지 않음. 멀티스레드 환경에서 안전하지 않습니다.
• 순서 보장: 삽입된 순서(혹은 접근 순서)를 보장합니다.
• null 허용: 하나의 null 키와 여러 개의 null 값을 허용합니다.
• 성능: HashMap과 유사하지만, 추가적인 순서 유지를 위한 오버헤드가 존재합니다.
• 특징: 순서를 유지하는 데 필요한 추가적인 메모리가 필요합니다.
• 사용 예: 순서를 유지하면서 데이터를 저장하고 검색해야 할 때.

1-3) Hashtable

• 기본 설명: 예전부터 존재하던 Map 구현체로, HashMap과 유사하지만 동기화됩니다.
• 동기화: 동기화됨. 멀티스레드 환경에서 안전합니다.
• 순서 보장: 삽입 순서를 보장하지 않음.
• null 허용: null 키와 null 값을 허용하지 않음.
• 성능: 동기화로 인해 HashMap보다 성능이 낮습니다.
• 사용 예: 멀티스레드 환경에서 안전하게 키와 값을 저장하고 검색해야 할 때.

2) Arrays.sort , Collections.sort 비교 참고 티스토리

2-1) Arrays.sort()

• 사용 대상: 배열 (primitive 배열 및 객체 배열)
• 정렬 알고리즘: Dual-Pivot Quicksort (primitive 배열), Timsort (객체 배열)
• 시간 복잡도: 평균적으로 O(n log n) , 최대 O(n^2)
• 동기화: 동기화되지 않음 (Not thread-safe)

2-2) Collections.sort()

• 사용 대상: 컬렉션 (주로 List)
• 정렬 알고리즘: Timsort
• 시간 복잡도: 평균적으로 O(n log n)
• 동기화: 동기화되지 않음 (Not thread-safe)

오름차순에선, 평균적으론 시간 복잡도가 비슷하나 최악의 경우엔 Arrays.sort()는 시간 복잡도 문제가 발생하는 경우가 있다.

추가적으로 오름차순이 아닌 내림차순의 경우도 비교해보자.

Array.sort() => Arrays.sort(intArray, Collections.reverseOrder());

Collections.sort() => Collections.sort(intList, Collections.reverseOrder());

이처럼, 두 경우 모두 reversOrder() 를 활용해야 정렬이 올바르게 되는 것을 알 수 있다!

끝

우선 이번 주제는 정렬 이였다. 사실 정렬은 기본적으로 sort나 collection에 대해서만 생각했는데 강의를 들어보니 생각보다 정렬의 종류도 많고 방식도 다양하다는 것을 알게 됐다.

1. Merge Sort 약간 반 나누고 반나누고 반복해서 1될때까지 하는 느낌 Stable sort 로써, 우선 순위가 같으면 그대로 고정.

2. Quick Sort 피벗 값을 임의로 지정해서, 해당 값 기준 왼쪽은 작고, 오른쪽은 더 큰 그런 위치 잡음. 그 후 왼쪽 따로 정렬/ 오른쪽 따로 정렬 근데 얜 우선순위 정렬 아니고, 최악의 경우 O(N^2) 이므로, 걍 쓰지말 것

3. Counting Sort 나온거 개수 체크한다음 나열 ex ) 1아 4개 2가 3개네 -> 1111222 이런느낌 단, 범위가 크면 못쓰므로 수가 한정적일 때만 가능!

4. Radix sort 자릿수 기준 정렬 ( 1의자리, 10의자리 ... )

O(DN)

위의 두갠 원소들끼리 서로 정렬하는 Comparison Sort 아래 두갠 Non-Comparison Sort로 원소들 끼리 비교x

근데 이런거 다 배제하고 코테는 사실 함수 있으면 있는거 쓰는게 좋겠지

Stl sort => sort 기준 내가 정함

아마 이번에 우선순위 큐 풀때 compare 한거처럼 그런 느낌 인듯! 재밌었다 굿굿

문제 정리!

1. 백준 자바 11650 좌표 정렬하기

2. 백준 자바 5648 역원소 정렬
3. 백준 자바 1181 단어 정렬

4. 백준 자바 2910 빈도 정렬

5. 백준 자바 7795 먹을 것인가 먹힐 것인가

이 문제는 제일 처음 t 개의 테스트 케이스가 주어지고 그다음 집합 A , B의 크기가 주어진다. 그 다음 각각의 크기에 맞는 값들이 주어지고 해당 값들을 비교하여 B보다 A가 더 큰 경우의 수를 누적해서 출력한다. 이 과정을 t번 반복하는 문제이다.

보면 t에 대한 언급은 크게 없으니 시간 복잡도에 대해 큰 문제가 없을 것 같지만, A,B의 크기인 N,M의 범위가 1 <= N,M<= 20,000 이므로 N,M이 각각 최대 값인 20,000 일 경우 단순 서로 쌍으로 곱하면 400,000,000으로 런타임 에러가 발생하게 된다. 따라서, N과 M을 O(N) 으로 구하는게 중요한 문제이다.

제일 처음 접근한 방식은, 집합 A의 인자들을 하나씩 B에 추가하고, 추가함과 동시에 해당 값보다 작은 값들을 구하는 느낌으로 고안했다. 이 과정에서 수업시간에 배웠던 stream과 람다를 활용해보자! 라는 느낌으로 구현했다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Ox12_Q5_1 {
    // 백준 7795 S3 먹을 것인가 먹힐 것인가
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        // 테스트 케이스 수 만큼 입력받음
        for(int i = 0 ; i<t; i++) {
            int cnt = 0;
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 데이터 배열에 저장
            int [] aArr = new int[n];
            List<Integer> bArr = new ArrayList();

            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n; j++) {
                aArr[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++) {
                bArr.add(Integer.parseInt(st.nextToken()));
            }
            // bArr 정렬 후 인덱스 번호 체크
            Collections.sort(bArr);
            // A가 B보다 큰 쌍의 개수 체크
            for(int j = 0; j<aArr.length; j++) {
                int temp = aArr[j];
                cnt += (int) bArr.stream().filter(x->x<temp).count();                
            }
            sb.append(cnt).append("\n");
        }// for fin
        System.out.println(sb.toString().trim());
        br.close();
    }

}

보면 값을 각각 다 입력 받은 후, bArr을 정렬한 후 aArr의 요소를 추가하여 해당 요소보다 작은 count를 구하는 방식이다. stream을 활용하였다.

망했다. 애초에 이 방식은 기대도 안하긴 했다. 그냥 스트림 연습하려고 썼다ㅎ 다음 방식은 bArr을 정렬하기 전에, aArr의 요소를 먼저 집어넣고 정렬한 다음 indexOf를 활용하는 방식이다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Ox12_Q5_2 {
    // 백준 7795 S3 먹을 것인가 먹힐 것인가
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        // 테스트 케이스 수 만큼 입력받음
        for(int i = 0 ; i<t; i++) {
            int cnt = 0;
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 데이터 배열에 저장
            int [] aArr = new int[n];
            List<Integer> bArr = new ArrayList();

            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n; j++) {
                aArr[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++) {
                bArr.add(Integer.parseInt(st.nextToken()));
            }

            // A가 B보다 큰 쌍의 개수 체크
            for(int j = 0; j<aArr.length; j++) {
                int temp = aArr[j];
                // bArr 복제
                List<Integer> bArr2 = new ArrayList<>(bArr);
                bArr2.add(temp);
                // bArr2 정렬 후 인덱스 번호 체크
                Collections.sort(bArr2);
                cnt += bArr2.indexOf(temp);
            }
            sb.append(cnt).append("\n");
        }// for fin
        System.out.println(sb.toString().trim());
        br.close();
    }

}

? 이번엔 진짜 될 줄 알았는데 사실 실패하길래 약간 놀랬다. 실은 indexOf(n)의 시간 복잡도가 O(1)인줄 알았는데, 알고보니 O(n)이였다 ㅎㅎ그럼 틀려야지

사실 문제 특성상 데이터 입력 부분은 달라질 것이 없으니 무조건 정렬에서 갈리겠다고 생각했다. 이에 따라 고민 하던 중 예전에 이진탐색에 대해 했던 적이 있어서 관련 방식으로 고안해봤다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Ox12_Q5_3 {
    // 백준 7795 S3 먹을 것인가 먹힐 것인가
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        // 테스트 케이스 수 만큼 입력받음
        for(int i = 0 ; i<t; i++) {
            int cnt = 0;
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            // 데이터 배열에 저장
            int [] aArr = new int[n];
            int [] bArr = new int[m];


            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n; j++) {
                aArr[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++) {
                bArr[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(bArr);
            // A가 B보다 큰 쌍의 개수 체크
            for(int j = 0; j<aArr.length; j++) {
                int temp = aArr[j];
                cnt += compareAB(temp,bArr);
            }
            sb.append(cnt).append("\n");
        }// for fin
        System.out.println(sb.toString().trim());
        br.close();
    }

    // 이진 탐색으로 값 비교
    public static int compareAB(int temp, int bArr[]) {
        int left = 0;
        int right = bArr.length;
        // 왼쪽이 오른쪽보다 작은 경우 fin
        while(left<right) {
            int middle = (left+right)/2;
            // 현재 값이 중앙 값보다 큰 경우
            if(temp>bArr[middle]) {
                left = middle + 1;
            }
            // 현재 값이 중앙 값보다 작은 경우
            else {
                right = middle;
            }
        }
        return left;
    }

}

현재의 비교할 요소와 배열 bArr을 인자로 받는다. 다음으로 비교할 요소 temp와 bArr의 중앙값을 계속해서 비교하는데, 만약 중앙값보다 현재 값이 크다면 left는 중앙+1, 작다면 right는 중앙값으로 체크하는 방식을 반복한다. 이 과정을 반복하여 while문 밖으로 나오게 되면 temp보다 작은 값의 개수를 return하게 된다.

굿

이 문제는 빈도라는 단어를 보자마자, 예전에 활용했던 getOrDeafult 함수가 떠올랐다. 따라서, 값들을 먼저 받아서 빈도를 계산한 후 해당 값들을 sort와 compareTo를 활용해서 해결하는 방식으로 구상했다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Ox12_Q4_1 {
    // 백준 2910 S3 빈도 정렬
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // n , c 세팅
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        // n개의 개수 세팅
        Map <String,Integer>cArrMap = new HashMap<>();
        st = new StringTokenizer(br.readLine());

        // 입력받은 문자 별 중복 개수 체크
        for(int i = 0; i<n; i++) {
            String temp = st.nextToken();
            cArrMap.put(temp, cArrMap.getOrDefault(temp, 0)+1);
        }

        List<String> keySet = new ArrayList<>(cArrMap.keySet());

        // Value 값으로 내림차순 정렬
        // 위 comparator 람다 표현식으로
        keySet.sort((o1, o2) -> cArrMap.get(o2).compareTo(cArrMap.get(o1)));

        // sb에 hashmap 값들 추가
           for(String key : keySet) {
           int value = cArrMap.get(key);
           for(int i = 0; i<value; i++) {
               sb.append(key + " ");
           }
       }
       System.out.println(sb.toString().trim());
    }
}

먼저 값들을 받아 준 후, 빈도를 계산하기 위한 Hashmap을 생성해준다. 그리고 n개 만큼 반복하여 입력 받음과 동시에 각각의 빈도를 저장한다. 이후 arrayList에 정렬하면서 저장해주고, sb에 추가하여 출력하는 방식이다.

? 틀렸다.

예제는 통과했었으나, 3퍼에서 애매하게 틀렸길래 이건 단단히 글러먹었다고 생각했다. 반례 사례들을 알아보니, 해당 방식으로 구현하다보면 빈도 수가 같은 경우 먼저 입력된 숫자가 먼저 출력되어야하는데 해당 부분에서 오류가 발생한 것이었다. 예를 들면, 6 2 2 1 1 2 1 2 라고 입력하면, 1, 2가 빈도수가 같으므로, 2가 먼저 입력되었으므로, 2 2 2 1 1 1 이 정답인데, 1 1 1 2 2 2 로 출력 아무래도 정렬되는 과정에서 더 작은 수가 앞으로 오게끔 되어있어서 그런 것 같다.

따라서 해당 문제를 해결하기 위해 고안하던 중, HashMap의 형태는 유지하되, 입력된 순서를 기억하는 LinkedHashMap이라는 것을 알게 되었다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Ox12_Q4_2 {
    // 백준 2910 S3 빈도 정렬
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // n , c 세팅
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        // n개의 개수 세팅
        Map <String,Integer>cArrMap = new LinkedHashMap<>();
        st = new StringTokenizer(br.readLine());

        // 입력받은 문자 별 중복 개수 체크
        for(int i = 0; i<n; i++) {
            String temp = st.nextToken();
            cArrMap.put(temp, cArrMap.getOrDefault(temp, 0)+1);
        }

        List<String> keySet = new ArrayList<>(cArrMap.keySet());

        // Value 값으로 내림차순 정렬
        // 위 comparator 람다 표현식으로
        keySet.sort((o1, o2) -> {
            int precompare = cArrMap.get(o2).compareTo(cArrMap.get(o1));
            // 만약 value 차이가 같다면, 입력 순서 유지
            if(precompare == 0) {
                return 0; // LinkedHashmap 특성, 입력 순서대로 key 유지
            }
            return precompare;
        }); // sort fin

        // sb에 hashmap 값들 추가
       for(String key : keySet) {
           int value = cArrMap.get(key);
           for(int i = 0; i<value; i++) {
               sb.append(key + " ");
           }
       }// for fin

       System.out.println(sb.toString().trim());
    }

}

마지막 쯤 정렬하는 구문을 보면, LinkedHashMap을 활용하기도 했지만, 정렬 구문에 대해서도 차이가 있다는 것을 알 수 있다. value ( 빈도 수 )가 차이가 없다면, return 0을 통해, 입력 순서가 유지 될 수 있도록 하였고, 마지막 출력은 똑같은 방식으로 해결했다.

굿

이 문제도 정렬하는 문제이므로, 이전 문제들 처럼 우선순위 큐를 사용해야겠다고 생각했다. 다만, 그 과정에서 문자열의 길이<를 기준으로 1차 정렬하고, 만약 길이가 같으면 사전 순이며, 중복된 단어는 하나만 남기고 제거해야되므로 총 세 가지 조건을 고려해야되는 문제이다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Ox12_Q3_1 {
    // 백준 1181 S5 단어 정렬
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        String [] str = new String[n];
        Set<String> set = new HashSet<>(); // 중복 단어 제거용 Set
        PriorityQueue<word> prique = new PriorityQueue<>(1, new wordComparator());

        // 값 입력 부분
        for(int i = 0 ; i<n; i++) {
            String temp = br.readLine();
            // 값이 중복이 아니라서 정상적으로 들어가는 경우
            if(set.add(temp)) { 
                prique.offer(new word(temp,temp.length()));
            }
        }// for fin
        br.close();

        // 출력 부분
        while(!prique.isEmpty()) {
            word w = prique.poll();
            sb.append(w.word).append("\n");
        }// while fin
        System.out.println(sb.toString().trim());
    }
}

class word{
    String word;
    int wordLen;

    word(String word, int wordLen){
        this.word = word;
        this.wordLen = wordLen;
    }
}

class wordComparator implements Comparator<word>{
    @Override
    public int compare(word w1, word w2) {
        // 길이가 같은 경우 -> 사전 순 정렬
        if (w1.wordLen == w2.wordLen) {
            return w1.word.compareTo(w2.word);
        } 
        // 기존 -> 문자열 길이 정렬
        else {
            return w1.wordLen - w2.wordLen;
        }
    }
}

구문 자체는 그렇게 복잡하진 않다. prique(우선순위 큐)에 입력받은 값과 해당 길이를 넣어주고, 출력하면서 정렬한다. 이 과정에서 중복을 바로 제거하기 위해 Hashset 형태로 입력한다.

이때 우선순위 큐의 코드는 먼저 길이가 같으면 사전 순으로 comparTo 함수를 통해 작은 값이 먼저 출력되게끔 하고, 길이가 다르면, 문자열 길이를 기준으로 정렬된다.

굿

이 문제는 값을 받을 때마다 뒤집은 다음 해당 원소들을 오름차순으로 정렬하는 문제이다. 이번 문제도 이전 문제처럼 우선순위 큐를 이용하면 쉽게 정렬되겠다! 라고 생각했었다. 여기서 왜 sort를 사용하지 않았냐고 생각할 수도 있겠지만.. 실은 나도 잘 모르겠다 ㅋㅎ 그냥... 문뜩 우선 순위큐가 쉽게 정렬되는 것 같아서 공부할 겸 써봐야지! 했는데 딸깍 되는건 아니였다.. 뭐 이참에 공부하고 좋은 것 같아서 계속 이걸 활용해서 해결해봤다.

package test12;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Ox12_Q2_2 {
    static String [] strArr;
    // 백준 5648 S5 역원소 정렬
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 첫 줄 먼저 체크
        strArr = br.readLine().split(" ");
        int n = Integer.parseInt(strArr[0]);

        PriorityQueue<Long> priQue = new PriorityQueue<Long>();
        int start ; // 반복문 시작할 인덱스 번호
        int linecnt = 0;
        while(priQue.size()<n) {
            // 첫 줄인 경우 
            if(priQue.isEmpty()&& linecnt == 0) {
                start = 1;
            }
            // 값이 있다는 것은 무조건 첫 줄이 아니므로, 반복문 시작 인덱스 0으로 지정
            else {
                start = 0;
                strArr = br.readLine().split(" ");
            }

            for(int i = start; i<strArr.length; i++) {
                if(strArr[i].equals("")) {
                    continue;
                }
                // 우선순위que에 reverse된 숫자 추가
                String temp = strArr[i];
                priQue.add(returnLong(temp));
            }// for fin
            linecnt++;
        } // while fin

        // priQue 안의 값들 sb에 추가
        while(!priQue.isEmpty()) {
            sb.append(priQue.poll()).append("\n");
        }
//         이렇게 poll 안하고 그냥 추가할 때는 똑바로 정렬되지 않음
//        for (int i : priQue) {
//            sb.append(i).append("\n");
//        }
        br.close();
        System.out.println(sb.toString().trim());
    }
    // String으로 된 숫자인자 받아서, 역순으로 변경
    public static long returnLong(String strInt) {
        // string은 reverse()가 없기에, StringBuilder를 활용함
        StringBuilder tempSb = new StringBuilder();
        String reverseStr = tempSb.append(strInt).reverse().toString();
        long reverseInt = Long.parseLong(reverseStr);
        return reverseInt;
    }
}

문제 풀이 과정은 다음과 같다. 이 문제 풀이에 대해 처음 고민했던 부분은 예제 1에서 첫 문장 10 5 2233 이부분이다. 기존 문제들은 한 문장에 n과 이후 값들이 주어지면 매너있게.. 10 5 3 6 ... 이런느낌으로 구분지어줬는데 이 문제는 한 문장에 개판으로 값을 주는 걸 보고 굉장히 싸가지없다고 생각했다.

암튼 그래서 첫 문장을 배열화 해서 n을 구분 짓고, 이후의 값들을 반복문을 통해 받는 느낌으로 구현했다. strArr를 static으로 선언하였기에, 계속 반복해서 체크하기 쉽고 문장마다 br.readLine().split(" ") 통해 오류 없이 구분되므로 값을 오류 없이 입력받을 수 있었다.

다음으로 숫자지만 현재는 문자열로 값을 받고 있고, 그러면 바로 reverse를 활용하면 역정렬이 될 것이라고 생각했다.

하지만, String에는 reverse()가 없고, StringBuilder에만 존재하기에 이를 활용하기 위해 returnLong 메소드를 만들어서 코드를 깔끔하게 만들어주었다. 문자를 받으면, 이를 StringBuilder에 추가하고, revese해준다음 Long타입으로 변경해주는 구문이다. ( 입력 받는 값의 최대가 10^12 이므로 Long 타입이다.)

마지막으로 반복하여 reverse 된 숫자 값들을 priQue (우선순위 큐)에 저장해주고, 이 문제에선 인자를 하나만 받으므로 값을 내보낼 때 자동으로 오름차순 정렬을 해준다. 따라서, 반복해서 poll 함과 동시에 sb에 저장해서 한 번에 출력하여 해결하였다.

? 하지만 에러가 발생했다. 심지어 바로 오류난 것이 아니라 진행 되다가 오류난 것을 보고 뭔가 놓친게 있다고 생각했다. 그 결과

이런식으로 넣을 땐 정상적으로 잘 들어가지만, 공백을 입력받을 때

NullException 이 발생되는 것을 확인할 수 있다. 이에 따라서 null 값을 받은 경우에 따른 예외처리를 해주어야한다.

for(int i = start; i<strArr.length; i++) {
                if(strArr[i].equals("")) {
                    continue;
                }
                // 우선순위que에 reverse된 숫자 추가
                String temp = strArr[i];
                priQue.add(returnLong(temp));
            }// for fin

값을 반복해서 받는 부분에 만약 공백이면, continue 해주는 구문을 추가하여 해당 오류를 해결하였다. 그리고, 첫 문장인지 아닌지도 체크해줘야 반복해서 값을 입력받을 때 1번인덱스부터 시작할지, 0번 인덱스 부터 시작할지를 확실하게 구분지으므로, 해당 변수도 추가해주었다.

package test12;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Ox12_Q2_2 {
    static String [] strArr;
    // 백준 5648 S5 역원소 정렬
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 첫 줄 먼저 체크
        strArr = br.readLine().split(" ");
        int n = Integer.parseInt(strArr[0]);

        PriorityQueue<Long> priQue = new PriorityQueue<Long>();
        int start ; // 반복문 시작할 인덱스 번호
        int linecnt = 0;
        while(priQue.size()<n) {
            // 첫 줄인 경우 
            if(priQue.isEmpty()&& linecnt == 0) {
                start = 1;
            }
            // 값이 있다는 것은 무조건 첫 줄이 아니므로, 반복문 시작 인덱스 0으로 지정
            else {
                start = 0;
                strArr = br.readLine().split(" ");
            }

            for(int i = start; i<strArr.length; i++) {
                if(strArr[i].equals("")) {
                    continue;
                }
                // 우선순위que에 reverse된 숫자 추가
                String temp = strArr[i];
                priQue.add(returnLong(temp));
            }// for fin
            linecnt++;
        } // while fin

        // priQue 안의 값들 sb에 추가
        while(!priQue.isEmpty()) {
            sb.append(priQue.poll()).append("\n");
        }
//         이렇게 poll 안하고 그냥 추가할 때는 똑바로 정렬되지 않음
//        for (int i : priQue) {
//            sb.append(i).append("\n");
//        }
        br.close();
        System.out.println(sb.toString().trim());
    }
    // String으로 된 숫자인자 받아서, 역순으로 변경
    public static long returnLong(String strInt) {
        // string은 reverse()가 없기에, StringBuilder를 활용함
        StringBuilder tempSb = new StringBuilder();
        String reverseStr = tempSb.append(strInt).reverse().toString();
        long reverseInt = Long.parseLong(reverseStr);
        return reverseInt;
    }
}

굿

이번주는 저번주에 비하면 좀 수월하게 해결한 것 같다.. 난이도도 실버라 많이 높진 않았고, 익숙한 개념인 정렬이라서 그랬던 것 같다. 우선, 데이터를 비교할 n을 받고, 이후 n 번의 데이터를 다 받은 후 정렬하면 되는 문제이다.

package test12;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox12_Q1_1 {
    // 백준 11650 S5 좌표 정렬하기
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        // 우선순위 큐 선언
        PriorityQueue<Dot> dotPrQ= new PriorityQueue<>(1, new dotComparator());
        for(int i = 0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int dot1 = Integer.parseInt(st.nextToken());
            int dot2 = Integer.parseInt(st.nextToken());
            dotPrQ.offer(new Dot(dot1,dot2));
        }
        br.close();

        while(!dotPrQ.isEmpty()) {
            Dot d = dotPrQ.poll();
            sb.append(d.dot1).append(" ").append(d.dot2).append("\n");
        }
        System.out.println(sb.toString());

    }

}

class Dot{
    int dot1;
    int dot2;
    public Dot(int dot1, int dot2) {
        this.dot1 = dot1;
        this.dot2 = dot2;
    }
}

//클래스 객체의 우선순위를 위한 클래스
class dotComparator implements Comparator<Dot>{
    @Override
    public int compare(Dot d1, Dot d2) {
        if(d1.dot1 == d2.dot1) {
            return d1.dot2 - d2.dot2;
        }else {
            return d1.dot1 - d2.dot1;
        }
    }
}

우선 이 과정에서 우선순위 큐를 활용하고 싶었는데, 아직 미숙하여 공부할 겸 다른 분들의 코드를 인용하여 사용하였다.

먼저 n을 받은 후, n번 반복하여 데이터 dot1, dot2를 반복하여 dotPrQ (우선순위 큐) 에 저장한다.

우선순위 큐 같은 경우 데이터를 입력하거나 출력할 때 힙 영역에서 정렬되고, 정렬하기 위한 방식을 Comparator를 상속받아 설정할 수 있다.

먼저, dot1과 dot2를 한 번에 비교해야하므로 두 값을 객체화 해서 Dot로 묶어주었고, 이 값을 비교해주는 메소드를 생성해주었다. 여기서 우리가 원하는 정렬 방식인, dot1의 값이 서로 같으면 dot2를 기준으로 작은 값이 나오고, 만약 다르면 더 작은 값이 우선해서 나오도록 정렬하는 구문을 작성해주었다.

이후 아까 저장했던 dotPrQ에서 값을 하나씩 빼면서 원하는 값들을 sb에 저장해주고, 이를 한 번에 출력해주면서 해결하였다.

굿

우선 지난주 ~ 주말엔 좀 일정이 많았다. 그래서 그런지 컨디션 회복이 안됐나 자꾸 상태가 안좋다 어제 아침엔 눈 염증 증세부터 시작해서.. 복통, 허리 통증 등 여기저기 상태가 안좋다 애매하네

• 어깨 아파서 조퇴했는데 다행히도 그냥 염증이란다! 라운드 숄더 그런 문제라는데 ..음.. 해결책이 운동을 해야된단다 음..ㅇㅋ; 그냥 참아야겠다

우선 이번에 들은 강의는 재귀함수랑 백트래킹이다. 사실 재귀함수는 기존에 알고 있던 개념이여서 수월하게 할 줄 알았으나 전혀 아니였다.

먼저 재귀함수란, 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘을 의미한다. 말 그대로 계속 호출하다가 특정 조건이 되면 return하여 값을 구한다. 따라서, 인자로 어떤 것을 받고, 어디 까지 계산한 후 자기 자신에게 넘겨줄 지 명확하게 정해야한다.

모든 재귀함수는 반복문만으로 구현했을 때에 비해 코드가 간결하지만 메모리 / 시간에서는 손해를 본다. 재귀함수가 자기 자신을 부를 땐 스택영역에 계속 누적하여 값을 체크한다.

다음으로 백트래킹은 이번에 처음 접했다. dfs랑 비슷한 느낌이였는데, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 아무래도 아직 이쪽 개념은 많이 부족하기에 문제도 많이 풀고 개념도 더 다듬어야겠다고 느꼈다.

다음으로 이번 주제로 풀었던 문제들을 소개하면서 마무리 하겠습니다!

1. 백준 자바 1074 Z

2. 백준 자바 17478 재귀함수가 뭔가요?

3. 백준 자바 9663 N-Queen

4. 백준 자바 15649 N과 M(1)

5. 백준 자바 15650 N과 M(2)

6. 백준 자바 2447 별 찍기 - 10

다음은 마지막으로 별찍기 문제다.. 개인적으로 가장 머리가 아팠다.

1/3 씩 반복해서 재귀문도 돌려야하고, 값을 찍어내기도 해야하는데, 중간중간 비워두기까지 해야한다..

package test11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ox11_Q5_1 {
    static int n;
    static char[][] board;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        br.close();

        // 보드판 세팅, 모든 공간을 공백으로 먼저 세팅
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = ' ';
            }
        }
        // 메서드 호출
        starFunc(0, 0, n);

        // 계산 된 보드판 출력세팅 , 행마다 "\n" 추가
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(board[i][j]);
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }

    public static void starFunc(int x, int y, int n) {
        if (n == 1) {
            board[x][y] = '*';
            return; // 재귀함수로 return
        }

        int newSize = n / 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) {
                    continue; // 중앙은 비워둔다.
                }
                // 재귀함수 호출, 지금 검사한 메소드 x * 3, y *3 좌표
                starFunc(x + i * newSize, y + j * newSize, newSize);
            }
        }
    }
}

우선 starFunc함수는 x(헹),y(열),n 을 인자로 받는다. Z문제 는 1/2씩 반복했다면, 이 문제는 1/3씩 반복한다. 점차 반복해서 제일 작은 블럭 (0,0,3)을 만들어 주고, 해당 구문이 반복해서 전체를 채워지게끔 하는 구조이다. 그 과정에서 가운데 부분은 공백이 와야하므로 i와 j 가 같은경우엔 contine 해준다.

참.. 백트래팅은 뭔가 머리론 얼추 이해하는데 손이 안따라주는 것 같다 어렵지만 꾸준히 해야겠다! 파이팅!

우선 이 문제는 제목에서도 알 수 있다싶이 이전 문제와 흡사하다. 다만 수열을 배열에 담을 때, 오름차순으로 점차 증가하게끔 넣어야 하기에 해당 제어문을 고려해주었다.

package test11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Ox11_Q4_2 {
    static StringBuilder sb;
    static int n,m;
    static int cnt;
    static boolean [] issued ;
    static int [ ] put;

    // 백준 15650 S3 ( N과 M(2) )
    public static void main(String args []) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        issued = new boolean[n+1];
        put = new int[m+1];
        br.close();

        checkN(0,1);
        System.out.println(sb.toString());

    }

    public static void checkN(int cur, int start) {
        // 현재 값(cur)과 원하는 개수(m)가 같으면 출력
        if (cur == m) {
            for (int i = 0; i < m; i++) {
                sb.append(put[i] + " ");
            }
            sb.append("\n");
            return;
        } // if fin

        // i가 start부터 시작하므로, 이후에 추가될 값은 오름차순임.
        for (int i = start; i <= n; i++) {
            if (!issued[i]) {
                put[cur] = i;
                issued[i] = true;
                // 재귀해서 체크
                checkN(cur + 1, i+1);
                // 초기화
                issued[i] = false;
            }// if fin
        } // for fin
    }// checkN fin

}

전체적으로 checkN 함수는 이전과 흡사하지만, 이번엔 증가하는 값들을 체크하기 위해 start라는 인자를 추가적으로 받아주었다. 그리고, 이전엔 반복하여 재귀문을 시행할 때, i = 0부터 시작했으나, 이번엔 i = start 부터 시작하였고, 바로 issued로 값의 여부를 체크해주므로 원하던 증가하는 값들만 구할 수 있었다. 마찬가지로 한 사이클을 돌리고 나선 isuued[i]를 초기화 시켜주면서 정상적으로 해결하였다.

굿

이 문제는 원래 풀어야 되는 문제는 아니였지만, 15650 N과 M(2)가 있기에 연습겸 풀었다.

package test11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Ox11_Q4_1 {
    static StringBuilder sb;
    static int n,m;
    static int cnt;
    static boolean [] issued ;
    static int [ ] put;

    // 백준 15649 S3 ( N과 M(1) )
    public static void main(String args []) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        issued = new boolean[n+1];
        put = new int[m+1];
        br.close();

        checkN(0);
        System.out.println(sb.toString());    

    }

    public static void checkN(int cur) {
        if (cur == m) {
            for (int i = 0; i < m; i++) {
                sb.append(put[i] + " ");
            }
            sb.append("\n");
            return;
        } // if fin

        for (int i = 1; i <= n; i++) {
            if (!issued[i]) {
                put[cur] = i;
                issued[i] = true;
                checkN(cur + 1);
                issued[i] = false;
            }// if fin
        } // for fin
    }// checkN fin

}

N-Queen 문제와 같이 강의에 있었기에 참고하면서 문제를 해결하였다. 함수 checkN 는 m개의 변수를 받아 수열화 할 것이고, cur번째 값들을 수열을 저장하는 배열에 순차적으로 더한다. 그 과정에서 m과 같아지면 완성된 수열을 sb에 차근차근 누적하는 구문이다. 이 과정에서 N-Queen과 같이 재귀하는 구문이 실행되고나면 차근차근 초기화 시켜주는게 포인트이다.

풀면서 느낀점이 백트래킹은 재귀 +Dfs 느낌인데, 내가 제대로 이해한게 맞는지 모르겠다.

굿

..백트래킹이라는 개념을 이번 강의를 통해 처음 접했는데, 나랑 안맞는 것 같다 ㅎ..

우선 이 문제는 이번 주의 강의였던 [바킹독의 실전 알고리즘] 0x0C강 - 백트래킹 에 있던 예제 중 하나였다. 물론 강의는 c++로 되어있으나, 우리는 자바로 문제를 풀기에 강의 내용을 이해한 후 자바로 재해석하여 문제를 해결하였다.

package test11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ox11_Q3_1 {
    static int cnt = 0; // 경우의 수
    static int n; 
    static boolean issued1 [] = new boolean [30]; // 세로 열 체크
    static boolean issued2 [] = new boolean [30]; // 오른쪽 위 대각선 체크
    static boolean issued3 [] = new boolean [30]; // 오른쪽 아래 대각선 체크
    // 백준 9663 G4 N-Queen
    public static void main(String args []) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        checkFunc(0);
        System.out.println(cnt);

    }

    public static void checkFunc(int cur) {
        // 체스 놓은 말 개수가 n이랑 같으면 return 
        if (cur == n) {
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            // Q가 있는 열, 오른쪽 대각선, 왼쪽 대각선에 값이 있는 경우 continue;
            if (issued1[i] || issued2[i + cur] || issued3[cur - i + n - 1]) {
                continue;
            }
            // 세 곳 값 세팅
            issued1[i] = true;
            issued2[i + cur] = true;
            issued3[cur - i + n - 1] = true;
            // 재귀
            checkFunc(cur + 1);
            // 다 놓아본 후 새로 복원
            issued1[i] = false;
            issued2[i + cur] = false;
            issued3[cur - i + n - 1] = false;
        } // for fin

    }
}

처음에 예제를 볼때, 왜 1차월 배열로 값을 체크하지? 하는 생각이 들었다. 제대로 이해가 되지 않았었으나, 구글링을 통해 해당 개념을 어느정도 이해할 수 있었다. 문제 특성상 체스를 한 개 두면 해당 열과 행 모두 둘 수 없기에 위에서 보면 하나의 열에 하나씩 값이 들어가 있는 느낌이다. 즉 배열 한 개가 있을 때 해당 인덱스가 열이고, 그 안에 있는 각각의 값이 행을 의미한다고 해석하면 된다.

다음으로, 함수 checkFunc를 해석해 보겠다. 체스를 말을 놓은 개수 cnt를 인자로 받고있다. 만약 (0,0) 에 퀸을 둔다고 가정하면 이에 해당 하는 x열, x행, 대각선 방향은 모두 값을 놓을 수 없으므로 이를 손쉽게 체크하기 위해 배열 세개를 두어 간편하게 검증하였다. 이후 해당 x열 (인덱스)를 의미하는 isuued1 해당 x열의 오른쪽 대각선 증가 를 의미하는 issued2 해당 x열의 왼쪽 대각선 감소를 의미하는 isuued3 에 각각 true값을 준 후 반복하여 해당 경우의 수를 구해고, 만약 재귀문이 종료되면 해당 구문들을 다시 false로 초기화해준다.

문제 자체는 어려웠으나, 강의 덕분에 차근차근 따라하여 수월하게 해결하긴했다. 하지만, 앞으론 혼자서도 해결할 수 있어야하므로 이에 방심하지 않고 꾸준히 공부해야겠다.

이 문제는 처음엔 약간 뭔소린가 싶었다. n번 반복하는데 확실하게 반복하는거도 아니고 뭐지.. 싶었는데 마우스로 드래그하면서 블럭을 나누다보니 반복되는 부분이 눈에보였다.

package test11;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Ox11_Q2_1 {
    static StringBuilder sb;
    static int count = 0;
    static String space = "";
    // 백준 17478 S5 재귀함수가_뭔가요?
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        br.close();
        sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
        // 증가하는 부분 재귀함수 실행
        returnPlus(n);

        // 중간 멘트 두 개 추가
        String sentence5 = '"' + "재귀함수가 뭔가요?" + '"' + "\n";
        String sentence6 = '"' +"재귀함수는 자기 자신을 호출하는 함수라네"+ '"' + "\n";
        sb.append(space + sentence5);
        sb.append(space + sentence6);

        String sentence7 = "라고 답변하였지.\n";
        for(int i =n; i>-1; i--) {
            sb.append(space + sentence7);

            // 출력할 때마다 언더바('_') 4개씩 줄어들게끔
            if(space.length()>3) {
                space = space.substring(0, space.length()-4);
            }
        }    
        System.out.println(sb);
    }
    public static void returnPlus(int n) {
        while(true) {
            if(count==n) {
                break;
            }
            // 증가하는 문장
            String sentence1 = '"' + "재귀함수가 뭔가요?" + '"' + "\n";
            String sentence2 = '"' +"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
            String sentence3 = "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
            String sentence4 = "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." + '"' + "\n";

            sb.append(space + sentence1);
            sb.append(space + sentence2);
            sb.append(space + sentence3);
            sb.append(space + sentence4);

            // 언더바 4개
            space += "____";
            count++;

            returnPlus(n);
        } // while fin

    }

}

우선 이 문제는 크게 세 가지 구간으로 나뉜다고 해석했다.

1. 질문 + 대답으로 이루어져 n번 반복하면서 증가하는 구간
2. 질문 + 대답으로 이루어져 1번만 출력하는 구간
3. 대답으로 이루어져 n+1번 반복하면서 감소하는 구간

이렇게 세 구간으로 인지했다.

그 과정에서 증가, 감소하면서 문장의 앞부분에 언더바 '_' 가 추가 및 제거 되므로 해당부분을 고려하면 쉽게 해결할 수 있을 것이라고 생각했다.

returnPlus()함수는 n번 반복하므로 반복할 횟수 n을 인자로 받는다. 이후 최종 출력할 sb에 반복해서 추가해주는데, 먼저 문장을 추가한 후 언더바들을 저장할 space에 4칸을 추가해준다.

이후 main부분에서 한 번만 추가되는 문장들과 n+1번 반복하지만 space가 점차 감소하여 추가되는 문장들을 고려해주면서 해당 문제를 마무리하였다.

굿

백준 자바 9466

이곳에서 확인 가능합니다.

우선 재귀함수 개념은 알고 있었으나, 강의를 듣고 제대로 풀려고 하니 대충 느낌은 이해 됐는데 뭔가 고안하는게 헷갈렸다.

우선

0 / 1 2 / 3

이게 반복 되는 구조이고, 원하는 위치가 정 사각형에서 몇 사분면에 있는지 반복하면서 체크하여 문제를 해결하였다.

package test11;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Ox11_Q1_1 {
    static int cnt = 0;
    // 백준 1074 S1 Z
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // n : 2의 n제곱만큼 보트 판크기
        // r : r행 (가로)
        // c : c행 (세료)
        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 기본적 보드판 생성
        int boardLen = (int) Math.pow(2, n);
        returnFunc(r,c,boardLen);
        System.out.println(cnt);

    }


    public static void returnFunc(int r,int c, int boardLen) {


        // boardLen ==1 -> 재귀 종료
        if(boardLen ==1 ) {
            return;
        }

        int temp = boardLen/2;
        //해당 좌표가 왼쪽 위
        if(r<temp && c<temp) {
            returnFunc(r,c,temp);
        }

        // 해당 좌표가 오른쪽 위
        else if(r<temp && temp<=c) {
            cnt+= (int)Math.pow(temp,2);
            returnFunc(r,c-temp,temp);
        }

        // 해당 좌표가 왼쪽 아래
        else if(r>=temp && c < temp) {
            cnt += (int)Math.pow(temp,2) * 2 ;
            returnFunc(r-temp,c,temp);
        }

        // 해당 좌표가 오른쪽 아래
        else {
            cnt += (int)Math.pow(temp,2) * 3;
            returnFunc(r-temp,c-temp,temp);

        }
    }

}

먼저 함수 returnFunc 는 r (행), c (열), boardLen (n의 길이)를 인자로 받는다.

우선, 전체 길이를 반복해서 1/4 해야하고, 전체 길이가 6이라 할때, 전체 길이의 반을 temp로 가정하겠다/ 왼쪽 위는 03 / 03이므로 이는 temp로에 해당된다.

두 번째로, 오른쪽 위는 46 / 03 이므로, 이는 행은 그대로고 열만 반부터 진행되니깐 returnFunc(r,c-temp,temp) 를 return해준다.

세 번째로, 왼쪽 아래는 03 / 46 이므로, 이는 행은 반부터 진행되고, 열은 그대로니깐 return(r-temp,c,temp) 를 return 해준다.

마지막으로, 오른쪽 아래는 46 / 46 이므로, 이는 행도 반부터 진행하고, 열도 반부터 진행되므로 returnFunc(r-temp, c-temp, temp)를 return 해준다.

이 과정에서 전체 숫자를 의미하는 cnt는 제 1사분면일 땐 따로 더해주는게 없지만, 2, 3, 4일땐 temp의 제곱, 2* temp의 제곱, 3* temp의 제곱을 각각 더해주면서 값을 구해주었다.

굿