22.7.15

bin1225·2022년 7월 15일
0

c++ 알고리즘

목록 보기
20/35
post-thumbnail

76. 이항계수(메모이제이션)

메모이제이션이란 재귀함수를 호출하는 과정에서 이미 호출된 적이 있는 값들은 저장해놨다가 그대로 꺼내서 쓰는 방법이다.

이 문제를 봤을 때 그냥 for문 돌려서 풀면 되는 거 아닌가? 라고 생각했는데, 재귀를 사용하는 이유는 먼저 가독성이 높아진다는 장점이 있다. 그리고 더 큰 이유로 단순 반복보다 훨씬 확장가능성이 높다.

77. 친구인가? (Union&Find 자료구조)

int b, cnt[1000];
vector<int> v[1000];
void DFS(int a){
	
	if(v[a].empty()) return;
	else{
		for(int i=0; i<v[a].size(); i++){
			if(v[a][i]==b){
				cout<<"YES";
				exit(0);
			}
			else if(cnt[v[a][i]]==0)
			{
				cnt[v[a][i]]=1;
				DFS(v[a][i]);
			}
		}
	}
	
}

int main(){
	
	//freopen("input.txt","rt",stdin);	

	int n, m, a;
	cin>>n>>m;
	
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	cin>>a>>b;
	DFS(a);
	
	cout<<"NO";
	return 0;

}

내가 문제를 푼 방식은 이중벡터에 인덱스마다 직접적으로 주어진 친구관계에 대한 정보를 담는다.
예를 들면, 1 3, 1 5 가 데이터로 주어지면 1번 인덱스에 3,5를 추가한다.
그 후 cnt벡터로 방문한 수인지 확인하면서 재귀함수를 통해 서로 연관된 친구인지 확인하는 방법을 사용했다.
이 방법이 꽤 명확하긴 하지만 데이터가 커지면 굉장히 비효율적일 것 같다는 생각이 든다.
그래서 강의에서 보여준 방법을 사용한다면 좋겠지만, 솔직히 그 방법을 과연 혼자서도 떠올리고 응용할 수 있을지는 조금 의문이다. 강의에서는 Union&Find 알고리즘을 사용했다.


int unf[1001];
int find(int k){
	if(unf[k]==k) return k;
	else return unf[k] = find(unf[k]);
}


void Union(int a, int b){
	
	a = find(a);
	b = find(b);
	
	if(a!=b) unf[a] = b;
}
int main(){
	
	//freopen("input.txt","rt",stdin);	

	int n, m, a, b;
	cin>>n>>m;
	for(int i=1; i<n; i++){
		unf[i]=i;
	}
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		Union(a,b);		
	}
	cin>>a>>b;
	a = find(a);
	b = find(b);
	if(a==b) cout<<"YES";
	else cout<<"NO";
	
	return 0;
}

Union&Find 알고리즘을 사용한 코드이다.
초기에 unf배열을 인덱스와 인덱스마다 저장된 데이터의 값이 같도록 설정해둔다.
이후 친구 사이인 두 수에 해당하는 인덱스에 저장된 값을 통일시키는데, 이 과정에서 find함수가 이용된다.
find 함수는 인덱스에 저장된 데이터와 인덱스가 일치하면 그대로 return 하고 그게 아니라면 이 조건을 만족하는 수가 나올 때까지 재귀함수를 호출하면서 동일한 집합에 속한 인덱스에 저장된 수들을 통일하는 매커니즘이라고 이해했다.

0개의 댓글