Java 코딩 테스트 교재 #3

Do it! 알고리즘 코딩 테스트 - 자바 편

http://www.easyspub.co.kr/20_Menu/BookView/500/PUB

 

3장 : 자료구조

---

💡 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇

문제의 입력 데이터 형태와 사용해야 하는 알고리즘에 따라 적절한 자료구조를 선택하는 것이 매우 중요하다

 

03-1 배열과 리스트

---

배열과 리스트는 비슷한 점도 많지만 다른 점도 많다

 

배열과 리스트의 핵심 이론

• 배열 : 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
  • 인덱스로 참조
  • 선언한 자료형 값만 저장 가능
  • 배열의 특징
    • 인덱스를 사용하여 값에 바로 접근 가능
    • 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움(해당 인덱스 값 이동 필요)
    • 구조가 간단하므로 코딩 테스트에서 많이 사용 됨
• 리스트 : 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
  • 리스트의 특징
    • 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 함 (느림)
    • 포인터로 연결되어 있으므로 데이터 삽입 삭제 속도가 빠름
    • 선언할 때 크기를 별도로 지정하지 않아도 됨 (크기가 변하기 쉬운 데이터를 다루기 좋음)
    • 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함

[연습문제 #001 : 숫자의 합 구하기 (boj_11720)]

n 개의 수가 공백없이 입력되고 총합을 출력한다

• 1 ≤ N ≤ 100
• 제한시간 1초

01단계 문제 분석하기

• N의 범위가 1부터 100까지 공백없이 입력되므로 int, long 형 같은 숫자형으로 담을 수 없음
• 먼저 문자열로 받은 후 배열로 변환해 순서대로 읽으면서 숫자형으로 변환해 더해야함
  • 문자형 숫자를 처리하기 위해 아스키코드 값을 알아야함

02단계 손으로 풀어보기

1. 입력값을 String형으로 저장 : String sNum = 10987654321
2. String형으로 입력받은 값을 char[]형으로 변환
3. 인덱스 0부터 끝까지 배열을 탐색하며 값을 정수형으로 변환해 누적

03단계 슈도코드 작성하기

N값 받기
길이 N의 숫자를 입력받아 String형 변수 sNum에 저장하기
sNum을 다시 char[]형 변수 cNum에 저장하기
int형 변수 sum 선언하기
for(cNum 길이만큼 반복하기)
{
  배열의 각 자릿값을 정수형으로 변환하며 sum에 더하여 누적하기
}
sum 출력하기

04단계 코드 구현하기

Import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String sNum = sc.next();
		char[] cNum = sNum.toCharArray();
		int sum = 0;
		for (int i = 0; i < cNum.length; i++){
			sum += cNum[i] - '0';
		}
		System.out.print(sum);
	}
}

자바에서의 형 변환 ex int) Integer.parseInt(문자열) // Integer.valueOf(문자열);

💡 parseInt와 valueOf의 차이 parseInt는 기본 자료형을 반환 valueOf는 객체를 반환. 2번째 인자값을 넣어서 10진수가 아닌 다른 진수로 리턴가능

 

[연습문제 #002 : 평균 구하기 (boj_1546)]

n 개의 수가 공백없이 입력되고 총합을 출력한다

• 1 ≤ N ≤ 100
• 제한시간 1초

 

03-2 구간 합

---

합 배열을 이용해 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘

 

구간 합의 핵심 이론

먼저 합 배열을 구해야 함

• 합 배열 : S[i] = A[0] + A[1] + … + A[i-1] + A[i] ⇒ A[0]부터 A[i]까지의 합
  • 합 배열은 기존의 배열을 전처리한 배열
  • 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함
• 합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i]
• 구간 합을 구하는 공식 : S[j] - S[i-1] (i~j 구간합)

 

[연습문제 #003 : 구간 합 구하기 (boj_11659)]

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N
• 제한시간 1초

01단계 문제 분석하기

• 수의 개수와 합을 구해야하는 회수는 최대 10만이므로 구간마다 합을 매번 계산하면 시간초과
  • 최악의 경우 1억 회 이상 연산 → 1초 이상의 수행 시간

<02단계 손으로 풀어보기 생략>

<03단계 슈도코드 작성하기 생략>

<04단계 코드 구현하기 생략>

 

---

[연습문제 #004 : 구간 합 구하기 2 (boj_11659)]

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다.

표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

제한

• 제한시간 1초

01단계 문제 분석하기

• 질의의 개수가 10만이므로 역시 질의마다 합을 구하면 안되고 구간 합 배열을 이용해야 한다.
• 구간 합 배열이 1차원에서 2차원으로 확장된 것으로 생각하여 어떻게 구성할지 고민하는 것이 이 문제의 핵심
• 2차원 구간 합 배열 D[X][Y]의 정의
  • D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합

02단계 손으로 풀어보기

1. 2차원 구간 합 배열의 1행과 1열부터 구한다.
   1. D[i][1] = D[i-1][1] + A[i][1]
   2. D[1][j] = D[1][j-1] + A[1][j]
2. 이를 통해 나머지 2차원 구간 합 배열을 채운다.
   1. D[i][j]의 값을 채우는 구간 합 공식 : D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
3. 질의 1번 (2 2 3 4)로 확인해보기
   1. 질의 X1, Y1, X2, Y2 에 대한 답을 구간 합으로 구하는 방법
   2. : D[X2][Y2] - D[X1 - 1][Y2] - D[X2][Y1 - 1] + D[X1 - 1][Y1 - 1]

<03단계 슈도코드 작성하기 생략>

<04단계 코드 구현하기 포스팅>

---

[연습문제 #005 : 나머지 합 구하기 (boj_10986)]

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

제한

• 제한시간 1초

01단계 문제 분석하기

• 모든 구간 합을 매번 구하거나, 그 나머지를 계산하면 시간초과
• 핵심 아이디어
  • (A + B) % C == ((A % C) + (B % C)) % C 이다.
  • 구간 합 배열을 이용한 식 S[i] - S[j] 는 j + 1 부터 i 까지의 구간 합이다.
  • S[i] % M 의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. ⇒ S[i] 와 S[j] 가 같은 쌍을 찾는다.

02단계 손으로 풀어보기

1. A 배열의 합 배열 S를 생성
2. 합 배열 S의 모든 값을 M으로 나머지 연산을 수행해 값을 업데이트
3. 나머지 연산한 원소 값이 0이면 정답에 +1 ← 0부터 i까지의 구간 합이 이미 M으로 나누어 떨어짐
4. 나머지 연산한 원소 값이 같은 쌍의 수를 정답에 +1

<03단계 슈도코드 작성하기 생략>

<04단계 코드 구현하기 포스팅>

 

 

원본 노션 정리 글

자바 알고리즘 교재 #3