섹션 2. 코딩테스트 - 자료구조 (1) 파트

728x90

섹션 2. 코딩테스트 [기초]

⬛ 03. 자료구조

⬛ 03-1. 배열과 리스트

🟦 배열과 리스트

🟧 배열

메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
각 값은 인덱스를 통해 참조 가능
배열 크기는 최초 선언 시 지정 가능하며, 한 번 선언한 뒤 크기 변경 불가능

🟧 리스트

값과 포인터를 묶은 노드를 다시 포인터로 연결한 자료구조
선언 시 크기 별도 지정 안하므로 크기 정해져 있지 않다.

⬛ 03-2. ‘구간 합’ 알고리즘

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 미리 구간합을 구해놓는 알고리즘 ****

🟦 구간 합 알고리즘

1차원 배열의 합 배열 S[i]

🟧 1) 합 배열 S의 정의

S[i] = A[0] + A[1] + ... + A[i]; //A[0] ~ A[i]까지의 합 저장

🟧 2) 합 배열 S 만드는 공식

직전까지의 합이 저장된 S[i-1]에 현재의 A[i]값을 저장하면 현재까지의 S[i] 전체 구간합 구할 수 O

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

🟧 3) 특정 구간 합을 구하는 공식

예를 들어, i ~ j까지의 구간합을 구하고 싶다고 한다면

S[j] - S[i-1] // i~j까지의 구간합만 구해진다.

🟦 백준 11659번. 구간 합 구하기 4

이 문제는 시간 제한이 0.5초인데, 데이터 크기가 100,000 이었다.
이중 for문 돌지 않고 구간 합을 구하기 위해 이 알고리즘이 필요하다.

package to_0531_1;

import java.util.Scanner;

/* 11659번. 구간 합 구하기 4
 * */
public class Solution {

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);

        int N = kb.nextInt();
        int M = kb.nextInt();

        int[] arr = new int[N+1];
        int[] sum = new int[N+1];
        //구간합 구해야 하는 이유 : 시간 제한 0.5초이므로
        for(int i=0; i<N; i++) {
            arr[i+1] = kb.nextInt();
            //동시에 구간합 구해놓기 
            sum[i+1] = sum[i] + arr[i+1]; //구간 합 
        }

        int[] answer = new int[M];
        //i, j 입력 받으면서 구함
        for(int i=0; i<M; i++) {
            int k = kb.nextInt();
            int j = kb.nextInt();

            answer[i] = sum[j] - sum[k-1];
        }

        //정답 출력
        for(int x : answer) {
            System.out.println(x);
        }
    }

}

2차원 배열의 합 배열 D[x][y]

🟧 1) 2차원 구간 합 배열 D[X][Y] 정의

D[X][Y] = 원본 배열의 (0,0) ~ (X,Y) 까지의 사각형 영역 안에 있는 수들의 합

🟧 2) D[i][j] 의 값 채우는 구간 합 공식

예를 들어. D[2][2]를 구하려면, D[1][2] + D[2][1] - D[1][1] + A[2][2]

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

🟧 3) 질의 X1, Y1, X2, Y2 에 대한 답을 구간 합으로 구하는 방법

D[x2][y2] - D[X1-1][y2] - D[X2][y-1] + D[X1-1][y1-1]

⬛ 03-3. ‘투 포인터’ 알고리즘

🟦 투 포인터 알고리즘

2개의 지칭 포인터로 알고리즘 시간복잡도 최적화한다.

🟧 투 포인터 이동 원칙

1) sum == N

count++, ed++, sum = sum + ed; //다음을 위해

2) sum > N

sum = sum - st; st++; // 앞을++

3) sum < N

ed++; sum = sum + ed; //뒤를++

🟦 백준 2018번. 연속된 자연수의 합

