4 5 1
1 2
1 3
1 4
2 4
3 4

1 2 4 3
1 2 3 4

5 5 3
5 4
5 2
1 2
3 4
3 1

3 1 2 5 4
3 1 4 2 5

1000 1 1000
999 1000

1000 999
1000 999

bfs는 큐로, dfs는 재귀(스택)으로 출력할 값들을 저장하면 된다.

#include <iostream>
#include <queue>
using namespace std;
#define MAX_VERTEX 1001
short graph[MAX_VERTEX][MAX_VERTEX];
char check_dfs[MAX_VERTEX];
char check_bfs[MAX_VERTEX];

int n ,m, v;
int from, to;

void dfs(int node){
    if(check_dfs[node]){
        return;
    } else{
        check_dfs[node] = 1;
        cout << node << " ";
        for(int i = 1; i <= n; i++){
            if(graph[node][i] && !check_dfs[i])
            dfs(i);
        }
    }

}

void bfs(int node){
    queue<short> q;
    int temp = 0;

    q.push(node);
    check_bfs[node] = 1;

    
    while(!q.empty()){

        temp = q.front();
        q.pop();
        cout << temp << " ";


        for(int i = 1; i <= n; i++){
            if(graph[temp][i] && !check_bfs[i]){
                q.push(i);
                check_bfs[i] = 1;
            }
        }

    }
}

int main(){
    
    cin >> n >> m >> v;

    for(int i = 0 ; i < m ; i++){
        cin >> from >> to;
        graph[from][to]=1;
        graph[to][from]=1;
    }
    dfs(v);
    cout << "\n";
    bfs(v);

    return 0;
}

vertex(정점)과 node는 같은 개념으로 사용하였다.

또한, bfs에서 같은 깊이에 있는 노드들을 작은 수부터 출력하라 하였는데,  애초에 다음 노드 탐색을 for문을 이용하여 1번 노드부터 n번 노드까지 탐색하고 push하였으므로 정렬할 필요는 없다.

6 5
1 2
2 5
5 1
3 4
4 6

2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX 1001

short graph[MAX_VERTEX][MAX_VERTEX]; // adjacency matrix
char check[MAX_VERTEX]; // check visitied node


void dfs(int i,int vertex_num) {
	
	check[i] = 1;
	for (int k = 1; k <= vertex_num; k++) {
		if(graph[i][k] && !check[k])
			dfs(i, k, vertex_num);
	}
	
}

int main() {
	int vertex_num, edge_num;
	int from, to;
	scanf("%d %d", &vertex_num, &edge_num);

	for (int i = 0; i < edge_num; i++) {
		scanf("%d %d", &from, &to);
		graph[from][to] = 1;
		graph[to][from] = 1;  //no direction
	}

	int count = 0;

	for (int i = 1; i <= vertex_num; i++) {
		
		if (!check[i]) {
			count++;
			dfs(i, vertex_num);
		}
		
	}

	printf("%d", count);

}

그래프 유형의 문제가 처음이라 꽤 애먹었는데, 

집합의 개수를 살릴때 그래프 기준이 아니라, 노드를 기준으로 count 해야하고, bfs 혹은 dfs는 연결되어있는 노드에 방문하기 위한 알고리즘이며 어떤 순서로 방문할껀지에 따라 알고리즘이 나뉜다.

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

5
1

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int global_n, global_m;

void record_history_dfs(int** arr, int x, int y) {
	int new_x, new_y;
	arr[y][x] = 0;
	// x ,y+1
	new_x = x;
	new_y = y + 1;
	if (new_y < global_n && arr[new_y][new_x]) {
		record_history_dfs(arr, new_x, new_y);
	}

	// x ,y-1
	new_x = x;
	new_y = y - 1;
	if (new_y >= 0 && arr[new_y][new_x]) {
		record_history_dfs(arr, new_x, new_y);
	}
	// x+1 ,y
	new_x = x + 1;
	new_y = y;
	if (new_x < global_m && arr[new_y][new_x]) {
		record_history_dfs(arr, new_x, new_y);
	}
	// x-1 ,y
	new_x = x - 1;
	new_y = y;
	if (new_x >= 0 && arr[new_y][new_x]) {
		record_history_dfs(arr, new_x, new_y);
	}
}

	int count(int** arr, int m, int n) {
		int total_count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j]) {
					record_history_dfs(arr, j, i);
					total_count++;
				}
			}
		}
		return total_count;
	}

	int main() {
		int size;
		int n, m, k;
		int x, y;
		int** arr = NULL;
		scanf("%d", &size);
		for (int i = 0; i < size; i++) {
			scanf("%d %d %d", &m, &n, &k);
			global_m = m;
			global_n = n;
			arr = (int**)malloc(sizeof(int*) * n);
			for (int j = 0; j < n; j++) {
				arr[j] = (int*)malloc(sizeof(int) * m);
			}
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					arr[j][k] = 0;
				}
			}

			for (int j = 0; j < k; j++) {
				scanf("%d %d", &x, &y);
				arr[y][x] = 1;
			}

			printf("%d\n", count(arr, m, n));

		}
	}

