개발하다보면 '싱글톤'이라는 디자인 패턴을 자주 접하게 되는데, 그때마다 대충 구글링해서 이런거구나~ 하고 넘기다보니 기억에서 자주 삭제되는 바람에..;; 마음먹은 김에 정리해두려고 한다. Singleton 패턴이란 🌟 프로세스가 실행 중에 오직 하나의 오브젝트만 생성되도록 강제하는 디자인 패턴 즉, 싱글톤 디자인 패턴을 가진 클래스를 사용해서 여러 개의 오브젝트를 만들더라도, 모두 단 하나의 오브젝트만 가리키도록 만드는 것이다. 언제 사용하나? 하나의 오브젝트가 리소스를 많이 차지할 때 하나의 오브젝트가 외부 네트워크와 연결되는데, 이 네트워크는 하나만 존재해야 할 때 등등 예시 1. 싱글톤 적용 X class Cat { constructor(name) { this.name = name; } speak..
Binary Indexed Tree(Fenwick tree ; 펜윅트리)
LSB 본격적인 Binary Indexed Tree를 설명하기에 앞서 LSB(k)에 대해 간단히 알아보자. (나중에 쓰이는 연산임!) 어떤 수 k를 2진수로 바꿨을 때 가장 첫 번째로 1이 등장하는 위치를 d라 하자. LSB(k) = 2^d 를 말한다. 아래의 예시를 보면 이해에 도움이 될 것이다. LSB(10) 10 = 1010(2진수) 가장 첫 번째로 1이 등장하는 위치 d = 1 (오른쪽부터 0으로 카운트 시작) LSB(10) = 2^1 = 2 LSB(12) 12 = 1100 d = 2 LSB(12) = 2^2 = 4 LSB(8) 8 = 1000 d = 3 LSB(8) = 2^3 = 8 LSB 빠르게 구하기 실제 코드에서 LSB(k)를 상수시간 내 계산하는 방법은 -k(2의 보수)를 활용하는 것이다..
트리 자료구조 정의 부모- 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조 용어 정리 부모(조상)노드, 자식(자손)노드 루트노드 : 모든 노드의 조상노드 리프노드 : 자식이 없는 노드 레벨(level) : 루트 노드 "0레벨" 부터 시작하여 한 세대씩 내려가며 1씩 증가 깊이(depth) : 루트에서 다른 노드를 연결하는 에지 개수 높이(height) : 노드의 높이는 자식 노드까지의 가장 큰 깊이 트리 높이 : 루트 노드의 높이 경로 : 두 노드 사이를 연결하는 엣지의 시퀀스. 경로의 길이는 에지의 수 분지수(degree) : 노드의 분지수는 자신의 자식 노드 수. 트리의 분지수는 가장 큰 분지수로 정의 부트리(subtree) : 어떤 노드와 그 노드의 자손노드들로 구성된 부분 트리 이진트리 모든..