고민의 흔적

참조형 매개변수

변수의 값을 읽고 변경할 수 있다.

반환 타입이 참조형일 경우 복사한 객체의 주소를 반환한다.

인스턴스 메서드

인스턴스 생성 후, 참조 변수. 메서드 이름()으로 호출

인스턴스 맴버와 관련된 작업을 하는 메서드

메서드 내에서 인스턴스 변수 사용 가능

static 메서드(클래스 메서드)

객체 생성 없이 클래스 이름. 메서드 이름()으로 호출

ex) Math.random() 등

인스턴스 멤버와 관련 없는 작업을 하는 메서드

메서드 내에서 인스턴스 변수 사용불가

static은 언제 붙여야 할까?

속성(멤버 변수) 중에서 공통 속성에 static 붙인다.

인스턴스 멤버를 사용하지 않는 메서드에 static 붙인다.

오버로딩

하나의 클래스 안에 같은 이름의 메서드를 여러 개 정의하는 것

오버로딩이 성립하기 위한 조건

1. 메서드 이름이 같아야 한다.
2. 매개변수의 개수 또는 타입이 달라야 한다.
3. 반환 타입은 영향 없다.

오버로딩의 올바른 예 - 매개변수는 다르지만 같은 의미의 기능 수행

생성자

인스턴스가 생성될 때마다 호출되는 인스턴스 초기화 메서드

이름이 클래스와 같아야 한다.

클래스 이름(타입 변수명, 타입 변수명, ...) {
	// 인스턴스 수행될 코드,
    // 주로 인스턴스 변수의 초기화 코드를 적는다.
}

생성자 this()

생성자에서 다른 생성자 호출할 때 사용

같은 클래스의 다른 생성자 호출 시 첫 줄에서만 사용 가능

참조변수 this

인스턴스 자신을 가리키는 참조변수

인스턴스 메서드(생성자 포함)에서 사용 가능

지역변수와 인스턴스 변수를 구분할 때 사용

상속

기존의 클래스로 새로운 클래스를 작성하는 것

두 클래스를 부모와 자식의 관계를 맺어주는 것

자손은 조상의 모든 멤버를 상속받는다.

자손의 멤버 개수는 조상보다 적을 수 없다.

자손의 변경은 조상에 영향을 미치지 않는다.

포함관계

포함

클래스의 멤버로 참조 변수를 선언하는 것

작은 단위의 클래스를 만들고 이들을 조합해서 클래스를 만든다.

class Point {
	int x;
    int y;
}
class Circle {
	point c = new Point();
    int r;
}

상속관계 : ~은 ~이다.(is-a)

포함관계 : ~은 ~을 가지고 있다.(has-a)

Object 클래스 - 모든 클래스의 조상

부모가 없는 클래스는 자동적으로 Object클래스를 상속받게 된다.

모든 클래스는 Object클래스에 정의된 11개의 메서드를 상속받는다. 

toString(), equals(), hashCode(), ...

오버라이딩

상속받은 조상의 메서드를 자신에 맞게  변경하는 것

오버라이딩 조건

1. 선언부(반환 타입, 메서드 이름, 매개변수 목록)가 조상 클래스의 메서드와 일치해야 한다.
2. 접근 제어자를 조상 클래스의 메서드보다 좁은 범위로 변경할 수 없다.
3. 예외는 조상 클래스의 메서드보다 많이 선언할 수 없다.

참조변수 super

객체 자신을 가리키는 참조변수. 인스턴스 메서드(생성자) 내에만 존재

조상의 멤버를 자신의 멤버와 구별할 때 사용

super() - 조상의 생성자

조상의 생성자를 호출할 때 사용

조상의 멤버는 조상의 생성자를 호출해서 초기화

생성자의 첫 줄에 반드시 생성자를 호출해야 한다. 그렇지 않으면 컴파일러가 생성자의 첫 줄에 super()를 삽입

import문

java.lang 패키지의 클래스는 import하지 않고도 사용 가능

import 패키지명.클래스명;

import 패키지명.*;

static import문

static멤버를 사용할 때 클래스 이름을 생략할 수 있게 해 준다.

import static java.lang.System.out;
import static java.lang.Math.*;

class EX {
	public static void main(String[] args) {
    	// System.out.println(Math.random());
        out.println(random());
        
        //System.out.println(Math.PI);
        out.println(PI);
    }
}

83번 선물 전달

