Linked List

Linked List란?

• 연속적인 메모리 공간이 아닌 노드(Node)들이 서로 연결된 데이터 구조이다.

Array와의 차이점

• Array는 연속된 메모리 공간에 데이터를 저장하지만, Linked List는 연결된 노드에 데이터를 저장한다.

Linked List의 장단점

• 장점: 데이터를 삽입, 삭제하는 연산이 빠르다. 메모리 공간을 동적으로 할당할 수 있다.
• 단점: 검색 연산이 느리다. 메모리 접근이 순차적이지 않아 캐시 효율이 떨어진다.

Linked List 기본 연산

삽입(Insertion)

• 맨 앞, 맨 뒤, 중간 위치에 삽입하는 방법이 있다.

삭제(Deletion)

• 맨 앞, 맨 뒤, 중간 위치의 노드를 삭제하는 방법이 있다.

검색(Search)

• 모든 노드를 하나씩 순회하며 찾는다.

수정(Modification)

• 특정 노드의 데이터를 변경하는 방법이 있다.

Linked List의 시간 복잡도

최선, 최악, 평균 시간 복잡도

• 삽입, 삭제, 검색, 수정 연산의 경우 최선, 최악, 평균 시간 복잡도는 각각 다르다. 각 경우의 시간 복잡도를 이해해야 효율적인 알고리즘을 작성할 수 있다.

삽입(Insertion)

• 맨 앞에 삽입하는 경우: O(1)
• 맨 뒤에 삽입하는 경우: O(n)
• 중간에 삽입하는 경우: O(n)

삭제(Deletion)

• 맨 앞에서 삭제하는 경우: O(1)
• 맨 뒤에서 삭제하는 경우: O(n)
• 중간에서 삭제하는 경우: O(n)

검색(Search)

• 순차적으로 검색하는 경우: O(n)

수정(Modification)

• 특정 노드의 값을 수정하는 경우: O(1)

위에서 n은 Linked List의 노드 개수를 나타낸다.
즉, Linked List는 삽입, 삭제 연산이 빠르지만 검색 연산이 느리다는 특징을 가지고 있다.

예제문제

선우의 셋리스트(백준 25962번)

문제 :
선우는 아주대학교의 $3$년 만의 대동제를 맞아 공연으로 노래를 열창해 아주대학교의 여심을 홀리고 싶다. 선우는 총 $N$($1\leq N \leq 10^{18}$)분의 공연을 기획하고 있는데, 어떤 노래를 어느 순서로 몇 번이나 부를지 정하지 못하고 있다.

예를 들어, 다음과 같은 후보곡들이 있다고 하자.

<아주바캉스>, 아주 강 같은 평화 - $3$분
<졸업할 수 있을까>, 컴공소년 - $2$분
<벌써 사년>, 브라운 관즈 - $1$분
<응급실>, 낫 이지 - $5$분
<이미 아픈 성적>, 요다 - $4$분
선우가 이 노래들로 $10$분의 공연을 구성한다면 [3번, 1번, 3번, 4번]와 같은 식으로 공연을 구성할 수 있다. 여기서 알 수 있듯이, 선우는 중간에 절대 쉬지 않는다! 또한 같은 노래를 여러 번 부를 수도, 어떤 후보곡은 쓰이지 않을 수도 있다. 이렇게 공연을 하는 데에 부르는 노래의 순서를 셋리스트라고 한다.

선우가 부를 수 있는 후보곡의 수와, 각 노래의 재생 시간이 주어질 때, 선우를 도와 정확히 $N$분의 공연을 할 수 있는 셋리스트의 경우의 수를 알려주자.

입력
첫 번째 줄에 선우가 공연을 기획한 시간 $N$($1 ≤ N ≤ 10^{18}$)과 선우가 부를 수 있는 후보곡의 수 $M$($2 \leq M \leq 100\,000$)이 공백으로 구분되어 주어진다.

두 번째 줄부터 ($M+1$)번째 줄까지 각 줄에는 노래의 재생시간 $t_i$($1 \leq i \leq M$, $ 1 \leq t_{i} \leq 5$)가 주어진다.

출력
첫 번째 줄에 선우가 공연을 위해 준비해야 하는 가능한 셋리스트의 경우의 수를 $1\,000\,000\,007$($=10^{9}+7$)로 나눈 나머지를 출력하시오.

셋리스트를 구성할 수 없다면 정답은 $0$이다.

예제 입력 1
25 5
5
5
5
5
5
예제 출력 1
3125
모든 노래의 길이가 같으므로 경우의 수는 $5^5$와 같다.

예제 입력 2
10 6
2
2
2
3
4
4
예제 출력 2
555

나의 생각

• 알고리즘 지식뿐 아니라, 경험이 부족하여 다른 사람의 설명을 찾아다니며 읽어 보았다. 내가 참고한 블로그이다. https://memoacmicpc.tistory.com/entry/%EB%B0%B1%EC%A4%80-25962%EB%B2%88-%EC%84%A0%EC%9A%B0%EC%9D%98-%EC%85%8B%EB%A6%AC%EC%8A%A4%ED%8A%B8

