heeStory

https://www.acmicpc.net/problem/15666   수열들을 비교했을 때, 앞에서 부터 비교했을 때 오름차순이 되어야한다.   접근순차적으로 모든 원소를 방문한다고 생각하고 필요없는 부분을 제거하는 백트래킹 가지치기를 하면 된다.순회 원소를 선택할 때, 중복이 없도록 고려하자. 가지 치기만약 1을 선택했다면 다음 원소는 다음 자리 수에 원소부터 골라야한다.  다른 가지에서 중복된 값을 선택하지 않아야 한다. (같은 줄 == depth에서) 전체를 순회하는 재귀 탐색 코드에서 위에 해당하는 가지를 제외시키면 정답이 된다.  코드단순히 전체를 순회한다면 아래와 같은 코드if(depth == M) { for(int n : nums) sb.append(n).append(" "); ..

문제링크:  https://www.acmicpc.net/problem/1967 가중치가 제일 큰 값을 가진 지름을 찾는 문제 문제에서 주어진 조건노드 번호 순서대로 주어짐첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호 접근원은 두 점(말단 노드) 사이 길이이다그 중 제일 긴 노드 두 점을 찾으면 된다DFS를  사용하면 시작 노드에서부터 가장 큰 말단 노드를 찾을 수 있다. 현재 어떤 노드가 제일 큰 노드인지 알 수 없으니 최상위 부모 노드에서 시작하여  가장 큰 말단 노드부터 찾는다.  1번. DFS로 말단 노드 한 점을 찾는다.최상단 노드는 제일 사이즈가 큰 말단 노드가 아니다. 따라서, 최상위 노드에서 경로가 가장 긴(지름이 제일 긴) 노드를 찾자.1번 노드는 그저 처음 탐색을 위한 노..

BFS & DFS 문제를 풀다보면, 메모리 초과가 발생할 때가 있다. 대부분 메모리 초과의 이유는 Stack에 담기는 요소가 계속해서 중복값을 넣고 제대로 필터링을 하지 않아서 발생한 문제이다. Visited 의 위치가 중요하다. 다음 코드를 보자, visited 선언에 따라서 결과가 다르게 반영된다. 자세하게 보자, 첫번째의 경우 만약 , Queue에 Node 1 , 2 , 3, 4 가 들어있는 상황에서 Node 1이 꺼내져서 bfs를 한다고 해보자, 그리고, Node 1 에서 갈 수 있는 Node는 Node 2 , Node 3이라고 하자. Node1 이 bfs를 하면서 Node 2가 당연히 아직 큐에 있으니, Visited[Node2] 는 false 이므로 또 넣게 되는 불상사가 생긴다. 큐에 있는 ..