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

오늘은 자바 최상위 클래스 Object 클래스의 equals 메소드에 대해서 알아보겠습니다.


equals 메소드

 Object 클래스에는 다음과 같이 equals 메소드가 정의되어있습니다.

public boolean equals(Object obj)

 메소드 이름 그대로 같은지 다른지 판단해서 boolean 값을 return 해주는 메소드로, 오버라이딩을 통해 원하는 내용 비교를 할 수 있도록 최상위 클래스인 Object 클래스에 정의되어 있습니다.

 

 우리가 비교를 생각하면 "==" 연산이 가장 먼저 떠오릅니다. 하지만, "==" 연산은 참조대상이 같은지, 다른지 판단해주는 연산으로 우리가 원하는 내용 비교와는 조금 다릅니다.

 같은 문자열을 담고 있는 2개의 String 인스턴스를 생성해 보도록 하겠습니다.

public class test{
	public static void main(String args[]) {
		String name1 = new String("travelbeeee");
		String name2 = new String("travelbeeee");
		if(name1 == name2) System.out.println("둘이 같습니다");
		else System.out.println("둘이 다릅니다");
	}
}

 name1, name2 인스턴스에는 분명히 같은 문자열이 저장되어있지만, 각각 인스턴스를 생성했기 때문에 서로 다른 인스턴스를 참조하고 있습니다. 따라서, "==" 연산의 결과는 둘이 다르다고 판단합니다.

[Output]
둘이 다릅니다

 그럼 내용 비교를 하고 싶으면 어떻게 해야 될까요? 그럴 때 equals 메소드를 오버라이딩해서 사용하면 됩니다. String 클래스에서는 이미 equals 메소드를 오버라이딩해서 지원해주고 있기 때문에, 다음과 같이 사용하면 됩니다.

public class test{
	public static void main(String args[]) {
		String name1 = new String("travelbeeee");
		String name2 = new String("travelbeeee");
		if(name1.equals(name2)) System.out.println("둘이 내용이 같습니다");
		else System.out.println("둘이 내용이 다릅니다");
	}
}
[Output]
둘이 내용이 같습니다

 x좌표와 y좌표를 담고 있는 클래스를 만든 후, equals 메소드를 좌표가 같은지 판단해주도록 오버라이딩 해보겠습니다.

class Point{
	private int xPos;
	private int yPos;
	public Point(int x, int y) {
		xPos = x;
		yPos = y;
	}
	@Override
	public boolean equals(Object obj) {
		if(((Point)obj).xPos == xPos && ((Point)obj).yPos == yPos) return true;
		return false;
	}
}

public class test{
	public static void main(String args[]) {
		Point p1 = new Point(5, 7);
		Point p2 = new Point(5, 7);
		if(p1 == p2)
			System.out.println("참조대상이 같다");
		else
			System.out.println("참조대상이 다르다");
		
		if(p1.equals(p2))
			System.out.println("내용이 같다");
		else
			System.out.println("내용이 다르다");
	}
}
[Output]
참조대상이 다르다
내용이 같다

 "==" 연산 결과는 서로 다른 인스턴스를 참조하고 있다고 알려주고 있지만, equals 메소드를 둘의 좌표를 비교하도록 오버라이딩 했기 때문에 내용이 같다고 비교해주고 있는 것을 볼 수 있습니다.

 

 이렇듯 두 인스턴스의 내용 비교 결과인 true, false 의 반환 조건은 해당 클래스를 정의하는 프로그래머가 결정해야 합니다. 기본적으로 Object 클래스의 equals 메소드는 "==" 연산자와 마찬가지로 참조변수의 참조 값을 비교하도록 정의되어 있습니다. 하지만, "==" 연산이 참조변수의 참조 값을 비교하는 기능을 지원해주므로 String 클래스 등과 같이 자바에서 제공하는 표준 클래스의 경우 equals 메소드가 내용 비교를 하도록 이미 오버라이딩 되어 있는 경우가 많습니다.


 

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


