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

 오늘은 가장 많이 사용하는 자료구조인 배열을 생성하는 방법, 데이터를 저장 및 참조하는 방법, 특성에 대해서 알아보겠습니다.


배열 (Array)

 배열은 '자료형이 같은 둘 이상의 값'을 저장할 수 있는 메모리 공간을 의미합니다.

, 자료형이 같은 여러 가지 값들을 모아서 저장할 때 사용하는 자료구조입니다.

 

 자바에서의 배열은 클래스로 정의되어있으므로, 우리는 인스턴스를 생성해서 배열을 이용할 수 있습니다. 또, length 라는 인스턴스 변수를 지원해줘서 배열의 길이도 쉽게 알 수 있습니다.

배열의 선언 및 초기화

자료형[ ] 변수명 = new 자료형[크기];    // 더 선호하는 방식
자료형 변수명[ ] = new 자료형[크기];
package Hello;

public class test{
	public static void main(String args[]) {
		int[] list = new int[5];
		int list2[] = new int[5];
	}
}

  두 가지 방법으로 선언할 수 있고, list과 list2 모두 자료형 int 를 5개 저장할 수 있는 배열을 선언했습니다. 배열의 길이는 고정되어 있으므로, 처음에 선언할 때 배열의 크기를 자바에게 알려줘야 됩니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int[] list = new int[] {1,2,3,4,5};
		int[] list2 = {1,2,3,4,5};
	}
}

 배열을 선언과 동시에 초기화할 수도 있습니다.

 위와 같이 배열을 선언하면서 동시에 초기화할 수 있습니다. 자바에서 배열의 크기를 5로 자동으로 인식하므로 크기를 전달하지 않아도 문제가 없습니다.

배열의 값 저장, 참조

  그럼 이렇게 선언한 배열에 값을 저장하거나 참조하려면 어떻게 해야 될까요?

 

 배열은 인덱스를 이용해서 참조할 수 있고, 인덱스는 0번 부터 시작합니다!

 

 즉, 5개를 저장할 수 있는 배열을 선언하면 5개의 메모리 공간이 생기고 인덱스로 참조할 수 있습니다. 이때, 인덱스는 0번부터 시작해 4번에서 끝이 납니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int[] list = new int[5];
		list[0] = 1;
		list[1] = 2;
		list[2] = 3;
		list[3] = 4;
		list[4] = 5;
	}
}

 크기가 5인 배열을 선언해 맨 앞부터 1, 2, 3, 4, 5를 저장했습니다.

 배열은 0번 인덱스부터 시작하므로, 다음과 같이 메모리 공간에 데이터들이 위치하고 있는 것을 예측할 수 있습니다.

 

 그러면, 2차원 혹은 3차원 배열은 어떻게 선언할까요? 1차원 배열과 크게 다르지 않습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int[][] list = new int[2][3];
	}
}

 2차원 배열은 위의 그림과 같이 2행 3열로 이루어졌습니다. 마찬가지로 데이터를 참조할 때는 인덱스를 이용해 다음과 같이 참조할 수 있습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int[][] list = new int[2][3];
		list[0][0] = 1;
		list[0][1] = 2;
		list[0][2] = 3;
		list[1][0] = 4;
		list[1][1] = 5;
		list[1][2] = 6;
	}
}

 자바는 다른 언어와 달리 다음과 같은 배열 특성을 가지고 있습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		int[][] list = { { 1, 2, 3}, { 4, 5}, {6} };
	}
}

 다음과 같이 2차원 배열을 선언하면 3행 3열의 배열이 선언될까요?? 아니면 채워지지 않은 공간은 메모리가 할당되지 않을까요??

 정답은 오른쪽 그림입니다!  자바는 배열의 가로길이가 행 별로 다른 2차원 배열을 생성할 수 있습니다. 즉, 초기화를 잘못하여 예상과는 다른 길이의 배열이 만들어지지 않도록 주의해야 합니다.

배열의 참조 값과 메소드

 위에서 우리는 배열 인스턴스를 생성해 사용한다고 말씀드렸습니다. 따라서, 당연히 메소드 호출 시 참조 값으로 배열을 전달할 수 있습니다. int 형 배열을 전달받아 합을 구하는 메소드를 만들어보겠습니다.

	int sumOfAry(int[] list) {
		int result = 0;
		for(int i = 0; i < list.length; i++)
			result += list[i];
		return result;
	}

 배열은 인스턴스 이므로 메소드 호출 시 전달할 수 있고, 자바에서 지원해주는 다양한 메소드에 인자로 전달해 다양한 기능을 사용할 수 있습니다.


 

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


