HS_development_log

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 접근방법이 꽤 어려웠던문제. 포스트오더와 인오더의 특징을 잘 활용해야지 풀 수 있었다. 포스트오더의 특성상 맨 마지막에 오는것이 루트이다. 인오더는 루트를 기준으로 왼쪽 오른쪽이 나뉜다. 따라서 포스트오더로 루트를 찾고 인오더로 왼쪽 오른쪽 노드를 찾아서 계속 작은 트리로 노드를 쪼개서 프리오더를 해주면 된다. 알고리즘 포스트오더의 끝을 루트로 정하고 프리오더로 답을 출력해야하므로 일단 출력한다. 루트를 기준으로 인오더..

문제 https://programmers.co.kr/learn/courses/30/lessons/42892?language=java 코딩테스트 연습 - 길 찾기 게임 | 프로그래머스 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 트리 순회 문제. BST 구현방식과 유사하다. BST와 같은방식으로 구현한뒤 순회 알고리즘 x축,y축 그리고 노드번호를 갖는 Node 클래스를 만들고 배열을 생성한다 y 좌표를 기준으로 내림차순으로 정렬한다 x 좌표를 기준으로 작으면 왼쪽, 크면 오른쪽으로 재귀적으로 탐색해서 트리 구성 순회 결과 리턴 소스코드 및 설..

자바를 이용한 세그먼트 트리의 기본구조입니다. 이진트리 구조로 구현되었습니다. 구간합을 예시로 들어서 구현했습니다. 세그먼트 트리 초기화 예를 들어 [ 1 , 2 , 3 , 4 , 5 , 6 ] 의 배열을 원소로갖는 세그먼트 트리의 모습은 아래 그림처럼 나와야합니다. 아래 코드로 이러한 모습이 구현이 가능합니다. public int init(int start, int end, int node) { if(start == end) { /* 리프노드이거나 자식노드들이 구간합이 모두구해졌을 경우 */ return tree[node] = arr[start]; /* 구간합 트리에 넣어준다 */ } /* 반씩 나눠서 재귀적으로 자식노드들의 구간합을 구해준다 */ int mid = (start+end)/2; retur..

자바를 이용한 트리의 기본구조 입니다. 이진트리의 구조가 아닙니다. 하나의 노드가 여러개의 자식노드를 가질 수 있도록 코딩했습니다. 소스코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.util.*;public class Tree { public static void main(String[] args) { Node root = new Node("1"); Node n2 = new Node("2"); Node n3 = new Node("3"); Node n4 = new Node("4"); Node n5 = new Node("5"); root.add(n2); root.add(n3); r..