내가 떠올린 풀이 해설

완전 순열이라는 개념을 사용하는 문제이다. 완전 순열은 n개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없을 때를 말한다. arr[n] 배열의 의미를 n명일 때 선물을 교환할 수 있는 모든 경우의 수로 정한다. n명이 존재한다고 가정하고 A와 B라는 학생에게 선물을 줬다고 가정하자 이때는 교환 방식이 2가지가 존재한다.

선물을 교환하는 2가지 방식

1. B도 A에게 선물을 줬을 때 : N명 중 2명이 교환을 완료했으므로 남은 경우의 수는 arr[n - 2]
2. B는 A가 아닌 다른 친구에게 선물을 전달할 때 : N명 중 B만 받은 선물이 정해진 상태이므로 남은 학생은 N - 1이며 경우의 수는 arr[n - 1]이다

A는 자기 자신이 아닌 N - 1명에게 선물을 전달 할 수 있다. 이 과정으로 경우의 수를 구하는 점화식은 arr[N] = (N - 1) * (arr[N - 2] + arr[N - 1]) 

정확한 풀이

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

public class Baek1947 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long mod = 1000000000;
		long[] arr = new long[1000001];
		arr[1] = 0;
		arr[2] = 1;
		for(int i = 3; i <= n; i++) {
			arr[i] = (i - 1) * (arr[i - 2] + arr[i - 1]) % mod;
		}
		System.out.println(arr[n]);
	}
}

84번 1로 만들기

내가 떠올린 풀이 해설

사용할 수 있는 3가지 연산을 바텀-업 방식으로 구현할 수 있는지 연습하는 문제이다. 

1. 점화식 형태와 의미를 도출한다. 

arr[i] : i 에서 1로 만드는 데 걸리는 최소 연산 횟수

2. 점화식을 구한다.

arr[i] = arr[i - 1] + 1 // 1을 빼는 연산이 가능함
if(i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1) // 2로 나누는 연산이 가능함
if(i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1) // 3으로 나누는 연산이 가능함

3. 점화식을 이용해 arr배열을 채운다.

4. arr[n] 을 출력한다.

정확한 풀이

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

public class Baek1463 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		int[] arr = new int[n + 1];
		arr[1] = 0;
	
		for(int i = 2; i <= n; i++) {
			arr[i] = arr[i - 1] + 1;
			if(i % 2 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 2] + 1);
			}
			if(i % 3 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 3] + 1);
			}
		}
		System.out.println(arr[n]);
	}
}

오늘의 회고

오늘은 조합 1문제와 DP문제를 풀었습니다. 점화식 세우는 방법이 너무 어렵습니다.. 지금까지 혼자 잘 공부해왔지만 불안한 감도 있어서 프로그래머스에서 [커뮤러닝/6기] 코딩 테스트 실력 UP 강의를 자부담비 10%와 내일배움카드가 90%를 지원해준다고 해서 신청하게 되었습니다. 선발된 과정에 충실하게 공부해서 실력을 한층 더 높이는 계기가 되었으면 좋겠습니다. 하반기에 원하는 기업에 입사하고 싶습니다.

1. 기본형과 참조형

1bit = 2진수 한자리

1byte = 8bit

기본형

오직 8개 (boolean, char, byte, short, int, long, float, double)

정수형 : byte 1byte, short 2byte, int 4byte, long 8byte

실수형 : float 4byte, double 8byte

논리형 : boolean 1byte

문자형 : char 2byte (java에서는 2바이트 유니코드를 사용하기 때문)

실제 값을 저장

참조형

기본형 8개를 제외한 모든 것 (String, System 등)

참조형 변수는 객체의 주소를 저장하기 위한 것

메모리 주소를 저장(4byte : 32bit JVM 또는 8byte : 64bit JVM)

2. 조건 연산자

조건식에 결과에 따라 연산 결과를 달리한다.

조건식 ? 식1 : 식2

조건식이 참이면 식1 거짓이면 식2

3. for문에 이름을 붙인다.

loop1 : for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		break; → 안쪽 for문만 끝난다.
        break loop1; → loop1이라는 이름이 붙은 반복문이 끝난다.
	}
}

4. 객체지향

클래스

정의 : 객체를 정의해 놓은 것

용도 : 클래스는 객체를 생성하는 데 사용

객체

정의 : 실제로 존재하는 것, 사물 또는 개념

