6번 문제   

 

 

 

    내가 풀이한 답   

 

  • 전위순회(Preorder): 부모노드를 먼저 방문하고 자식 노드를 방문
  • 중위순회(Inorder): 왼쪽 자식을 먼저 방문하고 부모노드를 방문
  • 후위순회(Postorder): 자식 노드를 먼저 방문하고 부모노드를 방문

 

 

 


 위의 그림과 같이 각 노드의 왼쪽에 있는 빨간색 점을 선으로 쭉 이어보면 전위순회가 완성된다. 중위순회와 후위순회도 마찬가지로 각각 초록색, 파란색 점을 선으로 이어보면 구할 수 있다.  

#include <iostream>
using namespace std;
 
//전위순회
void pre(int v, int n){
	if(v > n) return;
	else {
		cout << v << " ";
		pre(v*2, n);
		pre(v*2+1, n);
	}
}
 
//중위순회
void mid(int v, int n){
	if(v > n) return;
	else {
		mid(v*2, n);
		cout << v << " ";
		mid(v*2+1, n);
	}
}
 
//후위순회
void aft(int v, int n){
	if(v > n) return;
	else {
		aft(v*2, n);
		aft(v*2+1, n);
		cout << v << " ";
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	pre(1, n);
	cout << endl;
	mid(1, n);
	cout << endl;
	aft(1, n);
 
	return 0;
}

 

 

 

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x>7) return;
	else{
		printf("%d ", x);
		D(x*2);
		D(x*2+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	D(1);
	return 0;
}

 

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

8. 합이 같은 부분집합(DFS 완전탐색 : 아마존 인터뷰)  (0) 2020.10.22
7. 부분집합(DFS 완전탐색)  (0) 2020.10.22
5. 최소비용(DFS : 가중치 방향그래프 인접리스트)  (0) 2020.09.23
4. 최소비용(DFS : 인접행렬)  (0) 2020.09.23
3. 경로 탐색(DFS : 인접리스트 방법)  (0) 2020.09.23

    57번 문제   

 

 

 

 

    내가 풀이한 답   

 

Stack 구조를 활용하여 2로 나눈 몫이 1이면 몫과 나머지 순으로 출력하고 1이 아니면 다시 재귀함수를 호출하였다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
void binary(int n){
	if(n/2==1) {
		cout << n/2 << n%2;
		return;
	}
	else {
		binary(n/2);
		cout << n%2;
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	binary(n);
 
	return 0;
}

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x==0) return;
	else{
		D(x/2);
		printf("%d", x%2);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	int n;
	scanf("%d", &n);
	D(n);
	return 0;
}

 

  사이트의 답과 비슷했다.

    5번 문제   

 

 


    내가 풀이한 답   

 

 4번 문제와 똑같은 방법으로 풀었고 단순히 인접행렬을 인접리스트 방식으로 바꾸었다. 문제에서 입력 예제를 인접리스트로 나타내면 다음과 같다. 각각의 벡터들이 다른 인덱스값을 가지고 있고 인덱스 하나에 두 개의 값이 들어 있다. 하나는 간선으로 연결될 종점과 나머지 하나는 가중치 값이다. 

 

 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
 
vector<pair<int, int> > map[21];
vector<int> check(21);
int n, minValue = 77777, temp = 0;
 
int dfs(int v){
	if(v==n) {
		if(minValue > temp) minValue = temp;
	}
	else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i].first] == 0){
				check[map[v][i].first] = 1;
				temp += map[v][i].second;
				dfs(map[v][i].first);
				check[map[v][i].first] = 0;
				temp -= map[v][i].second;
			}
		}
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b, c; 
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b >> c;
		map[a].push_back({b, c});
	}
	
	check[1] = 1;
	dfs(1);
 
	cout << minValue;
	return 0;
}

 

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

#include<stdio.h>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;	
int ch[30], cnt=0, n, cost=2147000000;
vector<pair<int, int> > map[30];
 
void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<cost) cost=sum;
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i].x]==0){
				ch[map[v][i].x]=1;
				DFS(map[v][i].x, sum+map[v][i].y);
				ch[map[v][i].x]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b, c));
	}
	ch[1]=1;
	DFS(1, 0);
	printf("%d\n", cost);
	return 0;
}

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

