개요

백준 문제 1934번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 10분
https://www.acmicpc.net/problem/1934

문제

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
using namespace std;

void LCM(int numA,int numB)
{
	int addedNum = numB;
	while(addedNum % numA != 0)
	{
		addedNum += numB;
	}
	cout << addedNum <<"\n";
}

void solve()
{
	int testCase,numA,numB;
	cin >> testCase;
	for(int i=0;i<testCase;i++)
	{
		cin >> numA >> numB;
		LCM(numA,numB);

	}

}

int main()
{
	solve();
}

풀이

둘 중에 한 값을 A라고 했을 때 A는 계속 A를 더하면서 더해진 값 % B == 0인지 확인한다.

개요

백준 문제 2609번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ???
https://www.acmicpc.net/problem/2609

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
using namespace std;

void LCM(int num1,int num2,int gcd)
{
	cout << ((num1 * num2) / gcd) << "\n";
}

void GCD(int num1,int num2)
{	
	int tmpNum1 = num1;
	int tmpNum2 = num2;
	while(tmpNum2 != 0)
	{
		int r = tmpNum1 % tmpNum2;
		tmpNum1 = tmpNum2;
		tmpNum2 = r;
	}
	cout << tmpNum1 << endl;
	LCM(num1,num2,tmpNum1);
}


void solve()
{
	int num1,num2;
	cin >> num1 >> num2;
	GCD(num1,num2);


}

int main()
{
	solve();

}

소감 및 메모

예전에 배웠던 알고리즘인데 기억이 안남,,ㅋ
최소공배수는 a * b / gcd인 점
최대공약수는 그..네..외우죠,,ㅋ 유클리드 호제법입니다..!

개요

segment tree 자료구조를 공부하고 정리한다.

공부하게 된 배경

백준 1168 문제를 O(n^2)방법으로 풀었는데 시간초과가 발생하여
더 좋은 풀이 방법을 찾지 못하던 중
찾아보니 segment tree를 이용하면 O(NlogN)으로 풀 수 있다는 것을 발견하고
segment tree를 알아보게 되었다.

segment tree 개요

segment tree는 일반적으로 트리 자체에 구간합을 가지고 있다.
루트가 모든 합, 루트의 왼쪽에는 0~N/2까지,
루트의 오른쪽은 N/2+1 ~ N-1까지의 구간 합을 가지는 식으로 트리가 구성된다.
트리의 특징 상 필요한 합을 탐색하는데 시간복잡도는 O(logn)으로 선형적 자료구조에서 보다 빠름을 알 수 있다.

segement tree 코드

#include <iostream>
using namespace std;
const int MAX = 10001;
int arr[MAX];
int N;
int tree[MAX];

void init()
{
    cin >> N;
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
    }
}

int makeSegmentTree(int start,int end,int node)
{
    if(start == end)
    {
        return tree[node] = arr[node];
    }
    int mid = (start+mid)/2;
    return tree[node] = makeSegmentTree(start,mid,node * 2) + makeSegmentTree(mid+1,end,node * 2 + 1);

}

int sumSegmentTree(int start,int end,int node,int left,int right)
{
    if(left > end || right < start)
    {
        return 0;
    }
    //구간에 충족한다면 더 들어갈 필요 없이 리턴  
    if(left <= start && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end)/2;
    return sumSegmentTree(start,mid,node*2,left,right) + sumSegmentTree(mid+1,end,node*2+1,left,right);
}

void updateSegmentTree(int start,int end,int node,int changeVal,int idx)
{
    if(start > idx || end < idx)
    {
        return;
    }
    tree[node] += changeVal;
    //마지막 구간을 업데이트 하고 나면 더 깊게 들어갈 필요 없이 리턴
    if(start == end)
    {
        return;
    }
    int mid = (start + end) / 2;
    updateSegmentTree(start,mid,node*2,changeVal,idx);
    updateSegmentTree(mid+1,end,node*2+1,changeVal,idx);
}

int main()
{
    init();
    makeSegmentTree(0,N-1,1);

}

개요