용도 : 객체가 가지고 있는 기능과 속성에 따라 다름

객체 = 속성(변수) + 기능(메서드)

객체 : 모든 인스턴스를 대표하는 일반적 용어

인스턴스 : 특정 클래스로부터 생성된 객체 객체와 인스턴스는 같은 단어

1. 객체의 생성
클래스명 변수명; // 클래스의 객체를 참조하기 위한 참조변수를 선언
변수명 = new 클래스명(); // 클레스의 객체를 생성 후, 객체의 주소를 참조변수에 저장  

ex)
TV t;  // TV클래스 타입의 참조변수 t를 선언
t = new TV(); // TV인스턴스 생성한 후, 생성된 TV인스턴스의 주소를 t에 저장

TV t = new TV();

2. 객체의 사용
t.channel = 7; // TV인스턴스의 맴버변수 channel의 값을 7로 한다.
t.channelDown(); // TV인스턴스의 메서드 channelDown()을 호출  

5. 객체 배열

객체 배열 == 참조 변수 배열

6. 클래스의 정의

클래스 == 데이터 + 함수

1. 변수 : 하나의 데이터를 저장하는 공간
2. 배열 : 같은 종류의 여러 데이터를 하나로 저장할 수 있는 공간
3. 구조체 : 서로 관련된 여러 데이터(종류 관계 x)를 하나로 저장할 수 있는 공간
4. 클래스 : 데이터와 함수의 결합(구조체 + 함수)

7.  선언 위치에 따른 변수의 종류

class Variables { // 클래스 영역
	int iv;  // 인스턴스 변수
    static int cv; // 클래스 변수(static 변수, 공유변수)
    
    void method() {  // 메소드 영역
    	int lv = 0; // 지역변수    
    }
}

8. 클래스 변수와 인스턴스 변수

class Card {
	String kind; // 무늬
    int number;  // 숫자
    
    static int width = 100;  // 폭
    static int height = 250; // 너비
}

Card c = new Card();
// 인스턴스 변수
c.kind = "HEART";
c.number = 5;
// 클래스 변수
Card.width = 200;
Card.height = 300;

9. 메서드

메서드의 장점

• 코드의 중복을 줄일 수 있다.
• 코드의 관리가 쉽다.
• 코드를 재사용할 수 있다.
• 코드가 간결해서 이해하기 쉬워진다.

메서드 작성

• 반복적으로 수행되는 여러 문장을 메서드로 작성
• 하나의 메서드는 한 가지 기능만 수행하도록 작성

MyMath mm = new MyMath(); // 1. 먼저 인스턴스를 생성한다.
long value = mm.add(1L, 2L); // 2. 메서드를 호출한다.

long add(long a, long b) {
	long result = a + b;
    return result;  // 반환타입이 void가 아닌 경우, 반드시 return문 필요
}
1. main 메서드에서 메서드 add를 호출한다. 인수 1L과 2L이 메서드 add의 매개변수 a, b에 각각 복사(대입)된다.
2. 메서드 add의 괄호 {} 안에 있는 문장들이 순서대로 실행된다.
3. 메서드 add의 모든 문장이 실행되거나 return문을 만나면, 호출한 메서드(main메서드)로 되돌아와서 이후의 문장들을 실행한다.

10. 호출 스택(call stack)

스택 : 밑이 막힌 상자, 위에 차곡차곡 쌓인다.

넣을 때

꺼낼 때

호출 스택

1. 메서드가 수행에 필요한 메모리가 제공되는 공간
2. 메서드가 호출되면 호출 스택에 메모리 할당, 종료되면 해제

class CallStack {
	public static void main(String[] args) {
    	System.out.println("Hello");
    }
}

아래에 있는 메서드가 위의 메서드를 호출한 것

맨 위의 메서드 하나만 실행 중, 나머지는 대기 중

11. 기본형 매개변수

기본형 매개변수 : 변수의 값을 읽기만 할 수 있다. (read only)

참조형 매개변수 : 변수의 값을 읽고 변경할 수 있다. (read & write)

82번 사전

내가 떠올린 풀이 해설

a와 z의 개수가 각각 N, M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N + M 개에서 N개를 뽑는 경우의 수 또는 N + M개에서 M개를 뽑는 경우의 수와 동일하다. arr배열을 초기화하고, 점화식으로 값을 계산해 저장한다. 몇 번째 문자열을 표현해야 하는지를 나타내는 변수를 K라고 하자 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수는 T이다. T와 K를 비교해 문자를 선택한다. 문자 선택 기준은 T >= K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 Z로 선택하고, K = K - T로 업데이트 

