이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다. 처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다. 하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.) 즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다. 해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; struct node{ vector path_store; }; int checker(node *data_store, in..

대표적인 전위 순회, 중위 순회, 후위 순회를 활용한 탐색이다. 이진트리이므로 구조체(클래스)를 활용하여 좌/우 노드를 저장하고 재귀를 활용하여 방문해주면 된다. 아래 코드들을 익숙하게 활용할 수 있도록 반복할 것 #include #include #include #include #include #include using namespace std; struct node{ char left; char right; }; void first_cycle(node *data_store, char start){ int check_num = start - 'A'; cout > parent >> left >> right; data_store[parent - 'A'].left = left; data_store[parent..

이 문제에서 어차피 0부터 나무의 최대높이까지만 살피면 되는 상황이므로 이분탐색을 활용하여 자르는 높이를 구하는 것이 훨씬 쉽다는 것을 파악하면 된다. 다만, 이 문제를 처음에 풀었을 때 틀렸는데 compare_value가 int의 범위를 넘을 수 있다는 것을 확보하지 못했다. 대략적으로 지금 문제 조건이 간당간당하게 int범위를 넘지 않는 상황이므로 더하다보면 해당 범위를 넘을 수 있다. 이것만 주의해서 코드를 구현하면 다음과 같다. #include #include #include #include using namespace std; int main(void){ int n, m; cin >> n >> m; vector tree_length_store; for(int i = 0; i < n; i++){ ..

일단, count함수는 algorithm에 존재하므로 사용하기 위해서는 상단부에 #include 을 반드시 적어야 한다. 일차원 배열일 경우에는 되게 단순하게 하면 된다. count(배열의 시작지점, 배열의 끝나는 지점, 원하는 숫자) 예를 들어 arr[10]에서 3의 숫자를 센다고 하자 그러면 count(arr, arr + 10, 3)를 사용하면 된다. 단, 다차원배열의 경우에는 이와는 조금 사용법이 다른데 count(&배열의 시작지점, &배열의 시작지점 + 데이터 수, 원하는 숫자) 예를 들어 arr[10][10]에서 3의 숫자를 센다고 하자 그러면 count(&arr[0][0], &arr[0][0] + 100, 3)를 사용하면 된다. 벡터의 경우에는 너무 간단한데 그냥 count(r.begin(),..

일단, memcpy함수는 algorithm에 존재하므로 사용하기 위해서는 상단부에 #include 을 반드시 적어야 한다. 일차원 배열일 경우에는 되게 단순하게 하면 된다. copy(복사할 배열의 시작지점, 복사할 배열의 끝나는 지점, 복사될 배열의 시작하는 지점) 예를 들어 arr[10]을 arr_copy[10]에 옮긴다고 하자 그러면 copy(arr, arr + 10, arr_copy)를 사용하면 된다. 단, 다차원배열의 경우에는 이와는 조금 사용법이 다른데 copy(&복사할 배열의 시작지점, &복사할 배열의 시작지점 + 데이터 수, &복사될 배열의 시작지점) 예를 들어 arr[10][10]을 arr_copy[10][10]에 옮긴다고 하자 그러면 copy(&arr[0][0], &arr[0][0] + ..

이 문제의 경우는 경우의 수가 얼마 존재하지 않기 때문에 3개의 벽을 선택하고 각각의 경우에서 바이러스가 전파하고 남은 영역이 몇개 존재하는지를 체크해주면 된다. 다만, 사용하는 숫자가 0, 1, 2이므로 각각을 구분해 주어야하고 방문을 일일히 체크해주어야해서 조금 귀찮다. 이 문제의 경우는 전파하는 것만 찾으면 되므로 BFS나 DFS나 크게 차이가 존재하지 않는다. 코드로 구현한 결과는 다음과 같다. #include #include #include #include #include using namespace std; int data_store[8][8]; int check_array[8][8]; vector zero_store; int n, m; int max_result_store = -1; void..

DFS, BFS를 처음 배운 입장에서는 좀 까다로운 문제였다. 이 문제를 보고 처음 접근한 방식은, DFS이다. 실제로 구현 방법이 아직까지는 DFS가 재귀로 짜기 쉽기도하고, 두 가지 방법의 근본적인 차이에 대해서 잘 이해하지 못했기 때문이다. 일단, 이 문제를 DFS로 바라보면 안되는 이유에 대해서 정리하자면, 1. 너무 불필요하게 하나의 케이스를 기준으로 건물 양 끝을 오가게 된다. 정확하게 이 문제를 이해해보면, 올라가는 케이스와 내려가는 케이스를 기준으로 해당하는 칸을 갈 수 있는지를 체크하는 것이 중요하다. 그런데, 만약에 해당하는 칸을 가면 참 좋겠지만 가지 못한다면 잘못하면 무한루프에 빠질 가능성이 존재한다. 위 문제에서 최저값이 1층 최고값이 입력에서 제한되어 있는 상황이므로 계속해서 계..

이 문제의 경우에서 기본적인 접근방법은, 자신을 기준으로 위로 올라가는 방향이든 아래로 내려가는 방향이든 구분하지 않고 이동을 한번 하면 촌수가 1 증가한다는 것을 이용하여 그래프를 활용하여 촌수를 계산할 수 있다는 것을 인지하고 풀면 된다. 처음에는 #include #include #include #include using namespace std; int visited[101] = {0}; int dfs(int start, int end, int (&data_store)[101][101]){ if(start == end) return 0; if(visited[start] == 1) return 0; else{ int count = 0; visited[start] = 1; for(int i = 0; i..