이 문제는 제한 시간 2초인데 N이 10,000,000 이므로, O(N) 으로 끝내야 한다.
따라서 연속된 자연수의 합을 두 개의 포인터 (시작, 끝) 지칭하면서 N과 비교하며 풀이
ed 포인터가 N과 같아질 때까지 반복하되, 포인터가 이동할 때마다 현재의 총합 sum 값과 N을 비교하며 같을 때만 count++처리하면 된다.
[주의] 여기서 cnt=1로 초기화 하는 이유 : 15 자기 자신을 뽑는 1가지 경우를 미리 세팅한 것.

package to_0531_1;

import java.util.Scanner;

/* 2018번. 연속된 자연수의 합 구하기 */
public class Main {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt();
        int sum = 1, count = 1; 

        int st = 1, ed = 1;

        while(ed != N) {
            if(N == sum ) {
                count++;
                ed++;
                sum = sum + ed;
            }else if(sum < N) {
                ed++;
                sum = sum+ed;
            }else if(sum > N) {
                sum = sum - st;
                st++;
            }
        }

        System.out.println(count);
    }

}

🟦 백준 1940번. 주몽

이 문제도 두 개의 재료 합이 M이 될 때 카운팅값 리턴하는 문제인데, O(n logn)에 끝내야 하는 문제이다.
일단 재료를 오름차순 정렬 시켜놓고 두개의 값 지칭할 포인터를 양 끝단에 위치시킨다.
양 끝단 포인터가 서로 만나지 않는 동안 반복시키면서 아래의 원칙을 지킨다.

🟧 투 포인터 이동 원칙

1) A[i] + A[j] > M

큰 번호 - -

2) A[i] + A[j] < M

작은 번호 ++

3) A[i] + A[j] == M

큰 번호, 작은 번호 모두 이동시킴
count++

import java.util.Arrays;
import java.util.Scanner;

/* 1940번. 주몽 
 * */
public class Main {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt(); //재료 개수
        int m = kb.nextInt(); //합
        int[] arr= new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = kb.nextInt();
        }

        //정렬
        Arrays.sort(arr);

        int st = 0, ed = n-1;//양끝단에 각각 두기 
        int count = 0;
        int sum = 0;
        while(st < ed) {
            sum = arr[st] + arr[ed];
            if(sum == m) {
                count++;
                st++;
                ed--;
            }else if(sum > m) {
                ed--;
            }else if(sum < m) {
                st++;
            }
        }

        System.out.println(count);
    }
}

🟦 백준 1253번. ‘좋은 수’ 구하기

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

풀이

이 문제는 데이터 각 A[i]값이 최대 1,000,000,000 이고, 시간 제한 2초이므로 시간복잡도가 최대 O(nlogn)으로 끝나야 한다.
정렬, 투 포인터 알고리즘을 사용해야 한다.
우선 정렬시켜놓고 for문으로 각각의 k번째 수를 찍은 뒤 내부의 while문으로 양쪽 i,j 끝에 찍어놓은 두 수의 합을 k와 비교하며 조건을 걸면 된다.

package to_0605_1;

import java.util.Arrays;
import java.util.Scanner;

/*1253번. 좋은 수 */
public class Main {

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) arr[i] = kb.nextInt();

        Arrays.sort(arr);

        int answer=0; //카운팅 세팅용 

        for(int k=0; k<n; k++) {
            int cur = arr[k]; //현재 찍은 k값에 대하여  
            int i = 0, j = n-1;//양쪽 끝에 두고 
            while(i < j) { // 두 포인터 만나기 전까지 반복하면서 
                if(arr[i] + arr[j] == cur) {//두 수의 합이 cur과 같다면
                    if(i != k && j != k) {// 두 수 모두가 k번째도 아니라면 
                        answer++;
                        break;//현재의 turn은 종료 다음 turn으로 이동 
                    }else if(i == k) { //현재 i가 k번쨰 수이면 
                        i++;//i이동
                     }else if(j == k) { //현재 j가 k번째 수이면 
                         j--;//j이동 
                     }
                }else if(arr[i]+arr[j] < cur) { //cur보다 작다면 
                    i++;             
                }else if(arr[i]+arr[j] > cur) {
                    j--;
                }
            }
        }
        //출력

        System.out.println(answer);

    }

}