재귀적으로 호출하는 dfs 알고리즘을 사용하였다.

우선 1을 만나면, 해당 좌표 기준 상, 하, 좌 , 우 좌표가 바운더리 내에 존재하는지 확인 후 해당 좌표도 1이라면, 모두 0으로 바꿔주는 작업을 한 후, count를 하는 방향으로 설계하였다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

3
0
1
3

1 0
0 1
1 2

2
6
22

5 8
10946 17711

해당 문제는 다이나믹 프로그래밍 알고리즘 문제로, 탑다운 혹은 바텀업 방식을 선택할 수 있다.

특징으론, 시간이 0.25초로 매우 빠듯하게 설정되어 있으므로, 효율적이로 구현해야 한다.

문제에서 n의 범위가 40까지밖에 되지 않으므로, 바텀업 방식으로 간단하게 구현하였다.

#include <iostream>
#include <stdlib.h>
using namespace std;
int main(){
    int one[41] = {0,};
    int zero[41] = {0,};

    zero[0] = 1;
    one[0] = 0;

    zero[1] = 0;
    one[1] = 1;

    zero[2] = 1;
    one[2] = 1;

    for(int i = 3; i <= 40; i++){
        zero[i] = zero[i-1] + zero[i-2];
        one[i] = one[i-1] + one[i-2];
    }

    int size = 0;
    cin >> size;
    int* user_input = (int*)malloc(sizeof(int)*size);
    for(int i = 0; i < size; i++)
        cin >> user_input[i];
    for(int i = 0; i < size; i++)
        cout << zero[user_input[i]] << " " << one[user_input[i]] << "\n";
}

인덱스가 2인 경우 또한 for문에 넣어도 되지만, 이해를 돕고자 위처럼 분리하여 선언하였다.

결국 n도 n-1, n-2로 분리되므로 1의 개수와 0의 개수는 수마다 고유하다고 생각하면 된다.

5
1
3
8
-2
2

2
2
1
10

1
4000

4000
4000
4000
0

5
-1
-2
-3
-1
-2

-2
-2
-1
2

3
0
0
-1

0
0
0
1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


int compare(const void* a, const void* b) {
	int int_a = *(int*)a;
	int int_b = *(int*)b;

	if (int_a < int_b) return -1;
	else if (int_a > int_b) return 1;
	else return 0;
}

int mean(int* arr, int size) {
	double sum = 0; 
	for (int i = 0; i < size; i++) {
		sum += arr[i];
	}
	return (int)round(sum/size);
}

int median(int* arr, int size) {
	int indexA = 0, indexB = 0;
	int temp[2] = { 0 };
	//sort first

	if (size % 2 == 0) { //even case
		indexA = size / 2 - 1;
		indexB = size / 2;
		temp[0] = arr[indexA];
		temp[1] = arr[indexB];
		return mean(temp, 2);

	}
	else {//odd case
		indexA = size / 2;
		return arr[indexA];
	}
}



int most_num(int* arr, int size) {
	int maxCount = 0, mode = arr[0], count = 1, modeCount = 0; //maxCount : 현재 최고 빈도수, mode = 현재 최빈값, count = 현재 반복수, modeCount = 현재 최빈값 개수

	for (int i = 1; i < size; i++) {
		if (arr[i] ==  arr[i - 1]) { //같은 원소를 발견하면
			count++;  //count + 1
		}
		else { //다른 원소를 발견하면
			if (count > maxCount) { //만약, 빈도수가 더 큰값이면
				maxCount = count; //최고 빈도수를 업데이트
				mode = arr[i - 1]; //최고 빈도수를 가지는 값을 업데이트
				modeCount = 1; //최고 빈도수를 1개로 업데이트 
			}
			else if (count == maxCount) { //같은 빈도수를 가지는 값일 경우, 특히 빈도수가 현재 최고 빈도수값이랑 같을 경우
				if (modeCount == 1) { //최고 빈도수의 개수가 하나일 경우에만
					mode = arr[i - 1]; //최고 빈도수 값을 업데이트, 왜냐하면 두번째로 작은 수를 기록해야기 때문
					modeCount++; //최고 빈도수를 가지는 값의 개수를 업데이트, 2개 이상이므로 이제 기록 안됨
				}
			}
			count = 1; // else 문 마지막 문장으로, 다른 원소를 발견했으므로 count값 초기화
		}
	}
	// Check last element
	if (count > maxCount) { //마지막에 최빈값이 나온 경우
		mode = arr[size - 1];
	}
	else if (count == maxCount && modeCount == 1) { //배열의 끝에 최빈값이 나오는 경우. 끝에 나오는 경우가 아닌 이상 modeCount는 1이 아니다. 왜냐? 위 for문의 else-elseif문에서 해당 경우를 처리했기 때문
		mode = arr[size - 1]; //그 값 리턴
	}
	return mode;
}

