Feel Coding

C++로 트리 자료구조를 구현할 때에는 보통 왼쪽 자식을 가리키는 포인터, 오른쪽 자식을 가리키는 포인터, 내 데이터 이렇게 3가지 정보를 가지고 있는 Node라는 구조체를 만들어서 구현한다.

그런데 이 방법은 알고리즘 문제를 풀 때 직접 구현하기에는 너무 복잡하고 포인터를 이용하기 때문에 nullpointer 예외가 나기도 쉽다.

이진트리는 C++ STL인 map과 pair를 이용해서 쉽게 구현할 수 있다.

(만약 map을 잘 모르신다면 이 글을 먼저 보고 오는 것을 추천한다. 링크↓)

https://breakcoding.tistory.com/154

다음과 같은 이진트리가 있다고 하자.

일단 트리를 저장할 map 객체를 선언한다. 이 트리에는문자가 저장되어 있기 때문에 char 타입으로 선언했다.

pair에는 왼쪽 자식 노드와 오른쪽 자식 노드를 집어넣을 것이다.

map<char, pair<char, char>> tree;

A의 오른쪽 자식은 B, 왼쪽 자식은 C이므로 A 노드를 다음과 같이 집어넣어준다.

tree['A'] = make_pair('B', 'C');

B의 왼쪽 자식 노드는 D, 오른쪽 자식 노드는 없다. 자식이 없을 경우 .으로 표현하기로 하자. (NULL로도 표현해도 되고 내가 원하는 방식으로 표현해주면 된다. 대신 데이터로는 절대 나올 수 없는 것으로 선택해야 한다.)

tree['B'] = make_pair('D', '.');

D는 왼쪽, 오른쪽 자식이 모두 없으므로 tree['D']에는 이렇게 저장해준다.

tree['D'] = make_pair('.', '.');

이런식으로 모든 노드들을 tree라는 map에 저장해준다.

tree['C'] = make_pair('E', 'F');
tree['E'] = make_pair('.', '.');
tree['F'] = make_pair('.', 'G');
tree['G'] = make_pair('.', '.');

이렇게 노드의 개수만큼 map에 저장하는 것을 반복해주면 이진트리가 완성된다.

A 노드의 왼쪽 자식을 알고 싶으면

tree['A'].first

A의 오른쪽 자식을 알고 싶으면

tree['A'].second

이렇게 해주면 된다.

(pair 사용법이 낯설다면 이전 포스팅을 보고 오는 것을 추천한다. 링크↓)

https://breakcoding.tistory.com/96

일반적인 이진트리 구현방법인 포인터를 이용한 구조체로 트리를 구현했다면 무조건 가장 아래쪽에 있는 노드 D, 노드 E, 노드 G부터 만들어주고 위로 올라가야 한다. 따라서 그냥 이음선의 정보만 주어진다면 트리를 구현하기 위해서 위상정렬까지 해야 하는 상황이 발생한다. 하지만 이렇게 map을 이용해서 이진트리를 구현한다면 순서와 상관없이 이렇게 이음선의 정보만 map에 추가해주면 되기 때문에 트리를 쉽게 구현할 수 있다.

그러면 이렇게 map으로 구현한 이진트리를 전위순회, 중위순회, 후위순회 하는 방법을 알아보자.

void preorder(char node) {//전위순회
	cout << node << " "; //현재 노드의 데이터 출력
	if (m[node].first != '.') { //왼쪽 자식이 있다면
		preorder(m[node].first);
	}
	if (m[node].second != '.') { //오른쪽 자식이 있다면
		preorder(m[node].second);
	}
}
void inorder(char node) {//중위순회
	if (m[node].first != '.') { //왼쪽 자식이 있다면
		inorder(m[node].first);
	}
	cout << node << " "; //현재 노드의 데이터 출력
	if (m[node].second != '.') { //오른쪽 자식이 있다면
		inorder(m[node].second);
	}
}
void postorder(char node) { //후위순회
	if (m[node].first != '.') { //왼쪽 자식이 있다면
		postorder(m[node].first);
	}
	if (m[node].second != '.') { //오른쪽 자식이 있다면
		postorder(m[node].second);
	}
	cout << node << " "; //현재 노드의 데이터 출력
}

이렇게 재귀함수로 쉽게 순회할 수 있다. 만약 자식 노드가 없을 때에 NULL로 저장했다면

왼쪽 자식이 있는지 체크하는 부분을 m[node].first != NULL로

오른쪽 자식이 있는지 체크하는 부분을 m[node].second != NULL로 해주면 된다.