7. 부분집합(DFS 완전탐색)  (0) 2020.10.22
6. 전위순회, 중위순회, 후위순회  (0) 2020.10.21
4. 최소비용(DFS : 인접행렬)  (0) 2020.09.23
3. 경로 탐색(DFS : 인접리스트 방법)  (0) 2020.09.23
2. 미로탐색(DFS)  (0) 2020.09.23

    4번 문제   

 


    내가 풀이한 답   

 

 앞에서 풀었던 경로 탐색에서 조금 변형된 문제라고 생각했다. 기존에는 간선에 1 값을 넣었는데 1 값 대신에 가중치 값을 넣었고 temp 변수를 하나 선언하고 종점에 도달하기 전까지 더해서 종점에 도착하면 최솟값과 비교하는 것을 생각했다. 주의할 점은 아래 그림에서 두 번째 경로를 찾을 때 2-3, 3-4번으로 가는 가중치 값을 빼주는 것처럼 check값이 0으로 변할 때 temp에 가중치값도 빼줘야 한다. 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
int map[21][21], check[21], n, minValue=77777, temp=0;
 
int dfs(int v){
	if(v==n){
		if(minValue > temp) minValue = temp;
	}
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i]!=0 && check[i] == 0){
				check[i] = 1;
				temp += map[v][i];
				dfs(i);
				check[i] = 0;
				temp -= map[v][i];
			}
		}
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b, c;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b >> c;
		map[a][b] = c;
	}
 
	check[1] = 1;
	dfs(1);
 
	cout << minValue;
	return 0;
}

 

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[30][30], ch[30], n, cost=2147000000;	
 
void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<cost) cost=sum;
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]>0 && ch[i]==0){
				ch[i]=1;
				DFS(i, sum+map[v][i]);
				ch[i]=0;
			}
		}
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a][b]=c;
	}
	ch[1]=1;
	DFS(1, 0);
	printf("%d\n", cost);
	
	return 0;
}

 

 사이트의 답은 sum 값을 dfs 파라미터 인자로 넘겨주고 stack의 특성을 이용해서 sum 값이 stack에 저장되도록 하였다. 

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

6. 전위순회, 중위순회, 후위순회  (0) 2020.10.21
5. 최소비용(DFS : 가중치 방향그래프 인접리스트)  (0) 2020.09.23
3. 경로 탐색(DFS : 인접리스트 방법)  (0) 2020.09.23
2. 미로탐색(DFS)  (0) 2020.09.23
1. 경로 탐색(DFS)  (0) 2020.09.22

    3번 문제   

 

 


    내가 풀이한 답   

 

 논리적인 흐름은 바뀌지 않고 자료 구조만 바뀌었다. 기존에 이차원 배열이었던 것을 21개의 벡터로 선언하였고 방문 체크를 위한 일차원 배열도 21 크기의 벡터 하나를 선언하였다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> map[21], check(21);
int n, cnt=0;
 
void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i]]==0){
				check[map[v][i]] = 1;
				dfs(map[v][i]);
				check[map[v][i]] = 0;
			}
		}
	}
}
 
int main() {
	freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a].push_back(b);
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
 
	return 0;
}

 

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

#include<stdio.h>
#include<vector>
using namespace std;
int ch[30], cnt=0, n;		
vector<int> map[30];
void DFS(int v){
	int i;
	if(v==n){
		cnt++;
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i]]==0){
				ch[map[v][i]]=1;
				DFS(map[v][i]);
				ch[map[v][i]]=0;
			}
		}
	}
}			
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	ch[1]=1;
	DFS(1);
	printf("%d\n", cnt);
	return 0;
}

 

 

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

