정글에서 온 개발자

heapify는 O(logN)의 작업을 N 번 하니까 여느 sort처럼 O(NlogN)이 걸릴 것 같지만 그렇지 않다.heapify한 heap을 이용해 배열로 만드는 시간 (heap-build)가 O(NlogN)이 걸리는 것이다.레퍼런스요약각 노드들이 최대 얼마나 움직일 수 있는지를 기준으로 정해진다.각 노드들은 연산시 아래쪽으로만 이동한다. (재귀적인 heapify)각 높이에 있는 노드들은 최악의 경우에 h번 swap을 한다. (꼭대기에서 바닥까지 가는 경우)각 높이에 있는 노드는 대략 n/2^h개 이다. (2^h개의 노드를 가정했을 때, 꼭대기층에는 1개, 그 아래층에는 2개..)이 식을 시그마하면 O(n)이 된다.설명heapify의 과정위와 같이 맨 마지막 비 리프부터 시작해서, 윗쪽 노드로 가면서..

개요 JDBC(Java Database Connectivity) - 1990 중반. 자바 프로그래밍 언어의 일부 JdbcTemplate - 2000년 초. Spring Framework의 일부. Spring과 함께 등장 JPA(Java Persistence API) - 2000년대 중반. 자바 EE 표준. ORM(Object-Relational Mapping)을 위한 API 제공. Hibernate는 JPA의 구현체 Spring Data JPA - 2010년 초. Spring Data 프로젝트의 일부. JPA를 더 쉽게 사용 리포지토리 계층 쉽게 구현하는 추상화 제공 Spring Data JDBC - 2010년 후반. Spring Data JDBC. JPA의 복잡성을 줄이고자 등장. 도메인 중심 설계 촉..

