굳건하게

안녕하세요, 여행벌입니다.

오늘은 2진수 표기법의 특징을 활용한 비트마스킹 알고리즘에 대해서 포스팅해보겠습니다.

[ 비트마스킹 ]

 컴퓨터는 내부적으로 모든 자료를 이진수로 표현합니다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 합니다.

 비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있습니다.

비트 연산자

 비트마스킹은 기본적으로 비트를 다뤄야 하므로, 비트 연산자에 대해서 먼저 간단하게 알아보겠습니다.

집합의 표현

 비트마스크를 이용하면 집합을 쉽게 표현할 수 있습니다. 또, 집합에 원소를 추가, 삭제하는 등 다양한 연산을 굉장히 빠르게 수행할 수 있습니다.

 그럼 비트를 이용해서 어떻게 집합을 표현할 수 있을까요? 원소의 개수가 N인 집합이 있다고 하면, 각각의 원소를 0번부터 (N-1)번 까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현할 수 있습니다.

 예를 들어, { A, B, C, D, E, F, G } 집합이 있다고 하겠습니다.

총 7개의 원소가 존재하므로 우리는 7개의 비트로 이 집합을 표현할 수 있습니다. 즉, 각 원소마다 비트를 하나씩 대응시켜서 원소가 존재한다면 1, 존재하지 않다면 0으로 표현해보겠습니다.

예를 들어, { A } 라는 부분집합은 64 = 1000000(2) 로 표현하고 { C, F } 는 18 = 0010010(2) 로 표현할 것입니다.

원소 추가

 현재 상태 cur이 있을 때, p번 원소를 추가한다고 해보겠습니다. 그럼, 현재 상태 cur에서 p번 비트를 1로 바꿔줘야 됩니다. a | b 비트연산자를 활용하면 쉽게 해결할 수 있습니다.

cur = cur | (1 << p)

 1 << p를 통해서 p번 비트만 1, 나머지 비트는 0인 값을 만들고 | 연산을 진행한다면 cur의 p번 비트는 1로 바뀌게 되고, 나머지 비트는 원래 상태를 유지하게 됩니다.

원소 삭제

 원소를 삭제하는 연산도 쉽게 구현할 수 있습니다. 현재 상태 cur에서 p번 원소를 삭제한다고 생각해보겠습니다. 그러면, p번 비트를 0으로 바꿔줘야됩니다.

cur = cur & ~(1 << p);

 1 << p 를 통해서 p번 비트만 1, 나머지 비트는 0으로 만듭니다. 그 후, ~ 연산을 통해 p번 비트만 0, 나머지 비트는 1로 만들고 & 연산을 진행한다면 p번 비트만 0으로 바뀌고 나머지는 현재 상태 cur과 동일하게 유지할 수 있습니다.

원소 토글

 p번 비트가 1이면 0, 0이면 1로 바꾸는 토글 연산도 쉽게 구현할 수 있습니다. 현재 상태 cur에서 p번 원소가 있다면 삭제하고, 없다면 추가해보겠습니다.

cur = cur ^ (1 << p);

 1 << p 를 통해서 p번 비트만 1, 나머지 비트는 0으로 만듭니다. cur의 나머지 비트들은 0과 XOR 연산을 진행하므로 0이면 0, 1이면 1로 현재 상태를 유지하게 되고, p번 비트는 1과 XOR 연산을 진행하므로 1이면 0, 0이면 1로 토글이 됩니다.

집합 연산(합집합)

 비트마스킹을 이용하면 원소를 추가, 삭제, 토글 하는 연산 외에도 합집합, 교집합, 차집합 등등을 쉽게 구할 수 있습니다.

