[Do it] 알코테 자바 3일차

04. 자료구조

04-1 배열과 리스트

1. 배열 (Array)

배열은 연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조이다.

특징

• 인덱스를 통해 O(1) 시간에 바로 접근 가능
• 메모리 공간이 연속적으로 배치됨
• 크기를 선언 시 지정해야 함
• 한 번 선언하면 크기 변경 불가
• 중간에 삽입/삭제 시 요소 이동 필요 → 비효율적

장점

• 빠른 접근 속도
• 구조가 단순함

단점

• 크기 변경 불가
• 삽입/삭제 비용 큼 (O(N))

---

2. 리스트 (Linked List)

리스트는 값과 다음 노드의 주소(포인터)를 함께 저장하는 노드(Node)들을 연결한 자료구조이다.

특징

• 노드 단위로 구성
• 메모리 공간이 연속적이지 않음
• 인덱스 개념이 없음
• Head부터 순차 접근 필요 → 접근 속도 O(N)
• 크기를 미리 지정할 필요 없음

장점

• 삽입/삭제가 빠름 (O(1), 위치만 알고 있다면)
• 동적 크기 조절 가능

단점

• 탐색 속도 느림
• 포인터 저장 공간 필요 → 구조 복잡

---

3. ArrayList vs LinkedList (Java 기준)

 

구분	ArrayList	LinkedList
내부 구조	배열	이중 연결 리스트
접근 속도	빠름 O(1)	느림 O(N)
삽입/삭제	느림	빠름
메모리	상대적으로 적음	포인터 저장 공간 필요

 

__[001] 숫자의 합 구하기

백준 온라인 져지 11720번 https://www.acmicpc.net/problem/11720

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();
        
        int sum = 0;

        for (int i=0; i<n; i++) {
            sum += line.charAt(i) - '0';
        }
        System.out.println(sum);
    }
}

아스키코드 '0'은 48

 

__[002] 평균 구하기

백준 온라인 져지 1546번 https://www.acmicpc.net/problem/1546

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[n];

        int max = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            if (a[i] > max) max = a[i];
        }

        double sum = 0.0;
        for (int i = 0; i < n; i++) {
            sum += (double) a[i] / max * 100.0;
        }

        System.out.println(sum / n);
    }
}

04-2 구간 합 (Prefix Sum)

구간 합은 합 배열을 미리 만들어서 여러 번의 구간 합을 빠르게 계산하는 알고리즘이다.

일반적으로 구간 합을 매번 계산하면 O(N)이 걸리지만,
누적합 배열을 만들면 O(1)에 계산 가능하다.

---

1차원 누적합 공식

S[i] = S[i-1] + A[i]

 

구간 합 (i ~ j)

S[j] - S[i-1]

 

---

2차원 누적합 공식

S[i][j] = S[i-1][j] + S[i][j-1]
          - S[i-1][j-1] + A[i][j]

 

직사각형 구간 합

S[x2][y2]
- S[x1-1][y2]
- S[x2][y1-1]
+ S[x1-1][y1-1]

 

__[003] 구간 합 구하기 1

백준 온라인 져지 11659번 https://www.acmicpc.net/problem/11659

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

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

        // 1) N, M 입력
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 2) 누적합 배열 만들기 (1-indexed)
        long[] prefix = new long[N + 1]; // prefix[0] = 0
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int x = Integer.parseInt(st.nextToken());
            prefix[i] = prefix[i - 1] + x;
        }

        // 3) M개의 구간합 처리
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < M; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            long ans = prefix[j] - prefix[i - 1];
            sb.append(ans).append('\n');
        }

        // 4) 출력
        System.out.print(sb.toString());
    }
}

__[004] 구간 합 구하기 2

백준 온라인 져지 11660번

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 누적합 배열 (1-indexed)
        int[][] S = new int[N + 1][N + 1];

        // 표 입력 받으면서 누적합 채우기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int val = Integer.parseInt(st.nextToken());
                S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + val;
            }
        }

        StringBuilder sb = new StringBuilder();

        // M개 질의 처리
        for (int k = 0; k < M; k++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int ans = S[x2][y2]
                    - S[x1 - 1][y2]
                    - S[x2][y1 - 1]
                    + S[x1 - 1][y1 - 1];

            sb.append(ans).append('\n');
        }

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

__[005] 나머지 합 구하기

