[자료구조, 알고리즘 스터디] 배열과 리스트, 구간 합

1. 자료구조

1) 배열과 리스트

배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다

 

배열의 값은 인덱스를 통해 참조할 수 있다

 

선언한 자료형의 값만 저장할 수 있다

 

 

배열의 특징

1) 인덱스를 사용하여 값에 바로 접근할 수 있다

2) 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다

값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요

3) 배열의 크기는 선언할 때 지정할 수 있으며 한 번 선언하면 크기를 늘리거나 줄일 수 없다

4) 구조가 간단하므로 코딩 테스트에서 많이 사용한다

 

리스트

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다

 

 

리스트의 특징

1) 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다

즉 값에 접근하는 속도가 느리다

2) 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도는 빠르다

3) 선언할 때 크기를 별도로 지정하지 않아도 된다

즉 리스트의 크기는 정해져 있지 않으며 크기가 변하기 쉬운 데이터를 다룰때 적절하다

4) 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다

 

2) 구간합

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는

특수한 목적의 알고리즘이다

 

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다

배열 A가 있을때 합 배열 S는 아래와 같이 정의한다

 

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

 

합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다

 

이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을

구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다

 

합 배열 S를 만드는 공식

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

 

구간 합을 구하는 공식

S[j] - S[i-1]	// i에서 j까지 구간의 합

 

A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

S[1] = A[0] + A[1]

S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

 

2. 문제 정리

001. 숫자의 합 구하기

입력 : 첫번째 줄 숫자의 개수, 두번째 줄 공백없이 주어진 N개의 숫자

출력 : 주어진 N개의 숫자를 모두 더해서 정수로 출력한다

풀이 : 공백없이 들어온 N개의 숫자는 String 값으로 받는다 예를들어 "12345" 이렇게

그러면 각 숫자를 char 형태로 하나씩 뽑아서 char[] 배열에 넣어서

아스키코드를 이용해서 for문을 돌려서 인덱스 0번째 - '0' = 정수 나오는 식으로해서

sum에 += 누적시켜 더하면 될것 같다

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 첫 번째 숫자의 개수
        int N = scanner.nextInt();
        // 두 번째 공백없이 주어진 N개의 숫자
        String sNum  = scanner.next();
        // 각 숫자를 뽑아서 char 배열에 넣기
        char[] cNum = sNum.toCharArray();
        // for문으로 배열에 있는 값을 아스키코드 이용해서 정수 만들기
        int sum = 0;
        for(int i=0; i<cNum.length; i++) {
            sum += cNum[i] - '0';
        }
        System.out.println(sum);
    }
}

 

002. 평균 구하기

입력 : 첫번째 줄 시험을 본 과목의 개수 두번째 줄 각 과목의 점수

출력 : 과목의 점수/최고 점수 과목 * 100 을 마친 과목 점수들의 평균

풀이 : 최고 점수를 구해야하니 max 변수에 넣고 각 점수들을 int[] 에 넣어서

for문으로 각 점수들 뽑아서 각 과목별로 조작 점수를 만드는데

예를들어 3과목이면 과목의 점수/최고 점수 과목 * 100 이걸 3번 반복해야하는데

과목의 총 점수/최고 점수 과목 * 100 이렇게하면 1번으로 할 수 있다

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 평균 구하기
		Scanner scanner = new Scanner(System.in);

		// 첫번째 줄 시험을 본 과목의 개수
		int N = scanner.nextInt();
		// 두번째 줄 각 과목의 점수 넣을 int[]
		int score[] = new int[N];
		// for문으로 score에 각 과목의 점수를 넣는다
		for(int i=0; i<N; i++) {
			score[i] = scanner.nextInt();
		}
		// 배열에서 max값과 sum을 구한다
		long max = 0;
		long sum = 0;
		for (int i=0; i<score.length; i++) {
			if (score[i] > max) {
				max = score[i];
			}
			sum += score[i];
		}

		// System.out.println(sum / max * 100 / N);	// 66	// int로 나누니까 정수로 나온다
		System.out.println(sum * 100.0 / max / N);	//75	// 100.0 으로 먼저하니 소수로 된다
	}
}

 

003. 구간 합 구하기

입력 : 첫번째 줄 수의 개수, 질의 수 두번째 줄 N개의 수 세번째 줄 M개의 줄에 합을 구해야하는 구간  i와 j가 주어진다

출력 : i번째 수에서 j번째 수까지의 합을 출력한다

풀이 : 수의 개수 만큼 for문 돌려서 합 배열을 완성 시킨다 합배열은 s[i] = s[i-1]  + a[i] 이다

그리고 합을 구해야 하는 수 만큼 for문 돌려서 질의 i와 j를 를 받는다

그리고 구간 합을 출력해 준다 구간 합 은 s[j] - s[i-1] 이다

 

package codingTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main003 {
	public static void main(String[] args) throws IOException {
		// 구간 합 구하기 1
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

		// 첫번째 줄 수의 개수
		int suNo = Integer.parseInt(stringTokenizer.nextToken());
		// 첫번째 줄 질의 개수
		int quizNo = Integer.parseInt(stringTokenizer.nextToken());
		// 합 배열 생성
		long[] S = new long[suNo + 1];
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i=1; i<=suNo; i++) {
			S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
		}
		// 구간 합 구하기
		for(int q = 0; q<quizNo; q++) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());
			System.out.println(S[j] - S[i-1]);
		}
	}
}

 

참고

- Do it 알고리즘 코딩 테스트