트리

📖 문제 https://www.acmicpc.net/problem/20364    💡  풀이 방식• 트리필요 자료구조- 점유된 땅의 수 저장하는 int형 배열- 점유되었는지 상태를 표시할 boolean형 배열  1. 땅 개수 N과 오리 수 Q를 입력받는다.2. i번째 오리가 원하는 땅 번호를 입력받는다.3. 2에서 입력받은 오리가 원하는 땅 번호를 갈 수 있는지 확인해 출력한다.  - 원하는 땅에서 1까지 거슬러 올라오며(/2) 점유된 상태인지 확인한다.    ㄴ 점유된 상태인 경우, 점유된 땅의 번호를 정답으로 출력한다.    ㄴ 정답이 초기값 0에서 바뀌지 않은 경우, 해당 번호의 땅을 점유 처리한다.   🔺 코드1234567891011121314151617181920212223242526272..

📖 문제 https://www.acmicpc.net/problem/1967  💡  풀이 방식• DFS (트리)1. 2차원 인접 리스트 배열을 만들어 정보를 입력받는다. (양방향으로!)2. 1~N번의 모든 노드에서 DFS를 수행해 거리(가중치들의 합 = 트리의 지름)를 계산한다.for(int i = 1 ; i     [DFS 함수]현재 정점과 연결된 모든 점을 방문하며 가중치를 더하고, 이를 최댓값과 비교해 정답을 가장 큰 값으로 갱신한다.private static void dfs(int idx, int sum) { answer = Math.max(answer, sum); for(Node next : list[idx]) { if(!visited[next.idx]) { ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS / BFS + 그리디 필요 자료구조 - 인접 정점 정보 저장할 ArrayList 배열 - 정점 방문 표시할 boolean형 배열 - 가중치 정보 저장할 long형 배열 1. 배열 a의 전체 합한 값이 0인지 확인한다. 0이 아니라면 -1을 리턴한다. 2. 인접 정보를 저장할 ArrayList 배열을 생성해 인접한 값들 정보를 저장한다. 3. 방문 표시 배열과 DFS를 통해 leaf 노드까지 쭉 탐색했다가 차례대로 올라온다. (탐색 방향 : 위에서 아래) 4. 부모 정점은 자식..

🔺 문제 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.*; import java.io.*; public class Main{ public static void ma..

📍 정의 및 특징 사이클이 없다 트리는 그래프 구현 방식을 이용할 수 있고, 탐색 역시 그래프 알고리즘을 사용할 수 있다. - 예 : 이진 트리, 이진 탐색 트리, 힙 📍 트리 관련 알고리즘 종류 - 트리의 순회 (전위, 중위, 후위) - 트리의 레벨 순회 - 트리의 높이 계산 - 트리의 최소 공통 조상(LCA) ➕ 예제 - 트리에서 각 노드의 부모 노드 구하기 [백준/JAVA] 11725번: 트리의 부모 찾기 🔺 문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 bono039.tistory.com - 트리에서 리프 노..

🔺 문제 11438번: LCA 2첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net  🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117imp..

🔺 문제 11437번: LCA첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net  🔺 코드- 틀림 (시간 초과)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798import java.util.*;import java.io.*; public class..

🔺 문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.util.*; import java.io.*; public class Main { static int[][] tree; pub..

🔺 문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 import java.util.*; import java.io.*; public class Main { static in..