디렉토리 구성 model ArticleEntity.java dto ArticleDTO.java ReponseDTO.java repository ArticleRepository.java (interface) service ArticleService.java controller ArticleController.java 코드 Entity(Model) 테이블 스키마 그 자체 @Builder @NoArgsConstructor @AllArgsConstructor @Data @Entity @Table(name = "Article") public class ArticleEntity { @Id @GeneratedValue(generator="system-uuid") @GenericGenerator(name="system..

서블릿 엔진 → @RestController 개발자는 Javax.servlet.http.HttpServlet을 상속받는 서브 클래스를 작성해야 한다. 서블릿 컨테이너는 서블릿 서브 클래스를 실행시킨다. @RestController 에는 이 서블릿 서브 클래스가 이미 구현되어있다. MVC 흐름 contoller → model (service → repository) 데이터처리 데이터 → service → controller → view M(odel) @Service - Model에서 비즈니스 로직을 담당함 @Repository - 서비스에서 호출되어 실제 데이터베이스와 연결, 데이터 조회, 저장 작업을 수행함 .findbyId 등 이용 가능extends JpaRepository 로 JPA 이용 @Query..

Priority Inversion 문제 우선순위 역전. 우선순위가 높은 쓰레드가 우선순위가 낮은 쓰레드를 기다리는 현상 Critical Section(이하 CS)를 접근하지 못하도록 락을 거는 경우에 발생한다. 락은 우선순위와 상관 없이, 락 홀더가 끝날 때까지 다른 쓰레드들이 락이 풀릴때까지 CS 앞에서 대기한다. L(낮은 priority) 이 lock holder고 H(높은 priority)가 락 해제를 기다리는 경우에도 우선순위 역전이라고 할 수 있다.(나의 생각) 일반적으로는 CS에 접근하지 않는 M(L과 H의 중간 priority) 이 들어오는 경우에 이 역전이 더 극명하게 나타난다. L이 time_slice 때 cpu를 반환하면, L보다 우선순위가 높은 M이 먼저 실행된 뒤에야 L이 실행되어 ..

“프로그래밍” 은 테이블을 이용한 방법을 뜻한다. (컴퓨터와 관련이 없다.) 부분 문제의 해를 결합해 문제를 해결한다. 일반적으로 **최적화 문제(optimization problem)**에 적용한다. 최적화 문제 해와 값을 구분하자 문제의 풀이를 “해(Solution)” 라 한다. 그 풀이가 낸 답을 “값(Value)” 라 한다. 최적해는 각 해의 값 중 최적의 값을 내는 해이다. 최적의 값은 하나이지만 그 값을 내는 해는 여러개이다. 최단 거리(값)를 크루스칼, 프림 등 여러 방법(해)으로 풀 수 있다. 즉 최적화 문제는 여러개의 해를 가진다. 분할정복과의 비교 분할 정복은 서로 겹치지 않는(disjoint) 문제를 부분 문제로 분할한다. DP는 부분문제가 서로 중복될 때(부분 문제끼리 부분문제를 공..

알고리즘을 풀다 보면 알고리즘의 유형을 정리하고 싶을 때가 많다. 이 문제를 어떤 알고리즘으로 풀면 좋을지, 내가 쓰고 싶은 알고리즘(동적 프로그래밍, 그리디)로 풀 수는 있는지, 아니면 아예 풀 수 없는 문제인지 그런 문제 분류를 좀 더 큰 그림에서 연구하는 학문을 계산 복잡도 이론이라 한다. 계산 복잡도 이론 각 문제를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제를 분류하고, 각 분류의 특성을 연구하는 학문이다. 여기서 말하는 복잡도는 시간 복잡도랑은 조금 다르다. 시간 복잡도는 알고리즘의 특성이다. 계산 복잡도는 해당 문제 특성이다.(문제를 풀 수 있는 빠른 알고리즘의 시간복잡도) 어려운 문제, 쉬운 문제 다항시간에 풀 수 있는 문제는 “쉽다”고 하고, 다항시간 알고리즘은 “빠르다” ..

이진 탐색 트리(BST; Binary Search Tree) 이진 트리 : 각 노드가 왼쪽, 오른쪽. 최대 두개의 자식 노드만 가질 수 있는 트리 왼쪽 가지를 따라 내려가면 더 작은 수 오른쪽 가지를 따라 내려가면 더 큰 수를 만남 이진 검색트리를 중위 순회하면 크기 순서로 정렬된 원소를 얻을 수 있다. 정렬된 배열의 특징 루트부터 왼쪽으로 쭉 내려가면 최소 값이 나온다. 루트부터 오른쪽으로 쭉 내려가면 최대값이 나온다. 루트가 배열의 중앙값은 아니다(트리가 불균형하게 생길수도 있다.) 이걸 원하면 다른 트리 써야 함 부모 노드가 항상 나보다 한 등수 높은 것도 아니다. (오른쪽 리프를 생각해보자) 정렬된 배열보다 뛰어난 점 특정 원소가 존재 하는지 빠르게 확인할 수 있다 노드의 값을 기준으로 다음 검색..

계층 관계를 갖는 객체를 표현하기 위해 만들어진 자료구조 계층 관계가 없는 자료를 트리로 표현해서 같은 연산을 빠르게 할 수 있는 경우가 많다. 용어. 개념 정리 노드(node)와 간선(edge)로 이루어져 있다. 노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때는 한쪽이 상위, 다른쪽이 하위여야 한다. 상위는 부모(parent), 하위는 자식(child), 부모가 같은 노드는 형제(sibling) 부모와 부모들은 선조(ancestor), 자식과 그 자식들은 자손(descendant) 자식은 여러개 가질 수 있어도 부모는 하나만 가질 수 있다. 가장 윗쪽 노드는 **루트(**root;뿌리) 자식이 하나도 없는 노트는 리프(leaf;잎) 깊이(depth) :루트에서 어떤 노드에 도달하기 위해 거..

객체들의 상호 관계를 표현하기 위해 고안된 자료 구조 계층 관계만을 표현하는 트리에 비해 훨씬 다양한 현실 세계의 문제 표현 개요 그래프 표현 인접 행렬 표현 - 모든 정점의 관계를 표현. 밀집 그래프에서 유리 인접 리스트 표현 - 그래프 간 간선의 관계만 표현. 희소 그래프에서 유리 암시적 그래프 표현 ex) 좌표 표현 - 연결관계가 암시적(바로 옆의 좌표)으로 표현됨 문제가 비교적 단순한 경우 . 그래프 표현이 번거로워 사용 그래프가 아주 큰데, 일부만 사용(정점을 모두 그리지 않음) 단점. 그래프를 사용하는 알고리즘과 변환과정이 합쳐짐 → 코드가 복잡해짐 깊이 우선 탐색(DFS) 대표적 그래프 알고리즘. 재귀 사용 내부적으로 스택이 됨. 너비 우선 탐색(BFS) 가중치가 없는 그래프에서 두 점 사이..