BOJ 1968 트리의 지름

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

이 문제는 가중치가 주어진 트리에서 leaf과 leaf 사이, 혹은 루트와 leaf 사이의 모든 가중치의 합 중 가장 큰 값을 구하는 문제입니다. 

예제에서 주어진 그래프에서는 45의 값으로 답이 됩니다. 빨간색 선을 따라가면 9 - 5 - 3 - 6 - 12의 노드를 지나게 되고 가중치 합은 45라는 것을 알 수 있습니다. 이 값보다 큰 값은 존재하지 않습니다.

이 문제는 트리를 사용하여 풀 수 있습니다. 트리의 잎부터 시작해 올라오면서 서브트리의 양쪽 잎까지의 가중치 합과 서브트리의 루트와 잎까지 합 중 가장 큰 값으로 계속 업데이트를 하면 됩니다.

설명 및 전체 코드

입력받은 값으로 트리를 구성해야하는데, 이때 Node라는 구조체로 노드를 만들겠습니다. 이 Node 구조체는 자식 Node들을 가지고 있고, 부모로 향하는 weight값을 가지고 있는 구조체로 정의되어 있습니다. 노드의 자식은 여러개일 수 있으므로 vector를 사용했습니다.

typedef struct Node {
	vector<Node*> children = vector<Node*>();
	int weight;
};

기저사례로는 자식이 없을 경우 바로 부모로 향하는 weight를 return해줍니다. 더 이상 진행할 필요가 없으니까요. 그리고 자식이 한개일 경우에는 weight와 그 밑으로 향하는 큰 값중 하나를 더해서 반환해주면 됩니다.

if (root->children.size() == 0) return root->weight;

if (root->children.size() == 1) 
	return root->weight + traverse(root->children[0]);

그 외에는 자식이 둘 이상이겠죠. 양쪽으로 분기되는 값 중 가장 큰 값 두개를 선택해서 더해준 값을 현재까지 업데이트된 값하고 비교하여 둘 중 가장 큰 값으로 업데이트해줍니다. 현재까지 업데이트된 값을 value라고 임시로 정해줍시다.

이 과정을 루트로 올라올때까지 진행해주면 답을 구할 수 있습니다. 아래는 정답 코드입니다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;
typedef struct Node {
	vector<Node*> children = vector<Node*>();
	int weight;
};

Node nodes[10001];
int value = 0;
int traverse(Node *root) {
	//자식이 없는 경우 부모쪽으로 가는 간선의 값 return
	if (root->children.size() == 0) return root->weight;
	//자식이 하나일 경우 자신의 weight을 더해 return
	if (root->children.size() == 1) 
		return root->weight + traverse(root->children[0]);
	
	//여기서부터는 자식이 둘 이상
	vector<int> weights = vector<int>(root->children.size());

	//자식들 모두 다 돌때까지
	for (int i = 0; i < root->children.size(); i++) 
		weights[i] = traverse(root->children[i]);
	
	//오름차순으로 정렬
	sort(weights.begin(), weights.end());

	//가장 큰 값을 가진 두 값을 더해서 value와 비교하여 value업데이트
	value = max(weights[root->children.size()-1]
		+ weights[root->children.size()-2], value);
	
	//현재의 weight와 다 더한값의 제일큰 weights값을 더하여 return
	return root->weight+weights[root->children.size()-1];
}

int main() {
	
	scanf("%d", &n);
	nodes[1] = Node();
	nodes[1].weight = 0;
	n--;
	for (int i = 0; i < n; i++) {
		int from, to, weight;
		scanf("%d %d %d", &from, &to, &weight);
		nodes[to] = Node();
		nodes[to].weight = weight;
		nodes[from].children.push_back(&nodes[to]);
	}
	int ret = max(value, traverse(&nodes[1]));
	printf("%d\n", ret);
}

이상으로 트리에 관한 문제를 풀어보았습니다.

BOJ 17298 오큰수

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

문제 설명

어떤 수열이 있는데요. 이 수열의 한 원소를 기준으로 오른쪽에 있는 자신보다 큰 원소 중 가장 왼쪽에 있는 수가 오큰수라고 합니다. 이때 수열에 대해 모든 원소의 오큰수를 구하는 것이 문제입니다. 

이때 오큰수가 없는 경우도 있습니다. 가장 큰 원소이거나 가장 오른쪽에 있는 원소는 오큰수가 없을 수가 있죠. 이때는 -1로 오큰수를 정해줍니다.

예를 들어 3 5 2 7 6 8이라는 수열이 있다면 5 7 7 8 8 -1이 해답이 됩니다. 5의 오른쪽에 있는 큰 수들은 7 6 8이 있는데, 이때 가장 왼쪽에 있는 수가 7이므로 5의 오큰수는 7이 됩니다. 여기까지 이해를 했으면 이제 문제를 풀어보겠습니다.

풀이

이 문제에 대해서 왼쪽부터 시작하지 말고 오른쪽부터 시작하면 접근이 쉽습니다. 가장 오른쪽에 있는 오큰수는 없으니까 -1로 시작하게 됩니다.

가장 최근에 큰 수(A)을 기억하고 있다가 그것보다 작은 수(B)가 나오게 되면 B의 오큰수는 A가 됩니다. 이때 B는 그냥 버리면 안됩니다. 왜냐면 B가 왼쪽 어떤 C의 오큰수 일 수 있으니까요. 그래서 B를 기억하고 있어야합니다. 아래와 같은 상황에서 B는 C의 오큰수가 됩니다. 이때 C도 역시 기억하고 있어야됩니다. C도 어떤 수의 오큰수가 될 수 있게 되니까요. 아래의 그림은 이해하기 쉽게 도형의 크기로 수의 크기를 표현하였습니다.