a | b; // a 와 b의 합집합
a & b; // a 와 b의 교집합
a & ~b; // a 에서 b를 뺀 차집합
a ^ b; // a와 b 중 하나에만 포함된 원소들의 집합

 A집합을 나타내는 a와 B집합을 나타내는 b가 있을 때, 둘이 | 연산을 하게 된다면 존재하는 원소들의 비트는 모두 1로 켜지게 되고, 두 집합에 모두 없는 원소들만 비트가 0이 됩니다. 따라서, 합집합 연산이 됩니다.

 마찬가지로 & 연산을 하게 되면, 두 집합에 모두 존재하는 원소들의 비트만 1과 1을 AND 연산하게 되므로 1로 살아남고, 나머지는 0이 됩니다. 따라서 교집합 연산이 됩니다.

 a & ~b 연산을 하게 되면 a 집합과 b의 여집합과 & 연산을 하게 됩니다. 즉, A - B 인 차집합 연산이 됩니다.

 마지막으로, ^ 연산을 하게 되면 둘 중 하나에만 포함된 원소들만 1로 살아남게 됩니다.

집합의 크기 구하기

 집합의 크기를 구하려면, 현재 1로 켜져 있는 비트의 수를 count 해야 됩니다. 따라서, 모든 비트를 순회해야 되고 재귀적으로 다음과 같이 구현할 수 있습니다.

int bitCount(int x){
	if(x == 0) return 0;
	return x % 2 + bitCount(x / 2);
}

 x % 2 를 하면 마지막 비트를 얻게 되고, x / 2 를 하게 되면 마지막 비트를 삭제할 수 있습니다. 따라서, 모든 비트를 재귀적으로 순회할 수 있습니다.

모든 부분 집합 순회하기

 어떤 집합의 모든 부분 집합을 순회하는 과정도 정말 간단하게 구현할 수 있습니다.

for(int subset = set; subset; subset = (subset - 1) & set){
	// subset은 set의 부분집합 중 하나.
}

 예를 들어, { A, B, D } 를 포함한 집합을 생각해보겠습니다.

 모든 부분 집합은 공집합을 제외하고 { A }, { B }, { D }, { A, B }, { A, D }, { B, D }, { A, B, D } 가 존재합니다.

 비트로 표현하면 다음과 같습니다.

 위에서 구현한 코드를 한 번 따라가 보겠습니다. set = 1101(2) = { A, B, D } 입니다.

 for문을 통해 모든 부분 집합을 다 순회하는 것을 확인할 수 있습니다.

 위처럼 비트마스크를 이용하면 집합의 표현, 원소 추가, 원소 삭제, 원소 토글, 합집합, 교집합, 차집합 등등 다양한 연산들을 어떤 자료구조보다 빠르게 구현할 수 있습니다.

안녕하세요, 여행벌입니다.

오늘은 저번 포스팅 상속에 이어서 오버라이딩에 대해서 포스팅해보겠습니다.

메소드 오버라이딩(Overriding)

메소드 오버라이딩은 상위 클래스에 정의된 메소드를 하위 클래스에서 다시 정의하는 것을 뜻합니다.

 오버라이딩을 위해서는 메소드의 이름, 메소드의 반환형, 메소드의 매개변수 선언이 모두 같아야 합니다. 메소드 오버라이딩이 발생하면 자바는 상위 클래스의 메소드를 무효화시키고, 하위 클래스의 메소드를 살려둡니다.

 예시를 통해서 익혀보겠습니다.

package Hello;

class supClass{
	public supClass() {}; //생성자
	void sayHello() {
		System.out.println("supClass Hello");
	}
}

class subClass extends supClass{
	public subClass() {}; // 생성자
	void sayHello() {
		System.out.println("subClass Hello!!");
	}
}

