Moon Seung Hyun

[DataType] 트리 구조


트리

트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. – 위키백과

트리 기본구조

Binary Search Tree

루트노드를 기준으로 작은 값은 왼쪽노드, 큰값은 오른쪽 노드로 설정하는 방식

코드

class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }

  insert(value) {
    if(value <= this.data) {
      if(this.left == null) {
        this.left = new Node(value)
      } else {
        this.left.insert(value)
      }
    } else {
      if (this.right == null) {
        this.right = new Node(value)
      } else {
        this.right.insert(value)
      }
    }
  }

  contains(value) {
    if(value == this.data) {
      return true
    } else if (value < this.data) {
      if( this.left == null) {
        return false
      } else {
        return this.left.contains(value)
      }
    } else {
      if(this.right == null) {
        return false
      } else {
        return this.right.contains(value)
      }
    }
  }

  printInOrder() {
    if(this.left != null) {
      this.left.printInOrder();
    }
    console.log(this.data)
    if(this.right != null) {
      this.right.printInOrder();
    }
  }

  printPostOrder() {
    if(this.right != null) {
      this.right.printPostOrder();
    }
    console.log(this.data)
    if(this.left != null) {
      this.left.printPostOrder();
    }
  }

  printPreOrder() {
    console.log(this.data)
    if(this.left != null) {
      this.left.printPreOrder();
    }
    if(this.right != null) {
      this.right.printPreOrder();
    }
  }
}

const tree = new Node();
tree.insert(10)
tree.insert(20)
tree.insert(7)
tree.insert(3)
tree.insert(6)
tree.insert(13)
tree.insert(16)
tree.insert(1)
tree.insert(19)
console.log('=======Start In Order======')
tree.printInOrder()
console.log('=======End======')
console.log('=======Start Pre Order======')
tree.printPreOrder()
console.log('=======End======')
console.log('=======Start Post Order======')
tree.printPostOrder()
console.log('=======End======')

트리를 이용한 문제 예시

  • 행렬(numArray)과 그 행렬의 개수(N)이 주어질때
    • 행렬을 순서대로 +, - 등식으로 조합하여 결과값이 0이상 ~ 20이하로 값이 유지되고,
    • 최종 값 역시 0이상 ~ 20이하로 값이 되도록하는
    • 부등식 조합의 갯수를 구하시오.
// const N = 11, inputNumbers= [8,3,2,4,8,7,2,4,0,8,8]; // 10
// const N = 4, inputNumbers= [8,3,10,10];
const N = 9, inputNumbers = [3,6,9,7,2,1,2,5,3] // 3


let answer = 0;
class Node {
  constructor(data, count, allProcess, left, right) {
    this.data = data
    this.left = left
    this.right = right
    this.isLeftStop = false // this.data가  음수일 경우 더이상 진행하지 않기 위해
    this.isRightStop = false // this.data가  20초과일 경우 더이상 진행하지 않기 위해
    this.count = count
    this.allProcess = allProcess
  }

  insert(value, c) {
    if(this.data == undefined) {
      this.data = value
      this.count = c
      this.allProcess = 3
      return 
    }

    if(this.isLeftStop == false) {
      if(this.left == undefined) {  
        if(this.data - value >= 0) {
          this.left = new Node(this.data-value, c, this.allProcess + " - " + value)
        } else {
          this.isLeftStop = true
        }
      } else {
        this.left.insert(value, c)
      }  
    }
    if(this.isRightStop == false) {
      if(this.right == undefined) {
        if(this.data + value <= 20) {
          this.right = new Node(this.data+value, c, this.allProcess + " + " + value)
        } else {
          this.isRightStop = true
        }
      } else {
        this.right.insert(value, c)
      }
    }
  }

  traverse() {
    if(this.left != undefined) {
      this.left.traverse()
    }

    if(this.right != undefined) {
      this.right.traverse()
    }

    if(this.count == N) {
      answer++
      console.log("this.allProcess : ", this.allProcess + " = " + this.data)
    }
  }
}

const tree = new Node()
for(let i=0;i<N;i++) {
  tree.insert(inputNumbers[i], i+1)
}
tree.traverse()
console.log("answer : ", answer)




2023

Flutter 맛보기 1

3 분 소요

직방 기술지원팀 기술공유 세미나 중 플러터를 소개한 내용입니다

Back to Top ↑

2022

Back to Top ↑

2019

[Tutorial] Storybook과 Bit을 활용한 UI 컴포넌트 관리(Workflow)

1 분 소요

회사에서 프론트엔드 개발원칙을 SFC(Single File Component)에서 UI 컴포넌트를 기준으로 CDD(Component Driven Development)를 진행하려고 한다. 그래서 체계적으로 관리하기위해 Storybook과 Bit을 도입해보고자 한다. 각각의 역할은 ...

[Workflow] 프론트엔드 개발조직을 위한 워크플로 설계

2 분 소요

작성 배경 회사의 작업구조를 페이지 중심 개발에서 UI 컴포넌트 중심 개발로 변경하면서 Workflow를 개선할만한 환경을 구성해야했다. 폐쇄망 기반에서 개발자간 UI 명세서 역할을 할 수 있는 Storybook과 그것을 공유할 Verdaccio라는 구축형 NPM Pri...

[ESlint & Prettier] 개발 관습 설정 in Visual Studio

1 분 소요

회사 프로젝트를 작업하기 전 프론트엔드 개발자들 간의 코드 규칙을 Eslint와 Prettier 설정을 맞춰 관리해가는 방향을 정했다. 아직 협업을 할 경우는 없지만 미래에 인수인계 받거나 협업을 진행할 경우 코드관습이 달라 고생할 경우를 대비하기로 했다. 설정은 작업을 진행하며 ...

[CodingTest] 2019-10-26 SQL문제

최대 1 분 소요

공부겸 코딩테스트 사이트에서 토요일 오전 10시에 백엔드 포지션 테스트를 해준다기에 참여해봤다. SQL문제가 나왔는데 더 좋은 답이 있는것 같아 나중에 기록해두고 수정해보기로 한다.

[CodingTest] 피보나치 수열

1 분 소요

문제 : 피보나치 수열 제 1항부터 입력한 자연수(N)까지의 피보나치 수열 항들의 합을 구하여라.

[Syntax] 새로 알게된 파이썬 문법 정리

최대 1 분 소요

chaning comparison 파이썬은 chaning comparison이라는 신기한 문법이 있다. 참고 if a < b and b < c : (...) 라는 구문이 if a < b < c : (...) 으로 연산된다. 직관적인 문법이 인상적. ...

[DataType] Map & Set

최대 1 분 소요

Set vs Array - 관련기사 Set 유일값들의 배열이 필요할때(distinct) 집합의 개념이 필요할때(차집합, 교집합 등등 자체 메서드들이 많음.) index가 필요 없을때 Array에서 중복값을 없앨때 => ...

Back to Top ↑

2018

SGIS-shpToGeojson

1 분 소요

SGIS에서 받은 지도데이터(.shp)를 geojson으로 변경하는 작업 내용

Back to Top ↑