백준 온라인 져지 10986번

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

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] sumArr = new long[n];   // 누적합 배열
        long[] counts = new long[m];   // 나머지별 개수
        long answer = 0;               // 정답

        //1. 두 번째 줄 (숫자들) 읽기
        st = new StringTokenizer(br.readLine());

        //2. 누적합 배열 만들기
        sumArr[0] = Long.parseLong(st.nextToken());

        for (int i = 1; i < n; i++) {
            sumArr[i] = sumArr[i - 1] + Long.parseLong(st.nextToken());
        }

        //3. 누적합 % m 계산
        for (int i = 0; i < n; i++) {

            int remainder = (int)(sumArr[i] % m);

            //4. 나머지가 0이면 (1 ~ i 구간이 m으로 나누어 떨어짐)
            if (remainder == 0) {
                answer++;
            }

            counts[remainder]++;
        }

        //5. 같은 나머지끼리 2개씩 뽑는 조합 계산
        for (int i = 0; i < m; i++) {
            if (counts[i] > 1) {
                answer += counts[i] * (counts[i] - 1) / 2;
            }
        }

        //6. 출력
        System.out.println(answer);
    }
}

04-3 투 포인터 (Two Pointer)

투 포인터는 두 개의 인덱스를 이용해 배열을 탐색하는 알고리즘 기법이다.

주로 사용되는 상황:

• 연속된 구간 합 문제
• 두 수의 합 문제
• 정렬된 배열에서 탐색

기본 아이디어

• 시작점(start), 끝점(end) 두 개의 포인터 사용
• 조건에 따라 포인터 이동
• 보통 정렬이 필요함

시간 복잡도: O(N)

__[006] 연속된 자연수의 합 구하기

백준 온라인 져지 2018번

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

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 1. 정수 N 입력받기
        int n = Integer.parseInt(br.readLine().trim());

        // 2. 필요한 변수 초기화
        // count : 경우의 수 (N 자체도 하나의 경우이므로 1로 시작)
        int count = 1;

        // start : 연속합 시작 지점
        int start = 1;

        // end : 연속합 끝 지점
        int end = 1;

        // sum : start ~ end까지의 합 (처음엔 1)
        int sum = 1;

        // 3. 투 포인터 알고리즘 시작
        // end가 n이 될 때까지 반복
        while (end != n) {

            // 3-1. 현재 구간 합이 n과 같은 경우
            if (sum == n) {
                count++;        // 경우의 수 증가
                end++;          // 끝 지점 확장
                sum += end;     // 확장된 값 더하기
            }

            // 3-2. 현재 구간 합이 n보다 큰 경우
            else if (sum > n) {
                sum -= start;   // 시작 지점 값을 빼고
                start++;        // 시작 지점 오른쪽 이동
            }

            // 3-3. 현재 구간 합이 n보다 작은 경우
            else {
                end++;          // 끝 지점 확장
                sum += end;     // 확장된 값 더하기
            }
        }

        // 4. 최종 경우의 수 출력
        System.out.println(count);
    }
}

__[007] 주몽의 명령

백준 온라인 져지 1940번

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 1. BufferedReader를 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 2. 첫째 줄에서 재료의 개수 N을 읽어 정수로 변환
        int n = Integer.parseInt(br.readLine());

        // 3. 둘째 줄에서 목표 합 M을 읽어 정수로 변환
        int m = Integer.parseInt(br.readLine());

        // 4. 셋째 줄에서 N개의 재료 번호를 읽기 위해 StringTokenizer를 사용
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 5. 재료 번호를 저장할 배열을 생성
        int[] arr = new int[n];

        // 6. 토큰을 하나씩 꺼내 배열에 재료 번호를 저장
        for (int k = 0; k < n; k++) {
            arr[k] = Integer.parseInt(st.nextToken());
        }

        // 7. 두 포인터 탐색을 위해 배열을 오름차순 정렬
        Arrays.sort(arr);

        // 8. 첫 번째 포인터 i는 배열의 시작 인덱스로 설정
        int i = 0;

        // 9. 두 번째 포인터 j는 배열의 끝 인덱스로 설정
        int j = n - 1;

        // 10. 쌍(갑옷)의 개수를 저장
        int count = 0;

        // 11. 두 포인터가 교차하기 전까지 반복하며 합을 탐색
        while (i < j) {
            // 12. 두 포인터가 가리키는 값의 합을 계산
            int sum = arr[i] + arr[j];

            // 13. 합이 M과 같다면 개수를 증가시키고 두 포인터를 모두 이동
            if (sum == m) {
                count++;
                i++;
                j--;
            }
            // 14. 합이 M보다 크다면 합을 줄이기 위해 큰 쪽 포인터(j)를 왼쪽으로 이동
            else if (sum > m) {
                j--;
            }
            // 15. 합이 M보다 작다면 합을 키우기 위해 작은 쪽 포인터(i)를 오른쪽으로 이동
            else {
                i++;
            }
        }

        // 16. 출력
        System.out.println(count);
    }
}