https://www.acmicpc.net/problem/9507

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	long long koong[68];
	koong[0] = koong[1] = 1;
	koong[2] = 2;
	koong[3] = 4;
	for (int i = 4; i < 68; i++) {
		koong[i] = koong[i - 1] + koong[i - 2] + koong[i - 3] + koong[i - 4];
	}
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		cout << koong[n] << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/11057

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


int main() {
	int n;
	cin >> n;
	vector<vector<int>> count(1001,vector<int>(10));
	for (int i = 0; i < 10; i++) {
		count[0][i] = 1;
		count[1][i] = 10 - i;
	}
	for (int i = 2; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = j; k < 10; k++) {
				count[i][j] = (count[i][j] + count[i - 1][k]) % 10007;
			}
		}
	}
	int total = 0;
	for (int i = 0; i < 10; i++) {
		total = (total + count[n - 1][i]) % 10007;
	}
	cout << total;
	return 0;
}

https://www.acmicpc.net/problem/11727

규칙성을 찾으면 되는 문제이다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int dp[1001];
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
	}
	cout << dp[n];
	return 0;
}

숫자처럼 생긴 문자열을 숫자로 바꿔야 할 때가 있다. 아니면 숫자를 문자열로 바꿔야 할 때도 있을 수 있다.

그럴 때 쓰는 것이 stoi, stof, stol, stod, stold, stoll 함수이다.

이 함수들은 string 클래스에 정의되어 있기 때문에 이 함수들을 사용하려면 <string> 헤더파일을 포함해야 한다.

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


int main() {
	string s = "100";
	int a = stoi(s); //문자열 s를 정수형으로 바꿈
	cout << a + 45 << endl;
	return 0;
}

문자열일 때에는 정수와 더하기가 불가능했는데 int형으로 바꾸니 더하기가 멀쩡하게 되는 것을 볼 수 있다.

그렇다면 char형을 정수로 바꾸고 싶다면?

char형은 정수이기 때문에 0의 아스키코드인 48을 빼주면 된다. 0의 아스키코드를 기억하기 힘들다면 '0'을 빼주면 된다.

#include <iostream>
using namespace std;


int main() {
	char c = '9';
	int a = c - '0';
	cout << a + 10 << endl;
	return 0;
}

https://www.acmicpc.net/problem/11052

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


int main() {
	int n;
	cin >> n;
	vector<int> v(n + 1);
	v[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	vector<int> dp(n + 1);
	dp[1] = v[1];
	dp[0] = v[0];
	for (int i = 1; i <= n; i++) {
		int maxDp = v[i];
		for (int j = 1; j < i; j++) {
			if (dp[j] + dp[i - j] > maxDp) maxDp = dp[j] + dp[i - j];
		}
		dp[i] = maxDp;
	}
	cout << dp[n];
	return 0;
}

https://www.acmicpc.net/problem/9465

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


int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		vector<vector<int>> score(2, vector<int>(n));
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				cin >> score[i][j];
			}
		}
		vector<pair<int, int>> dp(n);
		dp[0] = make_pair(score[0][0], score[1][0]);
		if (n > 1) dp[1] = make_pair(dp[0].second + score[0][1], dp[0].first + score[1][1]);
		for (int i = 2; i < n; i++) {
			dp[i].first = max(dp[i - 1].second + score[0][i], dp[i - 2].second + score[0][i]);
			dp[i].second = max(dp[i - 1].first + score[1][i], dp[i - 2].first + score[1][i]);
		}
		cout << max(dp[n - 1].first, dp[n - 1].second) << '\n';
	}
	return 0;
}

벡터 dp의 first는 윗줄을 선택했을 때, dp의 second는 아랫줄을 선택했을 때의 최댓값을 저장하도록 했다.

안드로이드 스튜디오에서 앱을 만드는 도중 이렇게 람다식이 지원이 안 된다고 뜬다면

다음과 같이 모듈 수준 gradle 파일에 들어가서

다음 코드를 추가한다.

compileOptions {
    sourceCompatibility JavaVersion.VERSION_1_8
    targetCompatibility JavaVersion.VERSION_1_8
}

그러면 이제 오류 없이 람다식을 사용할 수 있다.

StringTokenizer는 구분자를 기준으로 문자열을 분리하고 싶을 때 클래스이다.

구분자란 무엇일까?

"양파,당근,마늘,오이,상추"라는 문자열이 있을 때 콤마(,)를 기준으로 나누고 싶다면 콤마(,)가 구분자이다.

"2020년 02월 15일"이라는 문자열이 있을 때 공백을 기준으로 나누고 싶다면 공백이 구분자이다.

