트리 [BOJ] 4933번 뉴턴의 사과 (Java) 입력 받은 값을 어떻게 트리로 만드느냐를 생각하는 것이 관건. 입력은 포스트오더(후위순회)로 주어진다고 하니 stack을 활용하여 트리 구성 후위순회로 주어진 그래프의 stack 변환 로직 1. 현재 넣으려는 노드(i)가 null이 아니고, 이미 스택에 2개 이상 쌓여있다면 2. 맨 나중에 넣은 노드(stack.pop())가 오른쪽 노드 3. 그 전에 넣은 노드(stack.pop())가 왼쪽... 알고리즘트리알고리즘 [BOJ] 2233번: 사과나무 (Java) ~트리는 어렵다!!!!!!!!!!!!!!!!!~ 전체 로직 1. parent 배열과 root 배열 채우기 Stack을 이용하여 트리 만들기 이진 배열을 비교하며 삭제하고자 하는 노드의 '실제 인덱스' 구하기 2. 가장 가까운 공통 조상 구하기 parent배열을 사용한 재귀 기저조건: 루트까지 왔을 경우 or 다른 노드가 이미 방문 했던 노드를 방문할 경우 로직: 현재 노드 방문처리 후, 부모... 알고리즘트리알고리즘 [백준] 1991번: 트리 순회 문제 풀이 파이썬 문제 링크 풀이 방식 각 노드들을 입력 받아 그래프 형식으로 트리를 저장한다. 전위순회, 중위순회, 후위순회를 각각 함수로 정의한다. 순회 방식에 따라 출력과 재귀함수의 순서를 달리해준다. 전체 코드... beakjoo트리실버1백준재귀beakjoo 617. 이진트리 병합하기 입출력 예시 제약 조건 입력을 예로 들어서 설명한다. 두 트리 모두 루트가 있으므로 root 1 and root2에 의해 new_node=TreeNode(3)이 생성된다. 왼쪽으로 가본다. 부모 노드(값 3)는 그 결괏값을 기다린다. 왼쪽으로 간 분기에서는 val = 1 + 3 = 4인 노드가 생성된다. 왼쪽으로 가본다. 부모 노드(값 4)는 그 결괏값을 기다린다. 왼쪽으로 간 분기에선 ro... 코딩 테스트재귀트리재귀 [WIL] 트리(백준 1068) 트리 구성 예시 부모의 값과 자식(index)를 매핑해서 트리 구성(dictionary) dictionary를 사용한 트리 구성 dictionary 사용 이유 굳이 Tree구조를 만들고 탐색할 필요가 없음 list를 사용할 경우 입력받은 노드의 수(n)만큼의 2차원 배열을 생성해줘야함 방법 1 노드 제거 dictionary(d)의 값 조건 리프 노드라면 1을 반환한다. 자식 노드가 있다면 자... 백준트리1068예외처리1068 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later... 트리코딩 테스트leetcodeleetcode [백준] 4256번 - 트리 Python, Java 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorde... 트리백준treetree [백준] 20924번 - 트리의 기둥과 가지 Python, Java 시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다. 마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다. 기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 위 그림에서 기가 노드는 4번 노드다. 단, 위 그림과 같이 리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 ... 트리백준tree그래프tree 백준 문제 풀이 - 트리의 지름 1967번 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 ... 그래프 탐색깊이 우선 탐색트리그래프 이론그래프 이론 백준) 1068 트리 트리를 구현한다. 애초에 부모를 주어준다고 명시되어 있기때문에 양방향으로 저장할 필요가 없다. 각 부모별로 자식을 저장하는데 지워야되는 노드는 추가하지 않는다. 그다음 트리를 순회하면서 자식노드가 없는애들일때마다 답을 1씩 증가시켜주면 된다. 부모노드를 줄땐 굳이 양방향으로 저장하지 않아도 되고 그러므로 방문한 노드를 저장하는 배열도 필요없을듯. 근데 조건을 좀 잘봐야될듯 싶다.... 백준알고리즘트리백준 BOJ 1761 정점들의 거리 시간 2초, 메모리 128MB input : N(2 ≤ N ≤ 40,000) N - 1개의 줄 : 트리 상에 연결된 두 점과 거리 M(1 ≤ M ≤ 10,000) M개의 줄 : 한 쌍씩 입력 output : 두 노드 사이의 거리를 출력 조건 : N개의 정점으로 이루어진 트리 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력 개선된 LCA를 사용해서 해결하려 하였지만 parent에... LCA트리최소 공통 조상2021.11.092021.11.09 알기쉬운 알고리즘 4주차(1) - 트리 📍 트리 Root Node: 트리 맨 위에 있는 노드 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 이진 트리(Binary Tree)의 특징은 각 노드가 최대 두 개의 자식을 가진다는 것입니다. 완전 이진 트리(Complete Binary Tree)의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다... python힙알고리즘트리python [백준] 트리의 순회 - Python Input으로 in-order(중위 순회)의 결과와 post-order(후위 순회)의 결과를 받고 pre-order(전위 순회)를 구하는 문제 입니다. 그렇기 때문에 중위 순회의 결과는 루트 노드를 기준으로 왼쪽 자식 노드의 결과 리스트 -> 루트 노드 값 -> 오른쪽 자식 노드의 결과 리스트 순으로 출력됩니다. 왼쪽 -> 오른쪽 자식 노드를 탐색한 다음, 마지막으로 루트 노드의 데이터를 탐... 순회트리코딩테스트분할정복분할정복 BOJ 11438 LCA2 시간 1.5초, 메모리 256MB input : N(2 ≤ N ≤ 100,000) N-1개 줄 : 트리 상에서 연결된 두 정점 M(1 ≤ M ≤ 100,000) M개 줄에는 정점 쌍 output : 첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력 조건 : 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력 앞의 LCA를 개선해야만 해결이 가능한 문제이다. 그렇기에 시간 복잡도는 매우 강... LCA트리최소 공통 조상2021.11.092021.11.09 [WEEK03] DAY19 3주차 시작 !! 3주차 알고리즘 문제들의 주제는 그래프 탐색, DFS, BFS, 위상 정렬 이다. 그리고 그래프 탐색의 문제는 트리 문제로 시작되었다! 트리에 관한 정보를 빠르게 공부 ㅎㅅㅎ * 트리 * DFS, BFS 전위 순회 Preorder 중위 순회 Inorder 후위 순회 Postorder 레벨 순위 Levelorder 트리 구조를 코드로 어떻게 옮길 것인지에 대한 문제였다. 코드... BFSDFS트리BFS [백준] 트리의 지름(1967) - Python 따라서 트리를 순회하면서 간선 값을 누적해서 저장하는 방식, 즉 백트래킹을 이용해서 진행합니다. 각 정점마다 리프노드 의 지름 값을 저장하고 각 간선에는 리프노드 로부터 이어지는 누적 간선 값을 저장합니다. 그렇기 때문에 상위 노드로 가는 간선 값에 이전의 간선 값을 누적합니다. 여기서는 간선 세개 (11, 6, 5) 중 11과 6이 차례대로 크기 때문에 지름의 값은 17이 됩니다. key는... 트리코딩테스트코딩테스트 컬렉션 프레임워크와 셋(Set) HashSet<E> TreeSet<E> 중복 불가 순서 유지 불가 equals Object 클래스의 equals 메소드 호출 결과를 근거로 동일 인스턴스를 판단 hashCode set의 해쉬 코드를 반환 Set에서의 동일 인스턴스 hashCode를 통해 동일한 해쉬 코드를 가진 집합에 대해 접근한다. 동일한 해쉬 코드를 가진 집합에 대해 equals 메소드를 통해 동일 인스턴스를 찾는다. -... 해쉬셋자바트리comparatorcomparableJavaHashSet컬렉션트리셋정렬기준셋CollectionTreeSetsetCollection [boj] 215681. 트리와 쿼리 (node.js) 문제 요약 풀이 주어진 무방향 트리에서 '입력된 정점을 루트로 하는 서브트리에 속한 정점의 수를 출력한다' 는 쿼리가 주어질 때, 이 쿼리를 만족하는 결과를 구현하는 문제 루트 노드가 주어진다. 내 풀이 주어진 트리를 입력받은 후, 루트 노드에서 dfs 를 구현한다. 이때 dfs 함수는 노드에 자식 노드가 있는 경우, 자식 노드에서 다시 dfs를 수행한다. dfs 함수를 호출할 때마다 해당 ... 알고리즘DFS트리복습하기재귀함수DFS
[BOJ] 4933번 뉴턴의 사과 (Java) 입력 받은 값을 어떻게 트리로 만드느냐를 생각하는 것이 관건. 입력은 포스트오더(후위순회)로 주어진다고 하니 stack을 활용하여 트리 구성 후위순회로 주어진 그래프의 stack 변환 로직 1. 현재 넣으려는 노드(i)가 null이 아니고, 이미 스택에 2개 이상 쌓여있다면 2. 맨 나중에 넣은 노드(stack.pop())가 오른쪽 노드 3. 그 전에 넣은 노드(stack.pop())가 왼쪽... 알고리즘트리알고리즘 [BOJ] 2233번: 사과나무 (Java) ~트리는 어렵다!!!!!!!!!!!!!!!!!~ 전체 로직 1. parent 배열과 root 배열 채우기 Stack을 이용하여 트리 만들기 이진 배열을 비교하며 삭제하고자 하는 노드의 '실제 인덱스' 구하기 2. 가장 가까운 공통 조상 구하기 parent배열을 사용한 재귀 기저조건: 루트까지 왔을 경우 or 다른 노드가 이미 방문 했던 노드를 방문할 경우 로직: 현재 노드 방문처리 후, 부모... 알고리즘트리알고리즘 [백준] 1991번: 트리 순회 문제 풀이 파이썬 문제 링크 풀이 방식 각 노드들을 입력 받아 그래프 형식으로 트리를 저장한다. 전위순회, 중위순회, 후위순회를 각각 함수로 정의한다. 순회 방식에 따라 출력과 재귀함수의 순서를 달리해준다. 전체 코드... beakjoo트리실버1백준재귀beakjoo 617. 이진트리 병합하기 입출력 예시 제약 조건 입력을 예로 들어서 설명한다. 두 트리 모두 루트가 있으므로 root 1 and root2에 의해 new_node=TreeNode(3)이 생성된다. 왼쪽으로 가본다. 부모 노드(값 3)는 그 결괏값을 기다린다. 왼쪽으로 간 분기에서는 val = 1 + 3 = 4인 노드가 생성된다. 왼쪽으로 가본다. 부모 노드(값 4)는 그 결괏값을 기다린다. 왼쪽으로 간 분기에선 ro... 코딩 테스트재귀트리재귀 [WIL] 트리(백준 1068) 트리 구성 예시 부모의 값과 자식(index)를 매핑해서 트리 구성(dictionary) dictionary를 사용한 트리 구성 dictionary 사용 이유 굳이 Tree구조를 만들고 탐색할 필요가 없음 list를 사용할 경우 입력받은 노드의 수(n)만큼의 2차원 배열을 생성해줘야함 방법 1 노드 제거 dictionary(d)의 값 조건 리프 노드라면 1을 반환한다. 자식 노드가 있다면 자... 백준트리1068예외처리1068 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later... 트리코딩 테스트leetcodeleetcode [백준] 4256번 - 트리 Python, Java 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorde... 트리백준treetree [백준] 20924번 - 트리의 기둥과 가지 Python, Java 시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다. 마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다. 기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 위 그림에서 기가 노드는 4번 노드다. 단, 위 그림과 같이 리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 ... 트리백준tree그래프tree 백준 문제 풀이 - 트리의 지름 1967번 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 ... 그래프 탐색깊이 우선 탐색트리그래프 이론그래프 이론 백준) 1068 트리 트리를 구현한다. 애초에 부모를 주어준다고 명시되어 있기때문에 양방향으로 저장할 필요가 없다. 각 부모별로 자식을 저장하는데 지워야되는 노드는 추가하지 않는다. 그다음 트리를 순회하면서 자식노드가 없는애들일때마다 답을 1씩 증가시켜주면 된다. 부모노드를 줄땐 굳이 양방향으로 저장하지 않아도 되고 그러므로 방문한 노드를 저장하는 배열도 필요없을듯. 근데 조건을 좀 잘봐야될듯 싶다.... 백준알고리즘트리백준 BOJ 1761 정점들의 거리 시간 2초, 메모리 128MB input : N(2 ≤ N ≤ 40,000) N - 1개의 줄 : 트리 상에 연결된 두 점과 거리 M(1 ≤ M ≤ 10,000) M개의 줄 : 한 쌍씩 입력 output : 두 노드 사이의 거리를 출력 조건 : N개의 정점으로 이루어진 트리 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력 개선된 LCA를 사용해서 해결하려 하였지만 parent에... LCA트리최소 공통 조상2021.11.092021.11.09 알기쉬운 알고리즘 4주차(1) - 트리 📍 트리 Root Node: 트리 맨 위에 있는 노드 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 이진 트리(Binary Tree)의 특징은 각 노드가 최대 두 개의 자식을 가진다는 것입니다. 완전 이진 트리(Complete Binary Tree)의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다... python힙알고리즘트리python [백준] 트리의 순회 - Python Input으로 in-order(중위 순회)의 결과와 post-order(후위 순회)의 결과를 받고 pre-order(전위 순회)를 구하는 문제 입니다. 그렇기 때문에 중위 순회의 결과는 루트 노드를 기준으로 왼쪽 자식 노드의 결과 리스트 -> 루트 노드 값 -> 오른쪽 자식 노드의 결과 리스트 순으로 출력됩니다. 왼쪽 -> 오른쪽 자식 노드를 탐색한 다음, 마지막으로 루트 노드의 데이터를 탐... 순회트리코딩테스트분할정복분할정복 BOJ 11438 LCA2 시간 1.5초, 메모리 256MB input : N(2 ≤ N ≤ 100,000) N-1개 줄 : 트리 상에서 연결된 두 정점 M(1 ≤ M ≤ 100,000) M개 줄에는 정점 쌍 output : 첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력 조건 : 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력 앞의 LCA를 개선해야만 해결이 가능한 문제이다. 그렇기에 시간 복잡도는 매우 강... LCA트리최소 공통 조상2021.11.092021.11.09 [WEEK03] DAY19 3주차 시작 !! 3주차 알고리즘 문제들의 주제는 그래프 탐색, DFS, BFS, 위상 정렬 이다. 그리고 그래프 탐색의 문제는 트리 문제로 시작되었다! 트리에 관한 정보를 빠르게 공부 ㅎㅅㅎ * 트리 * DFS, BFS 전위 순회 Preorder 중위 순회 Inorder 후위 순회 Postorder 레벨 순위 Levelorder 트리 구조를 코드로 어떻게 옮길 것인지에 대한 문제였다. 코드... BFSDFS트리BFS [백준] 트리의 지름(1967) - Python 따라서 트리를 순회하면서 간선 값을 누적해서 저장하는 방식, 즉 백트래킹을 이용해서 진행합니다. 각 정점마다 리프노드 의 지름 값을 저장하고 각 간선에는 리프노드 로부터 이어지는 누적 간선 값을 저장합니다. 그렇기 때문에 상위 노드로 가는 간선 값에 이전의 간선 값을 누적합니다. 여기서는 간선 세개 (11, 6, 5) 중 11과 6이 차례대로 크기 때문에 지름의 값은 17이 됩니다. key는... 트리코딩테스트코딩테스트 컬렉션 프레임워크와 셋(Set) HashSet<E> TreeSet<E> 중복 불가 순서 유지 불가 equals Object 클래스의 equals 메소드 호출 결과를 근거로 동일 인스턴스를 판단 hashCode set의 해쉬 코드를 반환 Set에서의 동일 인스턴스 hashCode를 통해 동일한 해쉬 코드를 가진 집합에 대해 접근한다. 동일한 해쉬 코드를 가진 집합에 대해 equals 메소드를 통해 동일 인스턴스를 찾는다. -... 해쉬셋자바트리comparatorcomparableJavaHashSet컬렉션트리셋정렬기준셋CollectionTreeSetsetCollection [boj] 215681. 트리와 쿼리 (node.js) 문제 요약 풀이 주어진 무방향 트리에서 '입력된 정점을 루트로 하는 서브트리에 속한 정점의 수를 출력한다' 는 쿼리가 주어질 때, 이 쿼리를 만족하는 결과를 구현하는 문제 루트 노드가 주어진다. 내 풀이 주어진 트리를 입력받은 후, 루트 노드에서 dfs 를 구현한다. 이때 dfs 함수는 노드에 자식 노드가 있는 경우, 자식 노드에서 다시 dfs를 수행한다. dfs 함수를 호출할 때마다 해당 ... 알고리즘DFS트리복습하기재귀함수DFS