처음에는 이중배열을 만들어서 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++){ ..

이 문제의 경우는 경우의 수가 얼마 존재하지 않기 때문에 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..

이 문제를 보고 set 자료구조를 이용해야되는 것을 인지할 수 있어야 한다. 왜냐하면, 일단 vector나 array처럼 index를 기준으로 찾는 것이 아니라 문자를 기준으로 찾는 것이고 문자열만 판단하면 되므로 set 자료구조를 이용하면 된다. 해당하는 알고리즘을 코드로 구현하면 다음과 같다. #include #include #include #include #include #include #include #include using namespace std; int main(void){ int n, m; cin >> n >> m; set data_store; for(int i = 0; i > temp; data_store.insert(temp); } ..

이 문제의 경우에는 상황 자체는 쉽게 이해할 수 있으나, 구현이 상당히 까다롭다. 그러한 까닭에 디버깅을 한참 시도하였다..(문제를 잘못읽은 영향이 사실 제일 크다.) 이 문제를 풀기위해서 가장 중요한 조건은 2가지의 작동이 순차적으로 진행된다는 것이다. 미세먼지의 확산을 시키고, 공기청정기에 의한 작용을 살펴주면 된다. 단, 미세먼지의 확산이 동시에 되기 때문에 temp array를 하나 만들어줘서 따로 처리해주어야 한다. 그렇지 않으면 배열이 바뀌면서 확산에 영향을 끼치게 되기 때문에 오류가 나올 수 밖에 없다. 또한, 공기청정기에 의한 확산은 일종에 먼지가 이동하는 작업을 거치게 되는데 이전의 배열에 있는 숫자가 이후로 옮겨지는 양상이므로 그것을 저장해주기 위해서 DP방식을 활용하여 진행해주면 된다..

이 문제의 경우에서 가장 중요한 부분은 )가 등장했을 때, 막대기의 끝인지 레이저인지 구분하는 것이다. 레이저는 바로 앞의 값이 (이면 되고, 막대기의 끝은 바로 앞의 값이 )이면 된다. 이것을 기준으로 막대기의 갯수를 체크하면 된다. 단, 막대기의 갯수는 (의 갯수를 통해서 계산할 수 있는데 레이저가 나오거나 막대기의 끝이면 (의 갯수에서 -1을 시켜주면 된다. 해당하는 알고리즘으로 코드를 구현하면 다음과 같다. #include #include #include #include #include #include #include using namespace std; int main(void){ string input_data; cin >> input_data; // input data int len_data..