Graph BFS

 a 동영상과 b 동영상의 relevant 값은 a에서 b로 가는 경로 중 간선의 값이 가장 작은 값이 됩니다. 우리는 k와 v가 주어질 때마다, v번 동영상에서 다른 모든 동영상까지 relevant 값이 k 이상인 동영상들을 count 해줘야합니다. 따라서, a 동영상에서 시작해서 BFS 탐색을 진행하면서 다른 모든 동영상과의 relevant 값을 구하면 되는데, a에서 어떤 동영상까지 탐색하는데 relevant 값이 주어진 k보다 작아진다면, 그 뒤의 탐색들도 다 k보다 relevant 값이 작아지므로 탐색을 마저 진행하지 않는다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int N, Q, p, q, r, k, v;
vector<pair<int, int>> map[5001];

int BFS(int k, int v) {
	int ans = 0;
	vector<bool> visited(5001, false);
	queue<int> q;
	q.push(v);
	visited[v] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			int relev = map[cur][i].second;
			if (!visited[next] && k <= relev) {
				visited[next] = 1;
				q.push(next);
				ans++;
			}
		}
	}
	return ans;
}

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

	cin >> N >> Q;
	for (int i = 0; i < N - 1; i++) {
		cin >> p >> q >> r;
		map[p].push_back({ q, r });
		map[q].push_back({ p, r });
	}
	for (int i = 0; i < Q; i++) {
		cin >> k >> v;
		cout << BFS(k, v) << '\n';
	}

	return 0;
}

 

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 15681 : 트리와 쿼리  (0) 2020.07.01
[BOJ] 18235 : 지금 만나러 갑니다  (0) 2020.06.25
[BOJ] 10021 : Watering the Fields  (0) 2020.06.22
[BOJ] 2352 : 반도체 설계  (0) 2020.06.15
[BOJ] 1162 : Revamping Trails  (0) 2020.06.09

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


MST Graph Prim

 N개의 노드가 존재하고, a 노드에서 b 노드로 가는 간선이 존재하려면, 거리가 C 이상이여야 됩니다. 우리는 모든 노드들이 서로 연결되어있는 상태를 최소 비용으로 만들고 싶으므로, MST를 만들면 됩니다.

 MST 알고리즘은 대표적으로 Prim, Kruskal 2개가 있는데 이 문제는 간선이 굉장히 많이 존재할 수 있는 밀집 그래프 문제이므로 Kruskal로 MST를 구하면 시간초과를 직면하게 되고, Prim 알고리즘을 사용해야된다.

 

1) 모든 노드를 순회하며 거리를 계산하고, 거리가 C 이상이면 graph 에 간선을 만들어준다.

( 간선은 양방향 )

2) Prim 알고리즘을 통해 MST를 구한다.

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

const int INF = 1000000001;

int N, C;
int graph[2000][2000];
pair<int, int> point[2000];
int dist[2000];
bool selected[2000];

int getDist(int i, int j) {
	return (int)pow(point[i].first - point[j].first, 2) + (int)pow(point[i].second - point[j].second, 2);
}

int get_min_vertex() {
	int v;
	for (int i = 0; i < N; i++) {
		if (!selected[i]) {
			v = i;
			break;
		}
	}
	for (int i = 0; i < N; i++)
		if (!selected[i] && (dist[i] < dist[v])) v = i;
	return v;
}

int prim(int s) {
	for (int i = 0; i < N; i++)
		dist[i] = INF;
	dist[s] = 0;
	for (int i = 0; i < N; i++) {
		int u = get_min_vertex();
		selected[u] = 1;
		if (dist[u] == INF) return -1;
		for (int j = 0; j < N; j++)
			if (graph[u][j] != INF && !selected[j] && graph[u][j] < dist[j])
				dist[j] = graph[u][j];
	}
    int ans = 0;
    for(int i = 0; i < N; i++) ans += dist[i];
    return ans;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	// i <--> j 의 모든 edge를 구하고, MST를 구하면 된다.
	cin >> N >> C;
	for (int i = 0; i < N; i++)
		cin >> point[i].first >> point[i].second;

	// 프림으로 해보자.
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++) {
			int dist = getDist(i, j);
			if (C <= dist) graph[i][j] = graph[j][i] = dist;
			else graph[i][j] = graph[j][i] = INF;
		}
    cout << prim(0) << '\n';
    
	return 0;
	
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 18235 : 지금 만나러 갑니다  (0) 2020.06.25
[BOJ]15591 : MooTube(Silver)  (0) 2020.06.22
[BOJ] 2352 : 반도체 설계  (0) 2020.06.15
[BOJ] 1162 : Revamping Trails  (0) 2020.06.09
[BOJ] 1086 : 박성원  (0) 2020.06.02

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

