본문 바로가기

트리6

[SWEA - Java] 1232. 사칙연산 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 설명 위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다. 사람들은 사칙 연산을 할때 (9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다.하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다.즉 (9/(6-4))*3 → 964-/3*으로 변환되고 이를 계산한다. 따라서 해당 문제에서는 트리를 입력받고 후위 순회하며 각 단계에서 계산을 해주면 된다. 트리에서 후위 표기식 계산 방법 스택을 이용해 계산하면 된다. 숫자일 경우 바로 스택에 넣는다.. 2021. 10. 24.
[SWEA - Java] 1231. 중위순회 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 설명 트리를 구성할 때는 1차원 배열, 2차원 배열, 클래스 등 다양한 방법으로 구현할 수 있다. [Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 이 문제는 1번 노드부터 완전 이진트리 형식으로 주어지기 때문에 1차원 배열만으로도 중위 순회를 처리할 수 있다. 따라서 배열의 각 인덱스에 해당하는 알파벳 값을 저장하고 재귀를 이용해 순회할 수 있다. N번 노드의 왼쪽 자식 노드는 N * 2번 노드, 오른쪽 자식 노드는 N * 2 + 1번 노드가 된다. 중위 순회는 왼쪽 자식 노드 → 부모노.. 2021. 10. 24.
[SWEA - Java] 1233. 사칙연산 유효성 검사 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 설명 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라. 여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다. (단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 .. 2021. 10. 24.
[Java] 트리 Tree 3 - 이진 탐색 트리 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진트리 이진트리 기반의 탐색을 위한 자료 구조 이진 탐색 트리의 성질 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리 키들은 루트 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 찾고자 하는 키 값이 이진트리의 루트 노드의 킷값과 비교해 루트 노드보다 작으면 원하는 키값은 왼쪽 서브 트리에 있고, 루트 노드보다 크면 원하는 키 값은 오른쪽 서브 트리에 있다. ex. 왼쪽 서브 트리의 값들 (3, 7, 12)는 루트 노드인 18보다 작다. 오른쪽 서브 트리의 값들 (26, 31, 27)은 루트 노드인 18보다 크다. 위의 이진 탐색 트.. 2020. 12. 31.
[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5.
[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법 1. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 한 개 이상의 노드로 이루어진 유합 집합 A~J를 노드(node) 이들 중 하나의 하나의 노드를 루트(root) 노드라 하고 나머지 노드들을 서브 트리(sub tree)라 한다. 계층적 구조에서 가장 높은 곳에 있는 노드 A가 루트가 됨 루트와 서브트리는 간선(edge)으로 연결됨 ex) {A, B, C, D, E, F, G, H, I, J} 중에서 루트 노드는 A이고 나머지 {B, E, F, G}, {C, H}, {D, I, J}의 3개의 노드 집합들은 A의 서브 트리라 한다. 다시 서브 트리 {B, E, F, G}의 루트는 B가 되고, 나머지 {E}, {F}, {G} 노드들은 다시 3개의 서브 트리로 나뉜다. 나머지도 마찬가지이다.. 2020. 11. 3.
반응형

티스토리툴바