ex) a = 2, z = 2이고 a를 선택했을 때 나머지 문자열로 만들 수 있는 경우의 수는 arr[남은문자 총 개수 : 3][남은 z개수 : 2]

arr [3][2] = 3 >= k(2)이므로 a 확정 -> z는 2개 남음

arr [3][2] = 3 < k(2)이므로 z 확정 -> z는 1개 남음 -> K = K - T = 1로 업데이트

arr [1][1] = 1 >= k(1)이므로 a 확정 -> z는 1개 남음

arr [0][1] = 1 < k(2)이므로 z 확정

정확한 풀이

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

public class Baek1256 {

	public static void main(String[] args) throws IOException {
		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());
		int k = Integer.parseInt(st.nextToken());
		int [][] arr = new int[202][202];
		for(int i = 0; i <= 200; i++) {  // 조합 테이블 초기화 
			for(int j = 0; j <= i; j++) {
				if(j == 0 || j == i) {
					arr[i][j] = 1;
				}
				else {
					arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
					if(arr[i][j] > 1000000000) { //k 범위가 넘어가면 범위의 최댓값 
						arr[i][j] = 1000000001;
					}
				}
			}
		}
		if(arr[n + m][m] < k) { // 주어진 자릿수로 만들 수 없는 K번째 수이면 
			System.out.println(-1);
		}
		else {
			// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K 보다 크면 
			while(!(n == 0 && m == 0)) {
				if(arr[n - 1 + m][m] >= k) {
					System.out.print("a");
					n--;
				}
				else { // 모든 경우의 수가 k보다 작으면 
					System.out.print("z");
					k = k - arr[n - 1 + m][m]; // k값 업데이트 
					m--;
				}
			}
		}
	}
}

오늘의 회고

오늘은 캐치 콘에서 하는 세미나 참가로 조합 문제 1문제를 풀었습니다. 이제 조합 문제 1문제가 남았고 이제 DP를 들어갈 차례입니다. DP까지 풀면 중요한 알고리즘은 다 풀었습니다. 개념 복습을 하면서 다시 문제 풀고 문제 복습을 하는 순서로 공부를 해야겠습니다.

80번 조약돌 꺼내기

내가 떠올린 풀이 해설

단순하게 확률로 풀었습니다. 조약돌 개수를 배열에 담아서 한 색깔의 조약돌만 뽑을 확률을 색깔별로 모두 구하고 각각의 확률을 더해 정답으로 출력했다.

ex) 5개 조약돌이 있는 색만 뽑을 확률 : 5/18 * 4/17

정확한 풀이 1

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

public class Baek13251 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		
		int[] cnt = new int[M];
		double sum = 0.0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			cnt[i] = Integer.parseInt(st.nextToken());
			sum += cnt[i];
		}
		int K = Integer.parseInt(br.readLine());
		
		double answer = 0.0;
		for(int i = 0; i < M; i++) {
			double max = 1.0;
			for(int j = 0; j < K; j++) {
				max *= (cnt[i] - j) / (double)(sum - j);
			}
			answer += max;
		}
		System.out.println(answer);
	}
}

81번 순열의 순서

내가 떠올린 풀이 해설

이 문제는 조합 문제와 다르게 순열의 개념을 알아야 풀 수 있다. 순열은 순서가 다르면 다른 경우의 수로 인정된다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 이 문제의 핵심이다. 먼저 각 자리에서 사용할 수 있는 경우의 수를 구한다. 각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다. 4자리로 표현되는 모든 경우의 수는 4! = 24이다. N자리로 만들 수 있는 순열의 모든 경우의 수는 N!이다.

k번째 순열 출력하기

1. 주어진 값(k)과 현재 자리(n) - 1에서 만들 수 있는 경우의 수를 비교한다.
2. 1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)
3. k가 더 작아지면 순열에 값을 저장하고 k를 k - (경우의 수 * (cnt - 1))로 업데이트한다.
4. 순열이 완성될 때까지 1 ~ 3을 반복하고 완료된 순열을 출력한다.

입력된 순열 순서 구하기