6. 전위순회, 중위순회, 후위순회  (0) 2020.10.21
5. 최소비용(DFS : 가중치 방향그래프 인접리스트)  (0) 2020.09.23
4. 최소비용(DFS : 인접행렬)  (0) 2020.09.23
2. 미로탐색(DFS)  (0) 2020.09.23
1. 경로 탐색(DFS)  (0) 2020.09.22

    2번 문제   

 


    내가 풀이한 답   

 

 문제에서는 7 X 7 형태로 정해져 있었지만 이해를 위해 3 X 3을 기준으로 생각을 해보았다. 한 좌표에서 위, 아래, 오른쪽, 왼쪽을 접근하려면 더 큰 인덱스가 필요했다. 그 결과 (N+2) X (N+2) 형태면 가능하다고 보았다. 아래 그림에서 도착점까지 갈 수 있는 방법은 총 두 가지고 그 중 한 가지의 시퀀스는 다음과 같다. →, ↓, ←, ↑ 순서로 탐색한다고 가정했다.

 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
int map[9][9], check[9][9], cnt = 0;
int x[4] = {1, 0, -1, 0};
int y[4] = {0, 1, 0, -1};
 
void dfs(int a, int b){
	int xx, yy, i;
	if(a==7 && b==7) cnt++;
	else {
		for(i=0; i<4; i++){
			xx = x[i] + a;
			yy = y[i] + b;
			
			if(xx < 1 || yy < 1 || xx > 7 || yy > 7) continue;
			if(map[xx][yy] == 0 && check[xx][yy] == 0){
				check[xx][yy] = 1;
				dfs(xx, yy);
				check[xx][yy] = 0;
			}
		}
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i, j;
	
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			cin >> map[i][j];		
		}
	}	
	
	check[1][1] = 1;
	dfs(1, 1);
	
	cout << cnt;
	
	return 0;
}

 

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

#include<stdio.h>
int map[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;
 
void DFS(int x, int y){	
	int xx, yy, i;
	if(x==7 && y==7){
		cnt++;
	}
	else{
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1 || xx>7 || yy<1 || yy>7)
				continue;
			if(map[xx][yy]==0 && ch[xx][yy]==0){
				ch[xx][yy]=1;
				DFS(xx, yy);
				ch[xx][yy]=0;
			}		
		}
	}
}
 
int main(){
	freopen("input.txt", "r", stdin);
	int i, j;
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

 

 

 

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

6. 전위순회, 중위순회, 후위순회  (0) 2020.10.21
5. 최소비용(DFS : 가중치 방향그래프 인접리스트)  (0) 2020.09.23
4. 최소비용(DFS : 인접행렬)  (0) 2020.09.23
3. 경로 탐색(DFS : 인접리스트 방법)  (0) 2020.09.23
1. 경로 탐색(DFS)  (0) 2020.09.22

    1번 문제   

 

 


    내가 풀이한 답   

 

 문제에 있는 예제는 다음과 같은 과정을 거친다. check 배열을 통해 이미 접근한 노드에 다시 접근하는 것을 방지하고 dfs 재귀 함수를 호출하였다.

 

 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
int map[21][21], check[21], n, cnt=0;
 
void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i] == 1 && check[i] == 0){
				check[i] = 1;
				dfs(i);
				check[i] = 0;
			}
		}
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a][b] = 1;
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
	return 0;
}

 

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

<경로도 함께 출력하는 코드>
#include<stdio.h>	
int map[30][30], ch[30], cnt=0, n, path[30];
void DFS(int v, int L){
	int i, j;
	if(v==n){
		cnt++;
		for(j=0; j<L; j++){
			printf("%d ", path[j]);
		}
		puts("");
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]==1 && ch[i]==0){
				ch[i]=1;
				path[L]=i;
				DFS(i, L+1);
				ch[i]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, j, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	ch[1]=1;
	path[0]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

 

 

'알고리즘 & 자료구조 > 그래프' 카테고리의 다른 글

6. 전위순회, 중위순회, 후위순회  (0) 2020.10.21
5. 최소비용(DFS : 가중치 방향그래프 인접리스트)  (0) 2020.09.23
4. 최소비용(DFS : 인접행렬)  (0) 2020.09.23
3. 경로 탐색(DFS : 인접리스트 방법)  (0) 2020.09.23
2. 미로탐색(DFS)  (0) 2020.09.23

    4번 문제   

 


    내가 풀이한 답   

 

 장애물이 없는 경우와 장애물이 있는 경우를 살펴보면 장애물이 없을 때 (1, 1)에서 (3, 3)까지 갈 수 있는 방법은 6가지이고 장애물이 있을 때에는 2가지이다. 

 

 한 칸 아래 또는 한 칸 오른쪽으로 갈 수 있으므로 점화식은 f(m, n) = f(m-1, n) + f(m, n-1)이다. 장애물 같은 경우는 갈 수 있는 경우의 수가 0이므로 0으로 설정해준다. 

 

 

#include <string>
#include <iostream>
#include <vector>
using namespace std;
 
int a[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0; i<puddles.size(); i++){
        a[puddles[i][0]][puddles[i][1]] = -1;
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(i==1 && j==1) a[i][j] = 1;
            else if(a[i][j] == -1) a[i][j] = 0;
            else a[i][j] = (a[i-1][j] + a[i][j-1])%1000000007;
        }
    }
    return a[m][n];
}

 

 

 결과는 통과하였다.

 