public class test{
	public static void main(String args[]) {
		// supClass 참조변수가 supClass 인스턴스 --> 오버라이딩 X
		supClass class1 = new supClass();
		class1.sayHello();
		
		// supClass 참조변수가 subCLass 인스턴스 --> 오버라이딩 O
		supClass class2 = new subClass();
		class2.sayHello();
		
		// subClass 참조변수가 subClass 인스턴스 --> 오버라이딩 O
		subClass class3 = new subClass();
		class3.sayHello();
	}
}

 상위 클래스와 그 클래스를 상속하는 하위 클래스를 만들었습니다. 하지만, 상위 클래스와 하위 클래스에  반환형 / 메소드의 이름 / 메소드의 매개 변수가 모두 같은 sayHello 라는 메소드가 존재합니다. 

 저번 포스팅에서 상속을 진행하면 상위 클래스의 변수, 메소드가 모두 하위 클래스에게 전달된다고 얘기했습니다. 따라서, 같은 메소드가 동시에 2개 존재하는 상황이 발생합니다. 이때, 자바에서는 메소드 오버라이딩을 통해 상위 클래스의 메소드를 무효화시키고, 하위 클래스의 메소드만 남겨둡니다.

[Output]
supClass Hello
subClass Hello!!
subClass Hello!!

 그럼, 상위 클래스 메소드를 하위 클래스에서 사용하고 싶다면 어떻게 해야될까요? super 키워드를 이용하면 사용할 수 있습니다.

package Hello;

class supClass{
	public supClass() {}; //생성자
	void sayHello() {
		System.out.println("supClass Hello");
	}
}

class subClass extends supClass{
	public subClass() {}; // 생성자
	void sayHello() {
		super.sayHello();
		System.out.println("subClass Hello!!");
	}
}

public class test{
	public static void main(String args[]) {
		// subClass 참조변수가 subClass 인스턴스 --> 오버라이딩 O
		subClass class1 = new subClass();
		class1.sayHello();
	}
}

 다음과 같이 super 키워드를 이용하면 상위 클래스의 메소드 또한 이용할 수 있습니다.

인스턴스 변수, 클래스 변수, 클래스 메소드의 오버 라이딩

 그럼 인스턴스 메소드가 아닌 인스턴스 변수와 클래스 변수, 클래스 메소드도 오버 라이딩이 될까요?? 결론부터 얘기하면 오버라이딩 대상이 아닙니다.

 자바는 '참조변수의 형' 에 따라서 접근하는 변수가 결정되므로 클래스 변수, 클래스 메소드, 인스턴스 변수는 오버라이딩 되지 않습니다.

package Hello;

class supClass{
	int a = 1;
	static int b = 2;
	static void sayBye() {
		System.out.println("supClass Bye!!");
	}
	public supClass() {}; //생성자
	void sayHello() {
		System.out.println("supClass Hello");
	}
}

class subClass extends supClass{
	int a = -1;
	static int b = -2;
	static void sayBye() {
		System.out.println("subClass Bye!!");
	}
	
	public subClass() {}; // 생성자
	void sayHello() {
		super.sayHello();
		System.out.println("subClass Hello!!");
	}
}

public class test{
	public static void main(String args[]) {
		//supClass 참조변수가 supClass 인스턴스 참조
		supClass class1 = new supClass();
		System.out.println(class1.a + " " +  class1.b);
		class1.sayBye();
		
		// supClass 참조변수가 subClass 인스턴스 참조
		// 인스턴스 메소드였으면 원래 오버라이딩 되는 상황
		supClass class2 = new subClass();
		System.out.println(class2.a + " " + class2.b);
		class2.sayBye();
	}
}

 동일한 이름의 인스턴스 변수(a), 클래스 변수(b), 클래스 메소드(sayBye) 를 상위 클래스와 하위 클래스에서 모두 선언했습니다. 하지만, 오버라이딩 대상이 아니므로 결과는 다음과 같이 참조변수의 형에 따라서 supClass의 인스턴스 변수, 클래스 변수, 클래스 메소드를 참조하는 것을 알 수 있습니다.

[Output]
1 2
supClass Bye!!
1 2
supClass Bye!!

클래스와 메소드의 final 선언

 클래스와 메소드에 final 선언을 추가하면 해당 클래스 혹은 해당 메소드를 다른 클래스가 상속, 오버라이딩 하지 못하게 막을 수 있습니다. 대표적인 final 클래스로 String 클래스가 있습니다. 따라서, 우리는 String 클래스를 상속할 수 없습니다.