1. N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인한다.(현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
2. 해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 k에 더한다.
3. 모든 자릿수에 관해 1 ~ 3을 반복한 후 K값을 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1722 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr[] = new ArrayList[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		long f[] = new long[21];
		int[] s = new int[21];
		boolean visit[] = new boolean[21];
		f[0] = 1;
		for(int i = 1; i <= n; i++) {  // 팩토리얼 초기화 -> 각 자리수에서 만들 수 있는 경우의 수 
			f[i] = f[i - 1] * i;
		}
		
		if(m == 1) {
			long k = Long.parseLong(st.nextToken());
			for(int i = 1; i <= n; i++) {
				for(int j = 1, cnt = 1; j <= n; j++) {
					if(visit[j]) {
						continue;  // 이미 사용한 숫자는 사용할 수 없음 
					}
					if(k <= cnt * f[n - i]) { // 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기 
						k -= ((cnt - 1) * f[n - i]);
						s[i] = j;
						visit[j] = true;
						break;
					}
					cnt++;
				}
			}
			for(int i = 1; i <= n; i++) {
				System.out.print(s[i] + " ");
			}
		}
		else {
			long k = 1;
			for(int i = 1; i <= n; i++) {
				s[i] = Integer.parseInt(st.nextToken());
				long cnt = 0;
				for(int j = 1; j < s[i]; j++) {
					if(visit[j] == false) {
						cnt++;   // 미사용 숫자 개수 만큼 카운트 
					}
				}
				k += cnt * f[n - i]; // 자릿수에 따라 순서 더하기 
				visit[s[i]] = true;
			}
			System.out.println(k);
		}
	}
}

오늘의 회고

오늘은 조합 중에 좀 어려운 문제 2문제를 풀었습니다. 두 번째 푼 문제는 아이디어를 떠올리는데 안 떠올라서 풀지 못했습니다. 알고리즘 문제를 잘 풀고 싶습니다. 아직은 많이 부족한 것 같습니다. 열심히 나아가겠습니다.

76번 이항 계수 1

내가 떠올린 풀이 해설

조합에서 가장 기본이 되는 문제이다. 일반 점화식을 이용하면 쉽게 해결할 수 있는 문제이다. n과 k를 입력받고 DP 배열을 선언한다. 배열은 arr [n + 1][n + 1] 그리고 DP 배열의 값을 다음과 같이 초기화한다. arr [i][1] = i -> i 개 중 1개를 뽑는 경우의 수는 i개 arr[i][0] = 1 -> i 개 중 1개도 선택하지 않는 경우의 수는 1개 arr[i][i] = i -> i 개 중 i 개를 선택하는 경우의 수는 1개이다. 점화식으로 DP 배열의 값을 채운다. arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1] 마지막으로 arr [n][k] 값을 출력한다.

정확한 풀이

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

public class Baek11050 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] arr = new int[n + 1][n + 1];
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1; // i 개에서 1개도 선택하지 않는 경우의 수는 0개 
			arr[i][i] = 1; // i 개에서 모두 선택하는 경우의 수는 1개 
			arr[i][1] = i; // i 개에서 1개 선택 경우의 수는 i개 
		}
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j < i; j++) { // 고르는 수의 개수가 전체 개수를 넘을 수 없음 
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; // 조합 점화식 
			}
		}
		System.out.println(arr[n][k]);
	}
}

내가 떠올린 풀이 해설

바로 앞에 문제와 비슷한 문제이다 n의 값이 커지고 결괏값을 10,007로 나눈 나머지를 출력하라는 요구사항이 있다. 모듈러 연산의 특성을 이용해 문제를 풀었다. 모듈러 연산은 덧셈에 관해 위와 같이 각각 모듈러를 하고, 모듈러 연산을 수행한 것과 두 수를 더한 후 수행한 것의 값이 동일하므로 이 문제에서 arr배열에 결괏값이 나올 때마다 모듈러 연산을 수행하는 로직을 추가하면 문제를 해결할 수 있다.

모듈러 연산의 특성

(A mod N + B mod N) mod N = (A + B) mod N

정확한 풀이

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

public class Baek11051 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] arr = new int[n + 1][n + 1];
		int pow = 10007;
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1;
			arr[i][i] = 1;
			arr[i][1] = i;
		}
		for(int i = 2; i <= n; i++) {
			for(int j = 1; j < i; j++) {
				arr[i][j] = (arr[i - 1][j - 1] + arr[i -1][j]) % pow;
			}
		}
		System.out.println(arr[n][k]);
	}
}

오늘의 회고