"2020-02-15"라는 문자열이 있을 때 '-' 문자를 기준으로 나누고 싶다면 구분자는 '-'이다.

일단 문자열을 쪼개고 싶다면 StringTokenizer 객체를 생성해야 한다. StringTokenizer 객체를 생성할 때에는 나누고 싶은 문자열과 구분자를 적어야 한다. 구분자를 적어주지 않으면 공백을 기준으로 나눈다.

String s = "2020년 2월 15일";
StringTokenizer tokenizer = new StringTokenizer(s); //공백을 기준으로 문자열 s를 나누기 위한 객체

공백을 기준으로 문자열을 나누고 싶다면 이렇게 생성자의 인자로 문자열만 넣어주면 된다.

String s = "2020-02-15";
StringTokenizer tokenizer = new StringTokenizer(s, "-");

특정 문자열을 기준으로 나누고 싶다면 문자열과 구분자를 생성자의 인자로 넣어주면 된다.

이렇게 StringTokenizer 객체를 생성하고 나면 문자열을 쪼개기 위한 준비작업은 다 끝났다.

이제 문자열을 나누면 된다.

일단 StringTokenizer 클래스의 메소드부터 살펴보자.

https://docs.oracle.com/javase/10/docs/api/java/util/StringTokenizer.html

이 메소드들의 사용법은 직접 코드를 보면서 배우는 것이 가장 빠를 거라고 생각한다.

import java.util.StringTokenizer;

public class StringTokenizerTest {
    public static void main(String[] args) {
        String s = "2020-02-15";
        StringTokenizer tokenizer = new StringTokenizer(s, "-");
        System.out.println("토큰의 개수: " + tokenizer.countTokens());
        while(tokenizer.hasMoreTokens()) {
            System.out.println(tokenizer.nextToken());
            System.out.println("토큰의 개수: " + tokenizer.countTokens());
        }
    }
}

import java.util.StringTokenizer;

public class StringTokenizerTest {
    public static void main(String[] args) {
        String s = "안녕? 여기는 feelcoding 블로그야";
        StringTokenizer tokenizer = new StringTokenizer(s);
        System.out.println("토큰의 개수: " + tokenizer.countTokens());
        while(tokenizer.hasMoreTokens()) {
            System.out.println(tokenizer.nextToken());
        }
    }
}

import java.util.StringTokenizer;

public class StringTokenizerTest {
    public static void main(String[] args) {
        String s = "2020-02-15";
        StringTokenizer tokenizer = new StringTokenizer(s, "-");
        System.out.println("토큰의 개수: " + tokenizer.countTokens());
        while(tokenizer.hasMoreTokens()) {
            System.out.println(tokenizer.nextToken());
        }
    }
}

import java.util.StringTokenizer;

public class StringTokenizerTest {
    public static void main(String[] args) {
        String s = "2020-02-15";
        StringTokenizer tokenizer = new StringTokenizer(s, "-");
        System.out.println("토큰의 개수: " + tokenizer.countTokens());
        while(tokenizer.hasMoreTokens()) {
            System.out.println(tokenizer.nextToken());
            System.out.println("토큰의 개수: " + tokenizer.countTokens());
        }
        tokenizer.nextToken(); //다 소모한 객체에서 토큰을 뽑아내려고 시도. 예외 발생
    }
}

StringTokenizer 객체는 소모적이라서 한 번 사용하면 다시 사용할 수 없다.

다시 사용하고 싶다면 객체를 새로 만들어야 한다. 이미 소모한 객체에서 토큰을 꺼내려고 하면 다음과 같이 NoSuchElementException 예외가 발생한다.

13번째 줄에서 예외가 발생했다고 하는데 그것은 마지막 코드인 tokenizer.nextToken();이다.

따라서 nextToken() 메소드를 사용하기 전에는 반드시 if(객체.hasMoreTokens()) 또는 if(객체.countTokens() > 0)으로 체크해보고 토큰을 뽑아야 한다.

https://www.acmicpc.net/problem/1431

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

bool cmp(string a, string b) {
	if (a.size() != b.size()) {
		return a.size() < b.size();
	}
	else {
		int sumOfA = 0;
		int sumOfB = 0;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] < 58) {
				sumOfA += (a[i] - '0');
			}
		}
		for (int i = 0; i < b.size(); i++) {
			if (b[i] < 58) {
				sumOfB += (b[i] - '0');
			}
		}
		if (sumOfA != sumOfB) {
			return sumOfA < sumOfB; //sumOfB
		}
		else {
			return a < b;
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < n; i++)
		cout << v[i] << '\n';
	return 0;
}