final class myClass { } // 다른 클래스가 상속할 수 없는 클래스

class myClass2{
	final void func(){ } // 메소드 오버라이딩을 할 수 없는 메소드
}

@Override

 자바 5에서 '어노테이션' 이 소개되었습니다. 그 중, 메소드 오버라이딩과 관련된 @Override 어노테이션에 대해서 알아보겠습니다.

 우리는 메소드 오버라이딩을 의도하고 코드를 구현했지만, 개발자의 실수로 오버라이딩 조건을 만족하지 못해서 오버라이딩이 진행되지 않는 상황이 발생할 수 있습니다.

package Hello;

class supClass{
	public supClass() {}; //생성자
	void add(int a, int b) {
		System.out.println(a + b);
	}
}

class subClass extends supClass{
	public subClass() {}; // 생성자
	// 메소드 오버라이딩
	void add(double a, double b) {
		System.out.println(a + b);
	}
	
}

public class test{
	public static void main(String args[]) {
		subClass class1 = new subClass();
		class1.add(5, 7);
	}
}

subClass 에서 supClass의 add 메소드를 오버라이딩 하려고 하였으나, 매개변수형이 int 형이 아닌 double 형이라 오버라이딩이 발생하지 않은 상황입니다. 이런 상황을 @Override 어노테이션을 통해서 해결할 수 있습니다.

class supClass{
	public supClass() {}; //생성자
	void add(int a, int b) {
		System.out.println(a + b);
	}
}

class subClass extends supClass{
	public subClass() {}; // 생성자
	// 메소드 오버라이딩
	@Override
	void add(double a, double b) {
		System.out.println(a + b);
	}
}

 @Override 어노테이션을 사용하면 자바 컴파일러에게 메시지를 전달할 수 있습니다. 즉, 나는 메소드 오버라이딩을 하고 싶어요! 라고 자바 컴파일러에게 전달하는 메시지입니다. 따라서, @Override 어노테이션을 오버라이딩을 원하는 메소드 위에 선언하면 반환형, 메소드의 이름, 매개 변수가 모두 같은 오버라이딩 가능한 메소드가 없다면 자바 컴파일러가 코드가 잘못 구현되었다고 알려줍니다.

문제 : https://www.acmicpc.net/problem/2352

DP LIS BinarySearch

 가장 긴 증가 부분 수열을 구하는 문제로 DP를 이용해 해결할 수 있는데, DP 배열을 BinarySearch를 이용해 채워야한다.

Dp[ x ] := 길이가 x 인 증가 부분 수열 중 가장 작은 마지막 값

ex )

[ 4 2 6 3 1 5 ] 에서 길이가 2인 증가 부분 수열은 4 - 6 / 4 - 5 / 2 - 6 / 2 - 3 / 2 - 5 / 3 - 5 / 1 - 5 처럼 여러가지가 있지만, 이 중 가장 작은 마지막 값은 3이므로 Dp[2] = 3 이 된다.

지금까지 우리가 구한 가장 긴 증가 수열의 길이가 longest 라고 한다면, 우리가 지금 보고 있는 i번 째 값이 Dp[longest] 보다 크다면, 지금까지 구한 longest 길이의 수열의 뒤에 i번 째 값을 이으면 되므로 Dp[longest + 1] 을 갱신할 수 있다. 아니라면, 현재 값을 Dp[ k - 1] < i번 째 값 <= Dp[ k ] 인 곳을 찾아서 갱신하면 된다.(지금까지 구한 부분 증가 수열 중에서 맨 뒤에 값을 이을 수 있는 곳) 이때, Binary Search를 이용해야 시간초과를 해결할 수 있다. 또, 초기값으로 Dp[0] = -INF 로 설정하면 더 간편하게 구할 수 있다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	const int INF = 99999;
	int N;
	cin >> N;

	vector<int> v(N), dp(N + 1, INF);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	// dp[i] := 길이가 i인 증가수열들 중에서 마지막 값 중 최소.
	dp[0] = -INF;
	dp[1] = v[0];
	int longest = 1;
	for (int cur : v) {
		if (dp[longest] < cur) {
			longest++;
			dp[longest] = cur;
		}
		else {
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), cur);
			*it = cur;
		}
	}
	int ans = 1;
	for (int i = 1; i <= N; i++)
		if (dp[i] != INF) ans = i;
	cout << ans << '\n';
	return 0;
}