__[008] ‘좋은 수’ 구하기

백준 온라인 져지 1253번

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

public class Main {
    public static void main(String[] args) throws IOException {

        // 1. 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 2. 정렬
        Arrays.sort(arr);

        // 3. N이 2 이하이면 좋은 수 없음
        if (N <= 2) {
            System.out.println(0);
            return;
        }

        int count = 0;

        // 4. 각 원소를 기준으로 검사
        for (int result_ind = 0; result_ind < N; result_ind++) {

            int target = arr[result_ind];
            int left = 0;
            int right = N - 1;

            // 5. 투 포인터 탐색
            while (left < right) {

                // 자기 자신 제외
                if (left == result_ind) {
                    left++;
                    continue;
                }
                if (right == result_ind) {
                    right--;
                    continue;
                }

                long sum = (long) arr[left] + arr[right];

                if (sum == target) {
                    count++;
                    break;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        // 6. 결과 출력
        System.out.println(count);
    }
}

04-4 슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우는 고정된 길이의 구간을 이동시키면서 계산하는 방식이다.

투 포인터와 유사하지만,
구간 크기가 고정되어 있다는 점이 다르다.

 

핵심 아이디어

• 처음 윈도우 값 계산
• 한 칸 이동 시:
  • 앞의 값 제거
  • 뒤의 값 추가

시간 복잡도: O(N)

__[009] DNA 비밀번호

백준 온라인 져지 12891번

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

public class Main {

    // 1. 최소 필요 DNA 개수를 저장할 배열 (A, C, G, T 순서)
    public static int[] DNA = {0, 0, 0, 0};

    // 2. 알파벳 인덱스 매핑
    // A = 0, C = 2, G = 6, T = 19 (char - 'A' 기준)
    public static int[] IDX = {0, 2, 6, 19};

    public static void main(String[] args) throws IOException {

        // 3. 입력을 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int S = Integer.parseInt(st.nextToken()); // 전체 문자열 길이
        int P = Integer.parseInt(st.nextToken()); // 부분 문자열 길이

        String pwd = br.readLine().trim(); // DNA 문자열

        // 4. 최소 개수 조건
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            DNA[i] = Integer.parseInt(st.nextToken());
        }

        // 5. 현재 윈도우의 알파벳 개수를 저장할 배열
        int[] alpha = new int[20];

        // 6. 처음 P 길이만큼 문자 개수
        for (int i = 0; i < P; i++) {
            alpha[pwd.charAt(i) - 'A']++;
        }

        int res = 0; // 정답 카운트

        // 7. 슬라이딩 윈도우 시작
        for (int i = 0; i <= S - P; i++) {

            // 8. 조건을 만족하는지 확인
            int chk = 0;
            for (int j = 0; j < 4; j++) {
                if (DNA[j] <= alpha[IDX[j]]) {
                    chk++;
                }
            }

            // 9. 4개 조건 모두 만족하면 정답 증가
            if (chk == 4) {
                res++;
            }

            // 10. 윈도우를 오른쪽으로 한 칸 이동
            // 맨 앞 문자 제거, 새 문자 추가
            if (i + P < S) {
                alpha[pwd.charAt(i) - 'A']--;
                alpha[pwd.charAt(i + P) - 'A']++;
            }
        }

        // 11. 출력
        System.out.println(res);
    }
}

__[010] 최솟값 찾기

백준 온라인 져지 11003번

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1. N(개수), L(구간 길이)
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        // 2. 수열 저장
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 3. 최소값 후보 인덱스를 저장할 덱
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {

            // 4. 현재 값보다 큰 뒤쪽 인덱스 제거
            while (!deque.isEmpty() && arr[deque.getLast()] > arr[i]) {
                deque.removeLast();
            }

            // 5. 현재 인덱스 추가
            deque.addLast(i);

            // 6. 윈도우 범위 벗어난 인덱스 제거
            if (deque.getFirst() <= i - l) {
                deque.removeFirst();
            }

            // 7. 현재 구간 최소값 출력
            bw.write(arr[deque.getFirst()] + " ");
        }

        bw.flush();
    }
}