오늘은 자바 가상 머신의 메모리 모델에 대해서 포스팅 해보겠습니다.


자바 메모리 모델

 자바 가상머신은 운영체제 위에서 실행되는 하나의 프로그램이고, 자바 프로그램은 자바 가상머신 위에서 실행되는 프로그램입니다. 따라서, 자바 가상 머신은 운영체제한테 할당 받은 메모리를 사용해 자바 프로그램이 실행합니다.

 자바 가상 머신은 효율적으로 할당받은 메모리를 사용하기 위해 3개의 영역으로 나눠서 관리합니다.

  메소드 영역, 스택영역, 힙 영역으로 나눠서 데이터를 보관합니다.

1) 메소드영역

 메소드 영역은 메소드의 바이트 코드, static 변수가 저장되는 영역입니다.

 소스파일을 컴파일할 때, 자바 가상머신에 의해 실행이 가능한 코드를 가리켜 '바이트 코드'라고 합니다. 쉽게 말하면 메소드 영역은 특정 클래스의 정보가 담겨있는 영역입니다.

 우리가 인스턴스를 생성하려면 먼저 클래스에 대한 정보가 메모리에 로딩되어있어야 합니다. 이를 클래스의 바이트 코드라고 합니다. 

package Hello;

import java.io.IOException;

class memoryEX{
	static int ex1 = 0;
}

public class test{
	public static void main(String args[]) {
		memoryEX.ex1++;
		new memoryEX();
	}
}

 memoryEX의 static 변수를 참조하고, 인스턴스를 생성하는 코드입니다. 메소드 영역에 memoryEX 클래스에 대한 정보가 로딩되어있기 때문에, 우리가 static 변수를 참조하고, 인스턴스를 생성할 수 있는 것 입니다.

2) 스택 영역

 스택 영역은 지역 변수와 매개 변수가 저장되는 공간입니다. 지역 변수와 매개 변수는 모두 "중괄호로 구분되는 지역 내에서만 유효한 변수들" 입니다. 즉, 중괄호 내에 할당된 이후에 해당 중괄호를 벗어나면 소멸되는 특성의 데이터들이 저장되는 공간입니다.

 또, 스택 영역은 말 그대로 자료구조 스택을 이용해 메모리가 관리됩니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int num1 = 1;
		int num2 = 2;
	}
}

 위의 코드가 컴파일되면 먼저 args 변수가 스택 영역에 쌓이고, num1, num2 변수가 차례대로 스택 영역에 쌓이게 됩니다.

3) 힙 영역

 힙 영역은 인스턴스 정보가 저장되는 영역입니다. 인스턴스는 소멸 시점과 소멸 방법이 지역 변수와 다르기 때문에, 스택 영역과 구분해서 힙 영역에 저장이 됩니다.

 지역 변수와 매개 변수는 중괄호를 벗어나면 변수가 소멸된다고 했습니다. 그럼, 인스턴스는 언제 소멸될까요?? 인스턴스의 소멸시기는 가상머신이 결정합니다. 즉, 가상머신이 "이제 이 인스턴스를 소멸시켜야겠다" 라고 판단하면 인스턴스는 자동으로 소멸이 됩니다. 자바가 다른 프로그래밍 언어에 비해 '메모리 관리에 신경을 덜 써도 된다' 라는 평가를 받는 이유입니다.

 자바에서는 "가비지 컬렉션" 이라는 기능의 인스턴스 소멸 방식을 가지고 있는데, 가비지 컬렉션이 빈번하게 발생하면 시스템에 부담되기 때문에, 자바 가상 머신이 적절한 시기에 가비지 컬렉션을 실행합니다.


 

+ Recent posts