• 노래의 기획시간이 5분 이하이면, DP알고리즘을 통해 일차원배열로 문제를 해결한다.

• 그외 6분 이상이면, 행렬의거듭제곱을 이용하여 문제를 해결한다.

• 방법은 위 두개가 전부이며, 왜 행렬거듭제곱근을 사용하는지 또한, 링크한 블로그에 자세히 설명되어 있다.

• 처음 문제를 봤을 때, 스스로 방법을 어떻게 떠올려야할지 감이 안잡힌다.

• 나는 코딩테스트를 준비하는 입장으로서, 비슷한 문제들을 많이 풀어보면서, 알맞은 알고리즘과 방법을 떠올리는것이 당연하고 익숙하도록 노력할 필요가있다.

• 위 블로그에서는 언어 C11을 이용해 문제를 풀었다.

• 나는 자바에 좀더 익숙해질 필요가 있어 자바로 문제를 다시 풀어보았다.

구현

import java.io.*;
import java.util.*;

public class Main {
    static int mod = 1_000_000_007;

    // 5x5 행렬 클래스 정의
    static class Matrix {
        long[][] mat;
        Matrix() {
            mat = new long[5][5];
        }
    }

    // 두 행렬을 곱하는 함수
    static Matrix multiply(Matrix a, Matrix b) {
        Matrix ret = new Matrix();
        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++) {
                for(int k=0;k<5;k++) {
                    ret.mat[i][j] = (ret.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
                }
            }
        }
        return ret;
    }

    // 행렬 m을 n번 거듭제곱하는 함수
    static Matrix power(Matrix m, long n) {
        Matrix ret = new Matrix();
        for(int i=0;i<5;i++) ret.mat[i][i] = 1;

        while(n > 0) {
            if(n % 2 == 1) ret = multiply(ret, m);
            m = multiply(m, m);
            n /= 2;
        }
        return ret;
    }

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

        // 입력값 처리
        long n = Long.parseLong(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 각 곡의 개수 카운트
        int[] songs = new int[6];
        for(int i=0;i<m;i++) {
            int t = Integer.parseInt(br.readLine());
            songs[t]++;
        }

        // 간단한 경우(5 이하) 처리 dp알고리즘으로 해결한다.
        long[] simple = new long[6];
        for(int i=1;i<=5;i++) {
            simple[i] = songs[i] % mod;
            for(int j=1;j<i;j++) {
                simple[i] = (simple[i] + (songs[j] * simple[i-j]) % mod) % mod;
            }
        }
        if(n <= 5) {
            bw.write(Long.toString(simple[(int)n]));
            bw.write("\n");
            bw.flush();
            return;
        }

        // 행렬 계산을 위한 기본 행렬 구성 행렬의거듭제곱근 알고리즘으로 문제를 해결한다.
        Matrix base = new Matrix();
        for(int i=0;i<5;i++) {
            base.mat[0][i] = songs[i+1];
        }
        for(int i=1;i<5;i++) {
            base.mat[i][i-1] = 1;
        }

        // 행렬 거듭제곱을 이용한 계산
        base = power(base, n-5);
        long ans = 0;
        for(int i=0;i<5;i++) {
            ans = (ans + simple[5-i] * base.mat[0][i]) % mod;
        }
        bw.write(Long.toString(ans));
        bw.flush();
        bw.close();
    }
}

마무리

• 스스로 자세히 설명할 수 있을 만큼 공부할 필요가 있다.
• DP알고리즘에 대해 공부가 필요하다.
• 디버깅을하여 코드가 어떤식으로 작동해서 결과값을 어디서 찾아오는지 확인했다.
• 아이디어가 좋다.
• 밑에는 내가 처음 재귀함수로 작성한, 시간초과되는 완전탐색 알고리즘이다.

import java.util.*;

public class Main {
    static long result = 0;     // 결과값을 저장할 전역변수
    static final int MOD = 1000000007;    // 나머지값을 계산할 상수
    static long N;     // 노래의 길이

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextLong();  // 첫번째 입력값으로 노래의 길이를 받음
        int M = sc.nextInt();   // 두번째 입력값으로 노래의 개수를 받음
        int[] songs = new int[M];   // 노래 길이를 저장할 배열 생성
        for (int i = 0; i < M; i++) {
            songs[i] = sc.nextInt();    // 노래 길이를 입력받아 배열에 저장
        }

        // 1 ~ N개의 노래를 뽑아 만들 수 있는 모든 경우의 수를 구함
        for (int i = 1; i <= N; i++) {
            solution(songs, new int[i], i, 0, 0);
        }

        System.out.println(result); // 결과값 출력
    }

    // 조합을 이용하여 노래를 선택하는 함수
    public static void solution(int[] songs, int[] selected, int r, int index, int sum) {
        if (index == r) {   // r개의 노래를 모두 선택한 경우
            if (sum == N) {     // 노래의 길이의 합이 N과 같은 경우
                result = (result + 1) % MOD;    // 결과값을 1 증가시킴
            }
            return;
        }
        for (int i = 0; i < songs.length; i++) {
            selected[index] = i;
            solution(songs, selected, r, index+1, sum+songs[i]);
            selected[index] = 0;
        }
    }
}