하지만 C가 B보다 큰 경우 B는 오큰수가 아니게 되겠죠? C 이전의 수들은 B가 필요없게 됩니다. 왜냐면 C가 B보다 크면서 더 왼쪽에 있으니까요. 그래서 B는 이제 기억에서 사라지고 C를 기억하고 있어야됩니다.

자, 이제 뭔가 좀 감이 잡힐 수 있습니다. 가장 최근에 것을 상황에 따라 보관하고 있다가 비교하거나 버리고 하는 것을 알 수 있게 됩니다. 그래서 스택이라는 자료구조가 이 문제에서 사용됩니다.

Stack에는 가장 오른쪽부터 시작해서 오큰수들이 들어가게 됩니다. 이때 value는 현재 수열의 비교할 값을 말한다고 합시다. 스택의 가장 위(top)는 어떠한 오큰수가 들어가게 되는데, value보다 작다면 이 오큰수는 쓸모가 없게 되므로 스택에서 pop하면 됩니다. stack의 top이 value보다 더 클때까지 계속 pop하게 되면 결국 stack이 비게 되거나, value보다 큰 오큰수가 존재하게 됩니다. 

이때 스택이 비어있다면 value의 오큰수가 없다는 것, 비어있지 않다면 스택에 있는 top의 값이 오큰수가 되게 됩니다.

위 설명을 따른 예제에 대한 그림 풀이가 아래에 있습니다. 참고하시기 바랍니다.

전체코드

전체 코드는 아래와 같습니다. 주석처리하여 추가설명하였습니다.

#include <cstdio>
#include <stack>

using namespace std;
int n, numbers[1000001], ans[1000001];

int main() {

	stack<int> st = stack<int>();

	scanf("%d", &n);

	for (int i = 0; i < n; i++) 
		scanf("%d", &numbers[i]);
	
	st.push(numbers[n - 1]);	//가장 오른쪽에 있는 수는 stack에 push
	ans[n - 1] = -1;			//가장 오른쪽의 있는 수는 오큰수가 없으므로 -1
	for (int i = n - 2; i >= 0; i--) {	//거꾸로 for문
		int value = numbers[i];			//stack의 top과 비교할 숫자
		while (!st.empty() && value >= st.top()) {	//스택이 비어있지 않고, 스택의 top이 value보다 작거나 같으면
			st.pop();								//그 수는 버린다.
		}
		//이렇게 되면 두가지 상황이 발생하는데,
		//스택이 비어있으면 value 오른쪽에 오큰수가 없다는 것으로 value의 오큰수는 -1
		//숫자가 남아있다면 value보다 큰 수가 있는 것으로 오큰수는 st.top
		ans[i] = st.empty() ? -1 : st.top();
		
		//그리고 value를 stack에 push
		st.push(value);
	}

	for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
	printf("\n");
}

이상으로 포스팅을 마치겠습니다.

ASCII to Hex

간단히 말해서 입력이 String인데, 이것을 16진수 값으로 변환하는 코드를 구현해보도록 하겠습니다.

간단히 "CAFECAFE0102"라는 이런 문자열을 입력을 받았는데 16진수로 변환하고 싶은 것입니다.  즉, 0xCA, 0xFE, 0xCA, 0xFE, 0x01, 0x02의 숫자 배열로 입력을 변환하는 것이죠.

가장 간단하게 구현하기 위해서 매우 정상적인 입력값만 들어온다고 가정하겠습니다. 그러니까 16진수의 범위에 있지 않은 글자('G'를 넘어가는 알파벳)는 들어오지 않는다고 가정하겠습니다.

설명은 아래의 주석으로 대체하도록 하겠습니다.

#include <stdio.h>
#include <stdint.h>
#include <string.h>


//입력의 str은 모두 대문자인 16진수 변환가능한 문자열이라고 가정
//size는 str의 크기
//hex는 변환된 16진수 배열
unsigned int ascii_to_hex(const char* str, size_t size, uint8_t* hex)
{
    unsigned int i, h, high, low;
    for (h = 0, i = 0; i < size; i += 2, ++h) {
        //9보다 큰 경우 : 알파벳 문자 'A' 이상인 문자로, 'A'를 빼고 10을 더함.
        //9이하인 경우 : 숫자 입력으로 '0'을 빼면 실제 값이 구해짐.
        high = (str[i] > '9') ? str[i] - 'A' + 10 : str[i] - '0';
        low = (str[i + 1] > '9') ? str[i + 1] - 'A' + 10 : str[i + 1] - '0';
        //high 4비트, low 4비트이므로, 1바이트를 만들어주기 위해 high를 왼쪽으로 4비트 shift
        //이후 OR(|)연산으로 합
        hex[h] = (high << 4) | low;
    }
    return h;
}

int main() {
    char str[128] = "CAFEcafe0102";
    uint8_t hex[128] = { 0, };
    size_t size = strlen(str);
    int i;

    //소문자 cafe를 대문자로 만들기 위해 strupr함수 사용
    strupr(str);
    //hex에 실제 16진수의 값이 들어감
    ascii_to_hex(str, size, hex);
    
    //size는 반으로 줄어듦, ex) hex[0]=0xCA;
    for (i = 0; i < (size/2); i++)
        printf("0x%02X\n", hex[i]);
}

1바이트의 unsigned int 자료형인 uint8_t를 사용하기 위해서는 stdint.h를 include해야합니다.

결과

사실 ascii에 대한 개념과 char 자료형이 정수처럼 계산할 수 있다는 사실, 그리고 비트 연산(SHIFT, OR) 연산만 이해하고 알고 있다면 그렇게 어려운 구현은 아니라고 생각이 됩니다.