mondegreen

[Part2-Chapter04-Clip04] - 백준 14267 회사 문화 1상사가 칭찬을 받으면 직속 부하를 연쇄적으로 칭찬하기 때문에 방향이 없는 그래프인 트리 구조를 활용하면 된다. 직속으로 타고 내려가다가 가장 말단 사원까지 점수를 더해줘야 하기 때문에 DFS 방식으로 점수를 더해주는 방식으로 구현한다. 먼저 입력값을 받아주는데 각 직원의 직속 상사를 입력할 때, 입력받는 순서인 인덱스가 '부하'이고 입력 받는 값이 '상사'이다. ArrayList를 원소로 가지는 배열을 생성해서 배열의 인덱스는 상사, 그 원소인 리스트는 연결된 부하로 값을 입력하면 트리 탐색이 가능한 형태가 된다. 이렇게 입력 받고 나면 칭찬을 순서대로 받아주면서 직속 부하들에게까지 점수를 입력하는데 이 때, 칭찬을 받을 때마다..

[Part2-Chapter04-Clip02]- 백준 11725 트리의 부모 찾기트리도 그래프의 일종이다. 단, 순환이 없는 그래프이다. 그래프 문제를 풀 때와 마찬가지로 인접 리스트를 선언하고 간선의 양 끝 정점을 리스트에 담아줬다. 부모를 찾는 함수를 구현하는 데 약간 어려움을 겪었다. 정점들을 연결된 순서대로 타고 가는데 루트 노드인 1부터 시작해서 따라가다 보면 직전의 정점이 즉, 나를 호출한 정점이 부모가 되는 로직이다. 이미 방문한 경우는 제외하고 자식 노드를 계속 찾아나가면서 자식 노드를 찾을 때마다 정답 배열에 부모인 직전 정점을 넣어주면 문제를 해결할 수 있다.package BaekJoon.tree;import java.util.ArrayList;import java.util.Scanner..

[정답코드] 인접리스트에 매몰되었음... 해시 맵을 우선순위 큐와 조합해서 유사하게 구현 가능하며 정렬까지도 한 번에 해결해 줌. 재귀가 끝나는 순서대로 답에 담기기 때문에 역순처리 해주기 import java.util.*; class Solution { public static ArrayList answer; public static HashMap tks; public String[] solution(String[][] tickets) { answer = new ArrayList(); tks = new HashMap(); for(String[] ticket : tickets){ tks.putIfAbsent(ticket[0], new PriorityQueue()); tks.get(ticket[0]).ad..

재귀..재귀..진짜 왜 재귀적 머리가 안 돌아가는지.. 한참 고민하고 푼 문제이다. 일단 타겟을 찾는 것보다 어쨋든 답이 나오는 문제라면 빼주어야 하는 값을 찾기로 한다. 오래 걸린 부분은 현재 이 숫자를 선택하느냐 마느냐라는 부분을 어떤 방식으로 구현하는 것인지였다. 아래와 같이 선택 여부에 따라 dfs를 나누어 실행해주고 만약 더한 값이 찾고자 하는 값보다 크면 바로 return해 버리는 방식으로 구현했다. class Solution { private static int find, answer; public int solution(int[] numbers, int target) { answer = 0; int total = 0; for(int i =0; i find) return; if(thisNum..

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다. 아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정..

- 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 엄청난 시간과 메모리이다. DFS 문제를 푼 지 오래되었지만 찾아보지 않고 직접 구현해보고자 했다. 인접배열로 만들 경우 당연 n과 m의 크기 때문에 메모리를 초과할 것 같았고 어차피 배열로 순회하면 시간도 초과해버린다고 생각했다. 정점에 비해 간선이 적을 경우에는 배열보다 인접리스트를 쓰는 것이 유리하다고 기억했고 이를 활용해 구현했다. 순회하는 정점의 순서대로 값을 넣기 위해 order 배열을 생성하고 idx를 dfs 함수를 호출할 때마다 하나씩 증가시켜 값으로 넣도록 처리했다. 처음에는 dfs인자에 담아서 처리하려 했는데 같은 정점에서 뻗어나가는 간선의 경우 동일한 idx를 갖게 되어 순서가 중복되는 문제가 발생했었다. 이 코드가 최적인 것 ..

깊이우선탐색의 개념 1) 루트 노드(또는 임의의 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 직전의 갈림선이 있는 정점을 되돌아가야 하기 때문에 재귀적으로 구현하거나, 후입선출 구조의 스택을 활용 ; 시작 정점의 한 방향으로 갈 수 있는 가장 깊은 경로까지 탐색하다가 끝을 만나면 직전의 갈림선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 탐색하는 방법 깊이우선탐색의 특징 1) 자기 자신을 호출하는 순환 알고리즘의 형태이다. 2) 위와 같은 이유로 방문한 노드는 그 여부를 반드시 검사해야 무한 루프에 빠지지 않는다. 3) 전위 순회, 중위 순회, 후위 순회 모든 형태의 트리 순회는 모두 DFS의 한 종류이다. 4) 인접 행렬 또는 ..