안녕하세요, 여행벌입니다.

오늘은 객체지향 언어인 자바의 중요한 문법, 상속에 대해서 포스팅해보겠습니다.

상속(Inheritance) 의 객체지향적 역할

"상속이란 연관된 일련의 클래스들에 대해 공통적인 규약을 정의해준다."

 상속이란 문법의 가장 큰 역할은 위와 같습니다. 그럼 어떻게 상속을 사용하고, 상속의 특징으로는 어떤 특징들이 있는지 알아보겠습니다.

상속(Inheritance) 이란

 상속은 쉽게 얘기하면 이미 기존에 정의된 클래스에 메소드와 변수를 추가하여 새로운 클래스를 정의하는 것을 의미합니다. 즉, 이미 만들어진 클래스에 우리가 원하는 기능과 데이터를 추가해서 새로운 클래스를 만드는 행위입니다.

 extends 키워드를 이용해 상속을 활용할 수 있습니다.

 그럼, 간단하게 이름을 가지고 있는 사람이라는 클래스에 핸드폰 번호도 추가해서 새롭게 클래스를 만들어보겠습니다.

class people{
	String name;
    void tellYourName(){}
}

class richPeople extends people{
	String phoneNum;
    void tellYourPhontNum(){}
}

 people이라는 클래스를 extends 상속해서 richPeople이라는 새로운 클래스를 만들었습니다.

그럼, richPeople 이라는 새로운 클래스는 people 클래스에 있는 변수와 메소드를 가져와 사용할 수 있습니다. 즉, richPeople이라는 클래스는 실제로 아래 그림과 같습니다.

이처럼

● 상속을 하는 클래스를 하위 클래스, 자식 클래스

● 상속을 당하는 클래스를 상위 클래스, 부모클래스  라고 부릅니다.  

상속(Inheritance) 과 생성자

 모든 클래스는 생성자 메소드가 존재한다고 앞의 포스팅에서 얘기했습니다. 그러면, 상속 관계에서는 생성자 호출이 어떤 식으로 진행될까요??

 다음 예제를 통해서 하위 클래스 인스턴스를 생성하면 생성자 호출이 어떻게 진행되는지 보겠습니다.

package Hello;

class people{
	String name;
	public people() {
		System.out.println("상위클래스생성사호출");
	}
}

class richPeople extends people{
	String phoneNum;
	public richPeople() {
		System.out.println("하위클래스생성자호출");
	}
}

public class test{
	public static void main(String args[]) {
		new richPeople();
	}
}

[Output]
상위클래스생성사호출
하위클래스생성자호출

 예시를 통해 아래와 같은 두 가지 사실을 알 수 있습니다.

● 하위 클래스의 인스턴스 생성 시 상위 클래스, 하위 클래스의 생성자가 모두 호출된다.

● 하위 클래스의 인스턴스 생성 시 상위 클래스의 생성자가 먼저 호출된다.

 즉, 하위 클래스의 인스턴스를 생성할 때 상위 클래스의 생성자를 먼저 호출해줘야 한다는 것을 알 수 있습니다. 따라서, 다음과 같이 클래스의 생성자를 구현할 수 있습니다.

package Hello;

class people{
	String name;
	public people(String name) {
		this.name = name;
	}
}

class richPeople extends people{
	String phoneNum;
	public richPeople(String name, String phoneNum) {
		super(name);
		this.phoneNum = phoneNum;
	}
}

public class test{
	public static void main(String args[]) {
		new richPeople();
	}
}