다익스트라 그래프 그래프이론

 1번 노드에서 시작해서 N번 노드까지 가는 최단 거리를 찾는 문제인데, K개 만큼의 길을 이동 거리(cost)를 0으로 만들 수 있는 상황에서의 최단 거리를 찾는 문제입니다.

 출발 노드가 정해져있으므로 다익스트라 알고리즘을 이용하고 몇 개의 길을 cost를 0으로 만들었는지에 따라 최단거리가 달라지므로, dist배열을 2차원 배열로 다음과 같이 정의하면 된다.

 

  dist[M][K] := K개 만큼의 길을 0으로 만들어서 1번 정점에서 시작해서 M번 정점까지 이동한 최단 거리.

 

주의할 점 : 최단 거리가 int 형 범위를 벗어난다.

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const long long INF = 10000000001;
int N, M, K;
long long dist[10001][21];
vector<pair<int, int>> map[10001];

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

	cin >> N >> M >> K;
	for (int i = 0, x, y, z; i < M; i++) {
		cin >> x >> y >> z;
		map[x].push_back({ y, z });
		map[y].push_back({ x, z });
	}
	memset(dist, INF, sizeof(dist));
	priority_queue<pair<long long, pair<int, int>>> pq;
	pq.push({ 0, { 0, 1 } });
	for (int i = 0; i <= K; i++)
		dist[1][i] = 0;

	while (!pq.empty()) {
		long long cost = -pq.top().first;
		int road = pq.top().second.first;
		int cur = pq.top().second.second;
		pq.pop();
		if (dist[cur][road] < cost) continue;
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			long long nextDist = cost + map[cur][i].second;
			// 현재 정점
			if (nextDist < dist[next][road]) {
				dist[next][road] = nextDist;
				pq.push({ -nextDist, {road, next} });
			}
			// 포장하고 진행
			nextDist = cost;
			if (road < K && nextDist < dist[next][road + 1]) {
				dist[next][road + 1] = nextDist;
				pq.push({ -nextDist, {road + 1, next} });
			}
		}
	}
	cout << dist[N][K] << '\n';
	return 0;
}

 

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

[BOJ] 10021 : Watering the Fields  (0) 2020.06.22
[BOJ] 2352 : 반도체 설계  (0) 2020.06.15
[BOJ] 1086 : 박성원  (0) 2020.06.02
[BOJ] 7575 : 바이러스  (2) 2020.05.22
[BOJ] 11559 : Puyo Puyo  (0) 2020.05.21

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


DP Bitmasking 비트마스킹

● 최대 길이가 50인 N개의 정수들을 뽑는 경우는 N! 개가 존재한다. N이 최대 15이므로, N! 개를 모두 구하면 시간초과 발생 --> DP 로 문제를 접근

● DP[state][r] := 현재 어떤 정수들을 뽑았는지 state에 비트마스킹을 이용해 표시하고, r 은 K로 나눴을 때 나머지를 의미한다.

 즉, DP[state][r] := state 상태에서 K로 나눴을 때 나머지가 r인 경우의 수

 

DP 배열을 채우기 위해 다음과 같은 정의가 미리 필요하다.

● mul[i] := pow(10, i) % K 를 미리 다 저장해둔다. mod 연산이므로 쉽게 계산 가능

● integer[i] := ( N개의 정수 중 i번 째 정수 ) % K 를 mul[] 을 이용해 미리 계산해놓는다.

 

그럼 DP[ i ] [ j ] 는 다음과 같이 채울 수 있다.

 현재 상태 ( i ) 와 나머지 j 에 대해서 N개의 정수를 다 뒤에 붙여본다. 이때, 이미 현재 상태에서 뽑아서 사용한 정수는 붙여주지 않는다.

 따라서, N개의 정수 중 k 번 째 정수를 뽑았다고 가정하면, i & ( 1 << k ) == 0 이 성립하면 그 정수를 붙여주고, 아니면 이미 사용한 정수이므로 넘어간다.

 이때, 정수를 붙여준다는 것은 현재 상태에서의 나머지 j 를 k번 째 정수의 길이만큼 옆으로 밀어주고, k번 째 정수를 붙여주는 것이므로 j * 10^(k번 째 정수의 길이)를 해주면 되는데, 미리 계산해놓은 mul 배열을 이용해 연산해주고, 뒤에 k번 째 정수를 붙여주는 연산은 integer 배열을 이용하면 된다.

 예시를 통해 익혀보면 현재 "12345" 를 만들었고, "678" 을 붙여주는 연산을 생각해보면 "12345" * 1000 + "678" 을 생각하면 된다.

 이때, 정수론에 의해 ("12345" * 1000 + "678") mod K == ("12345" * 1000) mod K + "678" mod K 와 동일하고, 더 쪼개면 == ("12345" mod K) * (1000 mod K) + ("678" mod K) 로 분해할 수 있다. "12345" mod K 는 우리가 DP[i][j] 에서 j에 해당되는 값이고, (1000 mod K) 는 mul 배열에서 다 계산했고, ("678" mod K) 도 integer 배열에 미리 다 연산해놓았으므로 쉽게 계산할 수 있다.

