알고리즘 테크닉 정리

2023년 12월 05일 TIL

알고리즘을 풀다 보면 공식으로 외워야 할 듯한 풀이법들이 보인다.
A <-> B 교체나, 정렬, 유클리드, 그리고...    

줄 서는 방법

문제

줄 서는 방법

 문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다.
n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다.
n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다.
예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

        [1, 2, 3]
        [1, 3, 2]
        [2, 1, 3]
        [2, 3, 1]
        [3, 1, 2]
        [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때,
사람을 나열 하는 방법을 사전 순으로 나열 했을 때,
k번째 방법을 return하는 solution 함수를 완성해주세요.

 제한사항

n은 20이하의 자연수 입니다.
k는 n! 이하의 자연수 입니다.

사전 순 정렬

모든 경우의 수를 사전 순으로 정렬 하려고 할 때 첫 시도는
Set<List<Interger>> 혹은, Map<Integer, List<Integer>> 를 이용하여
for 로 초기화한 후, sort 시키는 방법을 생각했다.

그러나 재귀로 Set을 초기화 시키려다 잠시 시선을 끄는 부분이 있었다.
일단 재귀는 효율이 최악인데다 문제 상에 k 값의 자료형이 long인게 눈에 들어왔는데,

    public int[] solution(int n, long k) {
        int[] answer = {};
        return answer;
    }

n <= 20 이라는 제한에 k값이 long 이라는 부분 눈이 가 20! 을 계산해보니...

결국

    public static int[] solution(int n, long k) {
        int[] answer = new int[n];
        ArrayList<Integer> numbers = new ArrayList<>();

        k--;
        long factorial = 1;

        for (int i = 1; i <= n; i++) {
            factorial *= i;
            numbers.add(i);
        }

        for (int i = 0; i < n; i++) {
            factorial /= (n - i);
            int index = (int) (k / factorial);
            answer[i] = numbers.remove(index);
            k %= factorial;
        }

        return answer;
    }

따로 공식에 가까운 테크닉이 있다는걸 확인하게 됐다.

factorial / (n - i) : 다음 숫자의 위치 탐색
k / factorial : 현재 위치에 올 숫자 탐색

이 방법으로 모든 경우의 수를 담아 sort 하지않아도,
List 안에 있는 숫자들의 사전순 정렬된 k 번째 배열을 가져올 수 있다.

피보나치 모듈화

    public int Fibonacci (int n) {
        if (n <= 1)
            return n;

        int tmp;
        int num1 = 1;
        int num2 = 1;

        for (int i = 2; i< n; i++) {
            tmp = num2;
            num2 = (num1 + num2) % 1234567;
            num1 = tmp;
        }
        return num1;
    }

피보나치 알고리즘에서 int 범위를 넘어가는 부분에서 나머지를 구할때,
공식 중간에 슬쩍 끼워넣으면서 나머지 부분을 미리 챙기는 식으로 계산 할 수 있다.

피보나치, 멀리 뛰기

둘은 사실상 같은 문제지만 재귀 대신 위와 같이 풀게 되면 효율적인 측면과
오버플로우를 방지할 수 있다.