'알고리즘 & 자료구조 > 동적 계획법' 카테고리의 다른 글

6. 가방 문제 (Knapsack)  (0) 2020.10.23
5. 가방 문제 (Knapsack)  (0) 2020.10.23
3. 정수 삼각형  (0) 2020.09.21
2. 알리바바와 40인의 도둑  (0) 2020.09.21
1. 네트워크 선 자르기  (1) 2020.09.21

    3번 문제   

 


    내가 풀이한 답   

 

 Bottom-up 방식으로 접근하였고 2번 알리바바와 40인의 도둑과 매우 비슷한 유형의 문제라고 생각했다. 정수 삼각형 역시 경우의 수를 생각해 보았다. 

 

 첫 번째는 보라색 부분과 같이 오른쪽 대각선으로만 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 해당 위치의 값을 더해주었다.

 

 두 번째는 하늘색 부분가 같이 왼쪽 대각선으로만 올 수 있는 경우였다. 이는 위쪽 값과 해당 위치의 값을 더해주었다.

 

 마지막으로는 오른쪽과 왼쪽 대각선으로 둘 다 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 위쪽 값 중 제일 작은 값과 해당 위치의 값을 더해주었다.  

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int arr[500][500];
int solution(vector<vector<int>> triangle) {
    int i, j, ans=0;
    for(i=0; i<triangle.size(); i++){
        for(j=0; j<triangle[i].size(); j++){
            if(i==0 && j==0) arr[i][j] = triangle[i][j];
            else if(j==triangle[i].size()-1) arr[i][j] = arr[i-1][j-1] + triangle[i][j];
            else if(j==0 && i!=0) arr[i][j] = arr[i-1][j] + triangle[i][j];
            else arr[i][j] = max(arr[i-1][j-1], arr[i-1][j]) + triangle[i][j];
        }
    }
    for(i=0; i<triangle[triangle.size()-1].size()-1; i++){
        ans = max(ans, arr[triangle.size()-1][i]);
    }
    return ans;
}

 

 

 결과는 통과하였다.

 


    다른 사람들의 풀이   

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<vector<int>> triangle) {
 
    //바닥부터 큰 값의 수를 윗 칸에 더해나간다
    for(int i = triangle.size()-2; i > -1; i--){
        for(int j = 0; j <= i; j++){
            triangle[i+1][j] > triangle[i+1][j+1] ? triangle[i][j] += triangle[i+1][j] : triangle[i][j] += triangle[i+1][j+1];
        }
    }
 
    return triangle[0][0];
}

 

 제일 끝 부분부터 큰 값의 수를 더해간다는 것이 인상 깊었다. 전혀 생각지도 못한 풀이였다.

 

 

'알고리즘 & 자료구조 > 동적 계획법' 카테고리의 다른 글

6. 가방 문제 (Knapsack)  (0) 2020.10.23
5. 가방 문제 (Knapsack)  (0) 2020.10.23
4. 등굣길  (0) 2020.09.22
2. 알리바바와 40인의 도둑  (0) 2020.09.21
1. 네트워크 선 자르기  (1) 2020.09.21

티스토리툴바