오늘은 DP 문제를 풀기 위해 먼저 학습해야 되는 조합에 대해서 학습하고 조합에 관련된 기본 문제 2문제를 풀었습니다. DP가 알고리즘 문제 풀이에서 2번째로 중요하다고 들었습니다. 매번 출제되는 문제인 만큼 확실하게 학습하고 넘어가겠습니다.

최소 신장 트리

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

최소 신장 트리의 특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 수는 항상 N - 1개다.

최소 신장 트리 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

   최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.

2. 그래프 데이터를 가중치 기준으로 정렬하기

   에지 리스트의 담긴 그래프를 데이터를 가중치 기준으로 오름차순 정렬한다.

3. 가중치가 낮은 에지부터 연결 시도하기

   가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.

4. 과정 3 반복하기

   전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복한다.

5. 총 에지 비용 출력하기

   에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다. 최소 신장 트리는 다른 그래프 알고리즘과 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 된다.

코드로 표현

static int[] parent;
static PriorityQueue<pEdge> que;

노드 수, 에지 수 입력
que = new PriorityQueue<>();  // 자동 정렬을 위해 우선순위 큐 자료구조 선택하기

parent = new int[n + 1];
parent배열 인덱스로 초기화

for(int i = 0; i < M; i++) {
	시작 노드 s, 끝 노드 e, 가중치 입력받기 v
    que.add(new pEdge(s,e, v));
}
int useEdge = 0;
int result = 0;
while(useEdge < N - 1) {
	pEdge now = que.poll();
    if(find(now.s) != find(now.e)) {  // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음
    	union(now.s, now.e);
        result = result + now.v;
        useEdge++;
    }
}
Union 연산 : 대표 노드끼리 연결하기
a = find(a);
b = find(b);
if(a != b) {
	parent[b] = a;
}
Find 연산
if(a == parent[a]) {
	return a;
}
else {
	return parent[a] = find(parent[a]); // 경로압축
}

class pEdge implements Comparable<pEdge> {
	int s;
    int e;
    int v;
    pEdge(int s, int e, int v) {
    	this.s = s;
        this.e = e;
        this.v = v;
    }
    @Override
    public int compareTo(pEdge o) {
    	// 가중치를 기준으로 오름차순 정렬을 하기 위해 compareTo 재정의하기
    	return this.v - o.v;
    }
}

플로이드-위셜

그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 음수 가중치가 있어도 수행할 수 있고, 동적 계획법의 원리를 이용해 알고리즘에 접근한다.

시간 복잡도(노드수 : V)

O(V^3)

플로이드-위셜 핵심 이론

플로이드-위셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

플로이드 위셜 점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

1. 배열을 선언하고 초기화하기

D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열이라 정의한다. S와 E의 값이 같은 같은 0, 다른 칸은 무한으로 초기화한다. 여기에서 S==E 는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.

2. 최단 거리 배열에 그래프 데이터 저장하기

출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 배열에 입력한다. 이로써 플로이드-위셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.

3. 점화식으로 배열 업데이트하기

기존에 구했던 점화식을 3중 for문 형태로 반복하면서 배열의 값을 업데이트한다.

플로이드-위셜 알고리즘 로직

for 경유지 K에 관해 (1 ~ N)

   for 출발 노드 S에 관해 (1 ~ N)

      for 도착 노드 E에 관해 (1 ~ N)

        D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 

플로이드-위셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 빠르지 않은 편이다. 플로이드-위셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드의 개수의 범위가 다른 그래프에 적게 나타난다는 것을 알 수 있다.

코드로 표현

static int N,M;
static int distance[][];

distance = new int[n + 1][n + 1];

for(int i = 1; i <= N; i++) { // 인접 행렬 초기화
	for(int j = 1; j <= N; j++) {
    	if(i == j) {
        	distance[i][j] = 0;
        }
        else {
        	distance[i][j] = 1000001; // 충분히 큰 수로 저장
        }
    }
}
for(int i = 0; i < M; i++) {
	int s, e, v 입력받기
    if(distance[s][e] > v) {
    	distance[s][e] = v;
    }
}
for(int k = 1; k <= N; k++) { // 플로이드-위셜 알고리즘 수행하기
	for(int i = 1; i <= N; i++) {
    	for(int j = 1; j <= N; j++) {
        	if(distance[i][j] > distance[i][k] + distance[k][j])
            	distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}
출력 부분