트리6 [프로그래머스] 150367번 - 표현 가능한 이진트리 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/150367 문제 설명 당신은 이진트리를 수로 표현하는 것을 좋아합니다. 이진트리를 수로 표현하는 방법은 다음과 같습니다. 이진수를 저장할 빈 문자열을 생성합니다.주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.문자열에 저장된 이진수를 십진수로 변환합니다.이진트리에서 .. 2025. 2. 22. [소프티어] 6251번 - 업무 처리 [Java] https://softeer.ai/practice/6251 1. 아이디어 각 직원에 대해 왼쪽 직원한테 받은 업무와 오른쪽 직원한테 받은 업무를 구분해야 한다. 이를 위해 두 개의 Queue를 갖는 노드 클래스를 활용했고 주어진 트리의 루트를 1로 설정한 후 비트마스킹을 활용했다. 업무의 전달은 부서장부터 말단 직원 순으로 진행된다는 점에 주의해야한다.2. 문제풀이 완전이진트리인데 말단 직원과 부서장까지의 올라가는 거리가 같으면 포화이진트리가 된다. 이를 통해 가장 왼쪽 말단 직원의 번호와 가장 오른쪽 말단 직원의 번호를 비트마스킹으로 구해서 변수로 저장했다. 이후 말단 직원에게 업무들을 부여했다. R일까지의 반복은 부서장 일처리 -> 중간 직원 일처리 -> 말단 직원 일처리 순서로 진행되며 역시 비트.. 2025. 2. 6. [백준] 14267번 - 회사 문화 1 [Java] https://www.acmicpc.net/problem/14267 1. 아이디어 각 칭찬마다 직원들의 칭찬 수치를 갱신하면 시간 초과가 발생한다. 각 직원마다 최초로 칭찬을 받은 경우 칭찬 수치를 더한 후 한번에 계산하는 방식으로 해결할 수 있다.2. 문제풀이 Bottom-Up 다이나믹 프로그래밍과 DFS 알고리즘으로 해결이 가능했는데 다이나믹 프로그래밍은 주어진 직속상사 정보를 바로 활용해서 현재 직원의 칭찬 수치는 현재 직원이 최초로 받은 칭찬 수치의 합과 현재 직원의 부모 직원이 받은 칭찬 수치이다. 상사의 번호가 직원의 번호보다 항상 작아서 해당 방식으로 해결할 수 있었다. DFS는 그냥 사장부터 탐색하며 파라미터로 칭찬 수치의 합을 들고 다니면 간단하게 해결할 수 있다.3. 코드 packag.. 2025. 2. 6. [백준] 1991번 - 트리 순회 [Java] https://www.acmicpc.net/problem/1991 1. 아이디어 트리에 대한 전위 순회, 중위 순회, 후위 순회를 구현하는 문제로 전위 순회는 현재 노드를 방문한 후 왼쪽 자식, 오른쪽 자식 순으로 방문하고, 중위 노드는 왼쪽 자식을 방문 후 현재 노드를 방문하고 오른쪽 자식을 방문하고, 후위 순회는 왼쪽 자식을 방문하고 오른쪽 자식을 방문하고 현재 노드를 방문한다. 이를 재귀적으로 구현하면 해결할 수 있다.2. 문제풀이 출력을 위해 전역 StringBuilder를 활용했고 왼쪽 자식의 알파벳, 오른쪽 자식의 알파벳을 갖는 Node 클래스를 활용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private.. 2025. 2. 6. [백준] 1068번 - 트리 [Java] https://www.acmicpc.net/problem/1068 1. 아이디어 트리의 루트부터 DFS 알고리즘으로 순회를 하며 리프 노드면 1을 반환하도록 구현했다.2. 문제풀이 DFS 메서드에서 리프 노드인지 판단하는 boolean 변수를 활용해 자식 노드로 이동이 가능하면 리프 노드가 아니므로 자식 노드를 루트로 하는 트리에서 얻은 리프 노드의 수를 반환하고 자식 노드로 이동이 불가능하면 리프 노드이므로 1을 추가로 반환하도록 구현했다. 루트 노드 하나만 존재하는 트리도 리프 노드가 1개인 점에 주의해야했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int N; private static in.. 2025. 2. 4. [백준] 11725번 - 트리의 부모 찾기 [Java] https://www.acmicpc.net/problem/11725 1. 아이디어 각 노드의 부모를 저장하는 p 배열을 활용한 BFS, DFS로 해결할 수 있다.2. 문제풀이 BFS, DFS 모두 인접 리스트에서 인접 노드를 탐색하도록 구현이 되는데 이때 트리의 루트부터 탐색 시 다음 노드가 현재 노드의 자식이 됨을 활용했다. p 배열에서 인덱스 번호를 노드 번호, 값을 부모 노드의 번호를 저장하도록 한 후 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { public static void main(String[] args) throws IOException { BufferedReader .. 2025. 2. 3. 이전 1 다음