피드백

 처음에 DP 배열 정의까지는 떠올렸으나, DP 배열 초기화 및 채우는 방법에서 굉장히 오래 헤맸다.

 DP[i][j] 에 그냥 1 ~ N 번 째 정수를 다 붙여본다고 생각하면 간단한데 너무 꼬아서 생각한 것 같다.

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

int N, K;
long long dp[1 << 15][100];
long long factorial[16];
int integer[15];
int mul[51];
string list[15];

long long gcd(long long a, long long b) {
	while (b) {
		long long r = a % b;
		a = b;
		b = r;
	}
	return a;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> list[i];
	cin >> K;

	for (int i = 0; i < N; i++)
		reverse(list[i].begin(), list[i].end());

	factorial[1] = 1;
	for (int i = 2; i <= 15; i++)
		factorial[i] = factorial[i - 1] * i;

	mul[0] = 1;
	for (int i = 1; i < 51; i++)
		mul[i] = (mul[i - 1] * 10) % K;

	for (int i = 0; i < N; i++) {
		int temp = 0;
		for (int j = 0; j < list[i].length(); j++) {
			temp += ((list[i][j] - '0') * mul[j]) % K;
			temp %= K;
		}
		integer[i] = temp;
	}

	// dp 배열을 채워보자.
	dp[0][0] = 1;
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < N; k++) { // k번 째 친구를 안쓴애들만 쓰자.
				if ((i & (1 << k)) == 0) { // 현재 상태랑 k 사용이랑 겹치는게 없음.
					// 현재 나머지가 j --> k번 째 수를 사용하면 나머지가 바뀜
					int next = j * mul[list[k].length()];
					next %= K;
					next += integer[k];
					next %= K;
					dp[i | (1 << k)][next] += dp[i][j];
				}
			}
		}
	}

	long long g = gcd(dp[(1 << N) - 1][0], factorial[N]);
	cout << (dp[(1 << N) - 1][0] / g) << '/' << (factorial[N] / g) << '\n';

	return 0;
}

 

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

[BOJ] 2352 : 반도체 설계  (0) 2020.06.15
[BOJ] 1162 : Revamping Trails  (0) 2020.06.09
[BOJ] 7575 : 바이러스  (2) 2020.05.22
[BOJ] 11559 : Puyo Puyo  (0) 2020.05.21
[BOJ] 1038 : 감소하는 수  (0) 2020.05.20

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

오늘은 String 클래스 정리에 이어서 StringBuilder 클래스를 정리해보겠습니다.


StringBuilder 클래스

 StringBuilder 클래스는 저번 포스팅에서 다루었던 String 클래스와 기능 면에서 정말 비슷합니다.

 하지만,

 

내부적으로 StringBuilder 클래스는 문자열을 저장하기 위한 메모리 공간을 지니고 있습니다.

그리고 이 메모리 공간은 String 클래스와 달리 문자를 추가하거나 삭제하는 것이 가능합니다.

 

 그럼 왜 기능 면에서 비슷한 두 개의 클래스를 자바에서 지원해주고 있을까요? 위에서 언급했던 문자를 추가하거나 삭제하는 것이 가능하기 때문입니다.

 다음 예제를 통해 StringBuilder 클래스의 장점에 대해서 알아보겠습니다.

String ex1 = "0" + 6 + '.' + "01";

 위의 코드는 실행하면 다음과 같이 바뀝니다.

String ex1 = "0".concat(String.valueOf(6)).concat(String.valueOf('.')).concat(String.valueOf(16));

 valueOf 메소드를 이용해 String 인스턴스를 생성하고 concat 메소드에 매개변수 인자로 넘겨줍니다. 따라서, String 인스턴스가 반복되서 생성됩니다. 이는 성능에 안 좋은 영향을 미치게 됩니다. 따라서, 새로운 인스턴스 생성 없이 문자를 추가하거나 삭제할 수 있는 StringBuilder 클래스가 등장했습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		String str1 = new String("abcdabcdabcd");
		String str2 = str1.concat("123");
		if(str1 == str2)
			System.out.println("같은 인스턴스를 참조 중입니다.");
		else
			System.out.println("같은 인스턴스 X");
		
		StringBuilder str3 = new StringBuilder("abcdabcdabcd");
		StringBuilder str4 = str3.append(123);
		if(str3 == str4)
			System.out.println("같은 인스턴스 참조 중 ");
		else
			System.out.println("같은 인스턴스 X");
	}
}

 위의 코드에서도 StringBuilder 클래스의 장점을 알아볼 수 있습니다. 결과는 str1 과 str2는 같은 인스턴스를 참조하지 않고, 즉 str2는 새로운 인스턴스가 생성된 것을 알 수 있고, str3 와 str4는 같은 인스턴스를 참조하는 것을 알 수 있습니다. StringBuilder 클래스는 이처럼 문자를 추가하거나 삭제할 때 인스턴스 생성을 최소화함으로써 성능을 향상시킵니다.

