[항해99 취업 리부트 코스 학습일지] 2024.04.15.(월)

내일이 시험이기도 하고, 이번주 배운 내용 정리하고, 구현할 수 있는 구조(템플릿)이 있는 알고리즘은 간단히 복습을 해보려고 한다.

[01. 완전탐색]

- Brute Force 알고리즘이라고 부르며, 모든 가능한 조합, 순열을 만들어 답을 찾는 알고리즘

- 순열과 조합

- 시간복잡도가 매우 높지만, 특정 문제에 대해 최적의 해를 보장한다

 

예시 : 주어진 배열에서 조합만들기

package src.com.company.week3.day5;

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

public class BruteForceCombinationExample {

    // 모든 조합 찾기
    public static List<List<Integer>> generateCombinations(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 조합 생성 함수
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    // 재귀, 조합찾기
    private static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
        // 현재 조합을 결과에 추가
        result.add(new ArrayList<>(current));

        // 각 요소를 선택하여 조합 생성
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            // 다음 요소 선택(feat 재귀)
            backtrack(nums, i + 1, current, result);
            // 선택한 요소 제거 (백트래킹)
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3}; 
        List<List<Integer>> combinations = generateCombinations(nums);

        // 결과 출력
        System.out.println("배열의 조합:");
        for (List<Integer> combination : combinations) {
            System.out.print(combination + " ");
            /** 출력
              * 배열의 조합:
              * [] [1] [1, 2] [1, 2, 3] [1, 3] [2] [2, 3] [3] 
            */
        }
    }
}

 

[02. 그리디]

- greedy 알고리즘은 지금 상황에서 최선의 해 구하기! 

- 거스름돈, MST(minimum Spanning Tree, 최소 신장 트리, 가중치의 합이 최소) 알고리즘 나오면 그리디를 떠올려라

- 주어진 문제에 대해 빠르게 해를 구할 수 있으나 최적해를 보장하지 않는다

예시 : 짐싸는데 최대한 물건 많이 넣기

package src.com.company.week3.day5;

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

public class GreedyBackpackExample {
    static ArrayList<String> itemNames;

    // 물건을 표현하는 클래스
    static class Item {
        int weight;
        int value;
        double valuePerWeight;
        String name;

        public Item(int weight, int value, String name) {
            this.weight = weight;
            this.value = value;
            this.valuePerWeight = (double) value / weight;
            this.name = name;
        }
    }

    // 그리디 알고리즘을 사용하여 배낭에 담을 수 있는 최대 가치를 계산하는 함수
    public static double greedyKnapsack(int capacity, Item[] items) {
        // 가치가 높은 순으로 물건 정렬
        Arrays.sort(items, Comparator.comparingDouble(o -> -o.valuePerWeight));

        double totalValue = 0;
        int currentWeight = 0;
        itemNames = new ArrayList<>();
        // 물건을 담을 수 있는 만큼 최대한 담기
        for (Item item : items) {
            if (currentWeight + item.weight <= capacity) {
                totalValue += item.value;
                currentWeight += item.weight;
                itemNames.add(item.name);
            } else {
                int remainingWeight = capacity - currentWeight;
                totalValue += item.valuePerWeight * remainingWeight;
                itemNames.add(item.name);
                break;
            }
        }

        return totalValue;
    }

    public static void main(String[] args) {
        int capacity = 50; // 배낭의 용량
        Item[] items = {
                new Item(10, 60, "물"),
                new Item(20, 100, "핫팩"),
                new Item(30, 120, "신분증")
        }; // 예시 물건들 (무게, 가치)

        double maxValue = greedyKnapsack(capacity, items);
        System.out.println("배낭에 담을 수 있는 최대 가치: " + maxValue);
        for (String name : itemNames) {
            System.out.print("배낭에 담긴 물건들:" + name + " ");
        }
    }
}
/**
 * 출력
 * 배낭에 담을 수 있는 최대 가치: 240.0
 * 배낭에 담긴 물건들: 물 핫팩 신분증 
 * */

 

[03. 다익스트라]

- Dijkstra 알고리즘, 네비게이션 알고리즘이라고 한다

- 가중치가 있는 그래프에서 우선순위큐를 사용해 구현한다.

저번주에 정리한게 있어서 간단한 예시는 이걸로 첨부..

[항해99 취업 리부트 코스 학습일지] 2024.04.12.(금)

 

 

[04. 다이나믹 프로그래밍]

- 주어진 문제를 더 작은 부분으로 나누어 해결, 그 해결책을 "저장" 하여 중복계산한다

- top down방식(memoization) 과 bottom up 방식으로 구현이 가능하다

- 피보나치수열, 배낭시리즈, 가장 긴 부분수열의 합 등등

피보나치 수열 구하기

⭐️ 중요한 부분

1. 배열 초기화 : dp배열을 만들고, 인덱스 0과 1을 초기화(피보나치 수열의 기본값)

2. 반복문을 통한 계산 : 현재 인덱스 i의 값은 i - 1번째 값과  i - 2번째 값을 더한것과 같다

DP에서 가장 중요한 것이 중간 결과를 재활용하는것!! 이다

 

⭐️⭐️⭐️ 완전탐색적으로 생각하고, 규칙이 있으면 적용해서 풀 수 있도록 하자

package src.com.company.week3.day5;

public class FibonacciExample {

    // 다이나믹 프로그래밍을 사용하여 피보나치 수열을 구하는 함수
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10; // 피보나치 수열의 n번째 항을 구하기 위한 입력값
        int result = fibonacci(n);
        System.out.println("피보나치 수열의 " + n + "번째 항: " + result);
        /**
         * 출력 
         * 피보나치 수열의 10번째 항: 55
         * */
    }
}