키워드 super 를 이용하면 '상위 클래스의 생성자 호출' 을 할 수 있습니다.

클래스 변수, 클래스 메소드의 상속

 static 선언이 붙는 클래스 변수와 클래스 메소드는 인스턴스 생성과 상관 없이 유일하게 존재한다고 앞에서 배웠습니다. 따라서, 클래스 변수와 클래스 메소드는 상속의 대상이 아닙니다. 그러면, 상위클래스의 클래스 변수와 클래스 메소드는 하위 클래스에서 이용할 수 있을까요?? 

 접근 수준 지시자가 접근을 허용하면 하위 클래스에서도 상위 클래스의 클래스 변수와 클래스 메소드에 접근이 가능합니다.

package Hello;

class people{
	// 클래스 변수와 메소드
	static int num = 9999;
	static void showNum() {
		System.out.println(num);
	}
	
	String name;
	public people(String name) {
		this.name = name;
	}
}

class richPeople extends people{
	String phoneNum;
	public richPeople(String name, String phoneNum) {
		super(name);
		this.phoneNum = phoneNum;
	}
}

public class test{
	public static void main(String args[]) {
		richPeople ex1 = new richPeople("travlebeee", "010-0000-0000");
		ex1.showNum();
		ex1.num++;
		ex1.showNum();
	}
}

[Output]
9999
10000

 private 접근 수준 지시자로 선언이 되어있다면, 하위 클래스에서 접근할 수 없지만 다른 접근 수준 지시자들은 접근이 가능합니다.

상속과 참조변수

 하위 클래스는 상위 클래스의 특징을 다 가지고 있다고 했습니다. 그러면, 하위 클래스의 참조 변수로 상위 클래스를 참조하거나 상위 클래스의 참조 변수로 하위 클래스를 참조하는 게 가능할까요??

 예시를 통해서 자세히 알아보겠습니다.

class people{
	String name;
	public people(String name) {
		this.name = name;
	}
	
	void showYourName() {
		System.out.println("내이름은 : " + name);
	}
}

class richPeople extends people{
	String phoneNum;
	public richPeople(String name, String phoneNum) {
		super(name);
		this.phoneNum = phoneNum;
	}
	void showYourPhone() {
		System.out.println("내 번호는 : " + phoneNum);
	}
}

 위와 마찬가지로 people 클래스를 richPeople이 상속하고 있는 경우입니다.

 먼저, 상위 클래스의 참조 변수로 하위 클래스를 참조해보겠습니다.

public class test{
	public static void main(String args[]) {
		// 상위 클래스 참조 변수로 하위 클래스 참조
		people p1 = new richPeople("travelbeeee", "010-0000-0000");
		p1.showYourName(); // 가능
		p1.showYourPhone(); // 불가능
	}
}

 richPeople은 people 클래스의 자식이기 때문에, 상위 클래스의 참조 변수로도 하위 클래스의 인스턴스를 참조할 수 있습니다. 하지만, 자바는 참조 변수를 기준으로 판단하기 때문에, people 클래스의 참조 변수 p1은 people 클래스의 메소드인 showYourName() 메소드는 호출이 가능하나 showYourPhone() 메소드는 호출이 불가능합니다.

 반대 상황도 보겠습니다.

public class test{
	public static void main(String args[]) {
		// 하위 클래스 참조 변수로 상위 클래스 참조
		richPeople p1 = new people("travelbeeee"); // 불가능
	}
}

 이번에는 하위 클래스 참조 변수로 상위 클래스를 참조하고 있기 때문에, 애초에 참조가 불가능합니다.

 상위 클래스가 부모이므로 부모가 자식을 참조할 수는 있으나 하위 클래스인 자식이 부모를 참조할 수는 없다! 라고 외우시면 편할 것 같습니다.

이상으로, 상속에 대한 기본 정리를 마무리해보겠습니다.

다음 포스팅에서는 메소드 오버라이딩을 추가로 정리해보도록 하겠습니다.