종만북에서 본 적이 있는 유형이라 쉽게 푼 편이다. 이분트리 탐색의 경우에는 재귀를 활용해줘서 처리해주면 된다. 부분과 전체를 보면서 코드를 구현할 수 있어야 한다. 이 문제를 요약하면 전위 순회를 후위 순회로 돌려야하는 것이다. 이분트리를 보면 각 노드를 기준으로 왼쪽은 자신보다 더 작고, 오른쪽은 자신보다 크다. 이러한 성질은 전체적으로 보아도 성립하고 최소 단위로 보아도 성립한다. 즉, 전위 순회를 한 데이터를 기준으로 자신보다 큰 숫자가 나올 때 그것이 오른쪽 노드의 시작을 의미함을 이해할 수 있다. 그러므로 자신보다 큰 숫자가 어느 시점에 나오는지를 확인하고 그것을 기준으로 왼쪽과 오른쪽 노드를 구분하면 된다. 후위 순회의 경우, 이 과정에서 자식 노드의 왼쪽과 오른쪽을 출력하고 자기자신을 출력..

이 문제의 경우에는 사실 트리보다는 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..

처음에는 이중배열을 만들어서 1번부터 node를 설정해주는 방향으로 진행하였다. 하지만, 숫자가 십만이므로 이렇게 사용하게 되면 100000 * 100000 * 4 = 40G(10^9 바이트가 1기가이므로) 가 나오고 메모리 초과가 뜬다. 이를 해결하기 위해 골똘히 고민해보니까 가질 수 있는 노드들의 갯수가 제한되어있으므로 해당 노드들만 저장하면 된다는 것을 파악하였다. 그리고 visited를 사용하여 방문한 노드들을 따로 제거해주면 상위 노드를 다시 방문하는 일은 발생하지 않는다. 위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; int visited[100001] = {0}; int par..

이 문제에서 어차피 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..