int range(int* arr, int size) {
		return arr[size - 1] - arr[0];
}


int main() {
	int size = 0;
	int* arr = NULL;
	
	scanf("%d", &size);
	arr = (int*)malloc(sizeof(int) * size);
	for (int i = 0; i < size; i++) {
		scanf("%d", &arr[i]);
	}

	qsort(arr, size, sizeof(int), compare);

	printf("%d\n",mean(arr, size));
	printf("%d\n",median(arr, size)); //n이 홀수이므로,  arr[size/2] 로 처리하여도 된다
	printf("%d\n",most_num(arr, size));
	printf("%d\n",range(arr, size));

}

최빈값을 구할 때, for문에서 i를 1부터 시작하여 size전까지 돈다.

그리고, 우측값과 좌측값을 비교하여 같은지 여부를 확인하고, (정렬되어 있다) 같은 경우엔 count++, 다를 경우 값을 업데이트 할지 여부를 결정한다. 하지만! 위 for문 로직으로는 배열의 끝에 최빈값이 등장한 경우를 처리하지 못한다.

(i를 기준으로 arr[i]와 arr[i-1]과 다를 경우 변수를 업데이트하는데, 위 경우에는 다른 경우가 없기 때문) 따라서, 해당 경우return하기 전에 조건문으로 한번 더 확인한다.

생각보다 많이 까다로웠던 문제다.

2
1
3
2
3

6
10

해당 문제는 다이나믹 프로그래밍 문제이다.

다이나믹 프로그래밍이란, 

복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방식을 말한다.

수열과 같이 특정한 규칙이 반복되는 경우, 해당 방법으로 해결할수 있다.

다이나믹 프로그래밍 문제를 푸는 방식은 1.바텀업, 2.탑다운 방식으로 총 2가지가 있는데, 

1. 바텀업 방식 -> 반복문을 활용하여, 필요한 정답을 모두 데이터에 저장한 후, 불러옴

2. 탑다운 방식-> 재귀함수를 이용하여, 필요한 값을 기준으로 하나하나 내려가면서(재귀함수를 통해) 더이상 내려갈 필요 없는 부분까지 내려간 후, 위 값을 이용해 다시 올라옴 (재귀함수 원리)

바텀업 방식은, 필요하지 않은 정답까지 모두 불러옴으로 시간과 자원을 낭비하는 단점이 있고

탑다운 방식은 스택 오버플로우 위험성과 재귀 호출의 오버헤드로 인한 단점이 있다. (흔히 재귀함수의 단점) 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int cal(int k, int n) {
	if (k == 0) {
		return n;
	}
	int temp = 0;
	for (int i = 1; i <= n; i++)
		temp += cal(k - 1, i);
	return temp;
}

int main() {
	int size;
	int n, k;
	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d %d", &n, &k);
		printf("%d\n", cal(n, k));
	}
	
	return 0;
}

재귀함수는 직관적이라 이해/작성 하기 쉬움으로, 탑다운 방식으로 작성하였다.

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제 입력 1 복사

13

예제 출력 1 복사

3

경계값을 기준으로 보면, 

1, 1+6, 1+6+12, ... {1+6+12 .. + 6*(n)}와 같은 형식으로 이루어진다.

수가 주어지면, 위 형식의 경계값 중 주어진 수보다 작으면서 가장 가까운 경계값을 찾은 후 이를 이용해 방의 수를 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int num;
	scanf("%d", &num);
    
	if (num == 1) {
		printf("1");
		return 0;
	}
	
	int index = 0;
	int boundary = 1;
	
	while (boundary < num) {
		boundary = boundary + 6 * index++;
	}
	printf("%d", index);

	return 0;
}

1일때는 예외처리가 필요하다.

3
21 Junkyu
21 Dohyun
20 Sunyoung

20 Sunyoung
21 Junkyu
21 Dohyun

구조체를 이용하여 데이터를 저장해야하는데, 멤버로는 가입 순서, 나이, 이름 이 필요하다.

STL을 이용하여 정렬을 수행하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Info{
	int order_of_registration;
	int age;
	char name[101];
} UserInfo;

int compare_UserInfo_age_and_order(const void* a, const void* b) {
	UserInfo* userA = (UserInfo*)a;
	UserInfo* userB = (UserInfo*)b;
	if(userA->age != userB->age)
		return userA->age - userB->age;
	return userA->order_of_registration - userB->order_of_registration;
}


int main() {
	int size = 0;
	scanf("%d", &size);
	
	UserInfo* info_array = (UserInfo*)malloc(sizeof(UserInfo) * size);
	
	for (int i = 0; i < size; i++) {
		info_array[i].order_of_registration = i;
		scanf("%d %s", &(info_array[i].age), info_array[i].name);
	}

	qsort(info_array, size, sizeof(UserInfo), compare_UserInfo_age_and_order);

	for (int i = 0; i < size; i++) {
		printf("%d %s\n", info_array[i].age, info_array[i].name);
	}

	free(info_array);

	return 0;
}