문제 난이도GOLD II (문제 링크)   풀이두 노드 간의 최장 경로인 트리의 지름을 구하는 문제이다. 모든 경우의 수를 구해서, 가장 큰 값을 찾아야하기 때문에 DFS에 적합하다. DFS 구현은 단순하니 이를 통해 문제를 쉽게 해결할 수 있다.//dfs 호출부int max = 0;for (int i = 1; i     메모리 초과는 단순 이차원 배열을 통해 각 노드의 경우의 수를 계산했기 때문에 발생했다.이는 리스트로 구현하여 해결하였다.  하지만, 모든 경우의 수를 구하면 시간 초과가 발생하는데, 모든 경우의 수를 구하게 되면 O(V^2)이 되며, 문제 조건에서 V가 100,000까지이기 때문에 최적화할 수 있는 방법이 필요하다. 임의의 노드 x에서 최장 경로 노드를 DFS를 통해 구했고, 이를 y..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 완전탐색 문제를 처음으로 외부 검색 없이 혼자 해결한 문제... 고생의 노력이 드디어 빛을 조금 본 것 같다. 1. boolean타입의 이차원 배열 선언 - 해당 칸이 숫자일 경우 true처리 2. dfs메서드에서 한번 탐색이 끝나서 list.add가 되는 경우는 무인도끼리 연결이 되지 않을 때, 즉 해당 섬의 연결이 끝났을 때가 될 수 있게 조건을 줬다. public void dfs(St..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [알고리즘] 깊이 우선 탐색(DFS) [알고리즘] 깊이 우선 탐색(DFS) 깊이 우선 탐색 ( Depth-First Search ) 루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 1. 모든 노드를 방문하고자 하는 경우에 사용한다. 2. 단순 검 mag1c.tistory.com 프로그래머스 기준 전반적인 2레벨 문제나, 적당한 3레벨문제 정도..

깊이 우선 탐색 ( Depth-First Search )루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징1. 모든 노드를 방문하고자 하는 경우에 사용한다.2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다.3. 검색이 아닌 순회를 할 경우 많이 사용한다.공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다.미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.  장점1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.2. 목표 노드가 깊은 단계에 있을 ..