StringBuilder 메소드

public StringBuilder append(boolean b)
public StringBuilder append(char c)
public StringBuilder append(double d)
public StringBuilder append(float f)
public StringBuilder append(int i)
public StringBuilder(Object obj)
public StringBuilder(String str)
// 등등 append 메소드는 다양하게 오버로딩 되어 있습니다.
// 기본 자료형 데이터를 문자열 내용에 추가해주는 메소드

public StringBuilder delete(int start, int end)
// start ~ end 이전까지의 내용을 삭제해주는 메소드

public StringBuilder insert(int offset, String str)
// offset 위치에 str에 전달된 문자열 추가

public StringBuilder replace(int start, int end, String str)
// start ~ end 이전까지의 내용을 str로 대체

public StringBuilder reverse()
// 저장된 문자열의 내용을 뒤집는 메소드

public String substring(int start, int end)
// start ~ end이전까지의 내용만 담은 String 인스턴스의 생성 및 반환

public String toString()
// 저장되 문자열의 내용을 담은 String 인스턴스의 생성 및 반환

public StringBuilder append( // 다양한 매개변수 ) 메소드

 append 메소드를 이용하면 문자열을 쉽게 추가할 수 있습니다. 기본 자료형을 포함한 다양한 인자를 전달받도록 오버로딩 되어 있습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		System.out.println(str1.toString());
	}
}

 int 형 75와 String 인스턴스 "75" 를 전달하니 문자열이 쉽게 추가되는 것을 확인할 수 있습니다.

public StringBuilder delete(int start, int end)

 delete 메소드를 이용하면 문자열을 삭제할 수 있습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		str1.delete(2,  5);
		System.out.println(str1.toString());
	}
}

 delete(2, 5) 를 수행하면 index 2 ~ 4 까지 삭제되는 것을 확인할 수 있습니다.

public StringBuilder insert(int offset, String str)

 insert 메소드를 이용하면 문자열을 원하는 위치에 삽입 할 수 있습니다.

 위의 예시에서 이어서 "travelbeeee" 문자열을 중간에 삽입해보겠습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		str1.delete(2,  5);
		str1.insert(2, "travelbeeee");
		System.out.println(str1.toString());
	}
}

public StringBuilder replace(int start, int end, String str)

 replace 메소드를 이용하면 원하는 부분을 다른 문자열로 대체할 수 있습니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		str1.delete(2,  5);
		str1.insert(2, "travelbeeee");
		str1.replace(0, 2, "tistory.");
		System.out.println(str1.toString());
	}
}
tistory.travelbeeeebcdabcd7575

 앞의 두 글자 (0 ~ 1 인덱스) 를 "tistory." 문자열로 대체했습니다.

public StringBuilder reverse()

 reverse 메소드는 매개변수 전달 없이 저장된 문자열을 뒤집어주는 메소드입니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		str1.delete(2,  5);
		str1.insert(2, "travelbeeee");
		str1.replace(0, 2, "tistory.");
		str1.reverse();
		System.out.println(str1.toString());
	}
}
5757dcbadcbeeeeblevart.yrotsit

public String substring(int start, int end)

 substring 메소드는 StringBuilder 인스턴스에 저장된 문자열의 부분 문자열을 String 인스턴스로 반환해주는 메소드입니다. 반환형은 String 인스턴스인 것을 주의하셔야 됩니다.

package Hello;

public class test{
	public static void main(String args[]) {
		StringBuilder str1 = new StringBuilder("abcdabcdabcd");
		str1.append(75);
		str1.append("75");
		str1.delete(2,  5);
		str1.insert(2, "travelbeeee");
		str1.replace(0, 2, "tistory.");
		str1.reverse();
		System.out.println(str1.substring(0, 5));
	}
}
5757d

 

 StringBuilder 클래스는 문자열을 추가, 삭제, 대체하는데 정말 유용한 메소드들을 지원해주고 String 클래스보다 성능 면에서도 좋습니다. StringBuilder 클래스는 자바 5에서 등장한 클래스로 그 전에는 StringBuffer 클래스를 이용해 동일한 기능을 수행했다고 합니다. 하지만, StringBuffer 클래스는 멀티 쓰레드 환경에서 안전하게 동작하도록 만들어졌지만 속도가 느리므로 요즘은 StringBuilder 클래스를 더 유용하게 사용한다고 합니다.


 

+ Recent posts