Jul's 개발일지 Jul's 개발일지

세그먼트 트리에 대해 알아봅시다. 세그먼트 트리란 구간의 합을 리프 노드에 저장하는 자료구조로 O(logN) 시간 복잡도를 가지고 연결된 데이터의 구간합을 구할 수 있습니다. 데이터 : 4 9 3 8 6 9 7 9 7 9 2 3 4 8 7 가 주어 질 때 구간의 합을 구하는 방법은 다음과 같습니다. 가장 단순하게 선형적으로 구하는 방법으로 시간 복잡도 O(n)가 나올 것입니다. 좀 더 개선하면 누적 합과 같이 각 행을 처음부터 해당 칸의 합을 저장해서 O(n) 이후 O(1)으로 계산할 수 있습니다. 누적합 4 13 16 24 30 39 46 55 62 71 73 76 80 88 95와 같이 저장될 것이며 O(n) 이 걸립니다. 이후 3번째부터 12번째 데이터 합은 인덱스 12번째 인덱스 - (3-1)번째..

오늘은 자료구조 이진 탐색 트리에 대해 정리해 보겠습니다. 다음 그림과 같이 데이터를 저장하는 자료구조를 Tree라고 합니다. 각각 데이터를 저장하고 있는 것을 Node라 할 때, 위와 같이 각 Node에 두 개의 Node가 저장되는 트리를 이진 트리라고 합니다. 이때 4,5,6,7 Node처럼 맨 아래에 있는 노드를 리프 노드라 합니다. 위와 같은 트리는 포화 이진트리 (리프노드를 제외한 노드가 두개의 노드를 가지는 트리) 또는 이진 트리(모든 노드가 두개의 노드를 가짐, 단 리프노드는 왼쪽에서부터 존재해야 함)라 합니다. 이진 탐색 트리는 부모노드의 왼쪽에 부모노드보다 작은 값, 오른쪽에는 큰 값을 저장합니다. add 하는 값의 순서에 따라 시간복잡도가 최악 O(N)이지만 O(logN)으로 값을 찾을..

저번 주에 면접일정 때문에 포스팅이 늦었어요 오늘은 ArrayList, LinkedList에 이은 Doubly Linked List에 대해 알아보려고 합니다. Doubly Linked List 는 Singly Linked List (LinkedList)에서 연장된 자료구조입니다. LinkedList에서는 단방향으로 데이터가 한 방향으로만 조회가 되었습니다. 하지만 Doubly Linked List에서는 양방향으로 이전의 데이터도 조회할 수 있게 하는 자료 구조입니다. Linked List 와 Doubly Linked List 차이점에 대해 알아봅시다. 이 같이 Doubly Linked List에는 이전의 Node의 data를 가리키는 previous Node를 가지고 있어야 합니다. 다음은 Doubly ..

자료구조 연결리스트(Array)와 단일연결리스트(LinkedList)에 대해 알아보자 두 자료구조의 차이점은 index의 유무라고 말할 수 있습니다. ArrayList에는 index가 존재하고 LinkedList에는 존재하지 않는다. 그림을 통해 알아봅시다. ArrayList의 빨간 글이 index이다. index로부터 객체를 참조할 수 있습니다. 반면 LinkedList에는 index가 존재하지 않기 때문에 4번째 값을 참조하기 위해서는 0번째 객체를 타고 1번째 > 2번째 > 3번째 > 4번째 방식으로 참조할 수 있습니다. 데이터를 조회하기에는 index로 접근하는 것이 효율적입니다. 그렇다면 삽입,삭제는 어떨까? 위의 그림과 비교해보자 만약 index 2를 제거한다면 3번째부터 마지막 객체에 접근해..

데이터베이스 설계에서 테이블 간의 관계를 설정할 때 외래키를 사용합니다. A 테이블 ,B 테이블 관계 설정을 하면 부모 테이블과 자식 테이블이 필연적으로 만들어지는데 외래키가 설정되는 테이블을 자식 테이블이라 했을 때 외래키가 자식 테이블에서 PK 또는 FK로 설정할 수 있습니다. PK로 사용 하는것을 식별 관계, FK로 사용하는 것을 비식별 관계라고 합니다. 식별과 비식별 사이에는 차이점이 있습니다. 바로 부모 테이블에 레코드에 종속적이게 되는가! PK 설정인 식별관계에서는 부모 테이블 PK가 존재하지 않으면 자식 테이블을 생성할 수 없지만 FK 설정인 비식별관계에서는 부모 테이블 PK가 존재하지 않아도 자식 테이블의 PK로 생성할 수 있다는 차이입니다. 식별관계로 설정 할 경우 부모 테이블에 의존적이..

프로젝트를 진행하면서 Union all을 사용하게 되면서 고찰하고 문제점을 개선한 이야기입니다. Union All을 사용하게된 배경 해당 서비스는 혼자 여행할 때 포스트 게시와 여러 명이 동행을 하면서 포스트 게시하는 서비스로 포스트가 저장되는 테이블이 2개 존재했습니다. ( 혼자 할 때, 함께 할 때) 2개의 테이블에서 특정 시간 내에 사용자가 마지막에 게시한 포스트들을 조회해야 했습니다. 두 개의 서브 쿼리와 동행의 연관관계 때문에 여러 번의 조인문이 존재했습니다. 문제는 Union All이었습니다. Union All을 사용하게 되면 두 개의 SELECT문이 하나로 합쳐지면서 인덱스를 타고 조회할 수 없게 됩니다. 데이터 량이 적으면 상관없겠지만 좋은 방법은 아닙니다. 또한 두개의 SELECT문을 메..

Spring Ioc(제어역전)와 DI(의존성 주입)에 대한 이야기입니다. 일반적으로 자바에서 객체를 사용하기 위해 생성자 new을 사용하여 객체를 생성한 후 객체에서 제공하는 기능을 사용합니다. 아래 코드는 일반적인 자바의 객체 생성 방식입니다. @RestController public class Controller { private HelloService helloService = new HelloServiceImpl(); @GetMapping("/hello") public String hello() { return helloService.getHello(); } } 하지만 제어역전을 사용하는 스프링은 자바와 다르게 동작합니다. new 생성자로 직접 생성하지 않고 객체를 관리하는 외부로 돌립니다. 이때..

토스에서 진행한 컨퍼런스에서 느낀 점을 정리한 글입니다. 토스에서 SLASH 23 개발자 컨퍼런스를 진행했습니다. 저는 백엔드 트랙 컨퍼런스에 참가했는데 첫 번째 주제에서 이야기해보려고 합니다. 첫 번째 주제로 주민등록증 사용자 인증에 관해서 유효한 사용자의 민증을 직접 인증을 하는 과정에서 사람이 직접 민증을 확인하는데 빠르면 2분 서비스를 이용하는 시간대에 따라 최대 6시간이 걸리고 사람이 실수했을 때 두 번째 대책이 없어서 Object detecting으로 민증이 원본사진인지 아닌지 판단하는데 AI 모델을 도입했다는 이야기였습니다. 때는 2019년의 일이다. 대학교 때 학교 커뮤니티 앱 개발에 참여했던 적이 있는데 유효한 학생임을 인증하는 역할을 맡았는데 학생이 학생증 사진을 찍어주면 OCR로 해당..