99클럽 코테 스터디 15일차 TLI-(탐욕법)

문제 : https://www.acmicpc.net/problem/13417

🚨 오늘의 학습

⭐️탐욕법(Greedy)⭐️

탐욕법(Greedy)알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다.

ex) 거스름돈 구하기

🗝️ 현재의 순간에 최선을 선택을 하는 경우를 구현

🗝️ 문자 비교시 문자의 순서가 빠른 것을 왼쪽으로 정렬한다

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

public class Main {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int trierCnt = Integer.parseInt(st.nextToken());
        StringBuilder total = new StringBuilder();

        for(int i=0; i<trierCnt; i++){
            StringBuilder stb = new StringBuilder();

            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            char[] Narr = new char[N];

            st = new StringTokenizer(br.readLine());

            for(int j = 0;j<N;j++){
                Narr[j]= st.nextToken().toCharArray()[0];

            }


            stb.append(Narr[0]);

            for(int k=1;k<Narr.length;k++){
				// 첫번째 문자보다 작거나 같으면 왼쪽에 삽입
                if(Narr[k]<=stb.charAt(0)){
                    stb.insert(0,Narr[k]);
                }else{
                // 오른쪽 삽입
                    stb.append(Narr[k]);
                }
            }
            total.append(stb).append("/");
        }


        for(int i=0; i<trierCnt;i++){
            System.out.println(total.toString().split("/")[i]);

        }
    }

}

오늘의 회고

• 그리디 알고리즘의 개념을 처음 알게 되었다
• 현재의 순간에 최선의 선택을 하는 알고리즘이다
• 항상 최적의 해를 갖지 않는다
• 다익스트라 VS 그리디??
  • 다익스트라는 특정 최단 경로 문제를 해결하는 데 특화된 탐욕적 접근 방식으로도 볼 수 있다.