백준 문제 1668번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ???
https://www.acmicpc.net/problem/1668

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#include <iostream>
using namespace std;
const int MAX = 10001;
int data[MAX];
int N,K;
int * tree;

void initData()
{
	cin >> N >> K;
	int * tmp = (int *)malloc(sizeof(int) * ((N+1)* 4));
	fill_n(tmp,(N+1)*4,-1);
	tree = tmp;

}

int initTree(int start,int end,int node,int * tree)
{	
	if(start == end)
	{
		return tree[node] = 1;
	}
	int mid = (start + end) / 2;
	return tree[node] = initTree(start,mid,node*2,tree) + initTree(mid+1,end,node*2+1,tree);
}

int getIdx(int start,int end,int node,int K)
{
	if(start == end)
	{
		return start;
	}
	int mid = (start + end) / 2;
	if(K <= tree[node * 2])
	{
		return getIdx(start,mid,node * 2,K);
	}
	else
	{
		return getIdx(mid+1,end,node * 2 + 1,K - tree[node * 2]);
	}
}

void updateTree(int start,int end,int node,int idx)
{
	if(idx < start || idx > end)
	{
		return;
	}
	tree[node]--;
	if(start == end)
	{
		return;
	}
	int mid = (start + end) / 2;
	updateTree(start,mid,node*2,idx);
	updateTree(mid+1,end,node*2+1,idx);
}	

void solve()
{	
	int deleteIdx = 0;
	int findIndex = 1;
	int remainNum = 0;

	initData();
	initTree(1,N,1,tree);
	cout << '<';
	for(int i=0;i<N;i++)
	{
		remainNum = N - i;
		findIndex += K - 1;
		if(findIndex % remainNum == 0)
		{
			findIndex = remainNum;
		}
		else if(findIndex > remainNum)
		{
			findIndex = findIndex % remainNum;
		}
		deleteIdx = getIdx(1,N,1,findIndex);
		updateTree(1,N,1,deleteIdx);
		cout << deleteIdx;
		if(i != N-1)
		{
			cout << ", ";
		}
		else
		{
			cout << ">";
		}
	}


}

int main()
{
	initData();
	solve();

}

코드 수준 메모

segment tree로 탐색을 Nlog(n)의 시간복잡도를 가지게 할 수 있어
segment tree로 배열의 인덱스 합 트리를 구성한다.
이후 삭제할려는 노드의 인덱스를 찾고 가져오면 되는데 그것은 getIdx 함수에서 한다.
그 중 코드를 보면 return getIdx(mid+1,end,node * 2 + 1,K - tree[node * 2]);
위 코드의 K - tree[node * 2]는 루트 노드에서 오른쪽으로 간다.
이 말은 트리 구조상 오른쪽이기 때문에 이동할려는 인덱스 - 왼쪽 노드 인덱스를 해야
정상적인 인덱스 비교를 할 수 있다 그렇지 않으면 오른쪽으로 한번 이동 한 뒤 항상 오른쪽으로 가게 된다.(루트보다 인덱스 값이 더 크기 때문에)
간단하게는 루트 노드와 왼쪽 오른쪽 노드가 같은 인덱스 범위를 갖는다면 어떻게 할 것인지 생각하면 알 수 있다.
update 함수는 삭제할려는 노드를 삭제하는 것인데 이것은 실제로는 해당하는 노드에서부터 루트까지 -1 해주면 삭제하는 효과를 얻을 수 있다.

소감 및 메모

일단은 어려웠다 어려운 문제였고
문제 자체는 저번에 풀었던 문제인데 그 문제에서 시간 제한이 빡빡해져서
O(N^2)으로 풀면 시간초과가 나기 때문에
이전 알고리즘보다 더 빠른 알고리즘을 채택해야하는데
아직 경험이 부족해 그런 알고리즘을 스스로 생각하진 못하고 검색하여 segment tree를 찾아내어 공부를 했다.
위 코드는 segment tree도 공부하고 여러 블로그에서 설명과 코드를 보면서 짠 코드라
내 실력이라 말할 수 없다.

그냥 문제 많이 풀어야함 수구바위