전체 글49 [ Java ] PriorityQueue에 하나씩 넣으면 O(n log n)인데, 한 번에 만들면 O(n)이라고? 지난 글에 이어서 PQ를 또 후두리찹찹 해보도록 하겠습니다. 우선순위 큐를 처음 채울 때 보통 이렇게 작성합니다.PriorityQueue pq = new PriorityQueue();for (int value : values) { pq.offer(value);}원소 하나를 넣을 때 힙을 조정하는 비용이 O(log n)이니까, n개를 넣으면 최악 O(n log n)입니다.그런데 이미 리스트에 값이 모여 있다면 이렇게도 만들 수 있습니다.List values = Arrays.asList(7, 6, 5, 4, 3, 2, 1);PriorityQueue pq = new PriorityQueue(values);이 경로의 힙 구성은 O(n)입니다.“같은 값을 넣는데, 생성자로 넘기면 더 싸다고?”(생성자가 반복.. 2026. 9. 28. [ Java ] PriorityQueue에 넣은 값을 바꿨는데, 왜 꺼내는 순서는 그대로일까? 코테를 풀다 보면 우선순위 큐를 자주 사용하게 됩니다. 작은 값부터 꺼내고 싶으면 PriorityQueue에 넣고, poll()로 하나씩 꺼내면 되죠. 그런데 객체를 넣었다면? 그리고 큐에 넣은 뒤에 그 객체의 우선순위를 바꿨다면? “값이 작아졌으니까 알아서 먼저 나오겠지?” ( 4개월 전 작성자의 크나큰 실수.. ) 흠..? 정말 그렇게 동작하는지 살펴보겠습니다!분명 1로 바꿨는데, 10이 먼저 나온다숫자가 작을수록 먼저 처리하는 작업 큐를 만들어보겠습니다.import java.util.Comparator;import java.util.PriorityQueue;public class PriorityQueueMutationDemo { static class Task { final Str.. 2026. 9. 27. [ MySQL ] 인덱스를 두 컬럼에 걸었는데, 왜 정렬은 따로 할까? 오늘도 찾아온 끄적끄적 공부기록..조회 성능 좀 개선해보고자 인덱스를 공부하며 적용 시켜보고있는데 홰 복합 컬럼이 이따구로 동작하는가에 대해 의문을 갖고 시작했습니다. 우선 게시글 목록을 조회한다고 가정해보겠습니다.카테고리로 검색하고, 작성 시간으로 정렬하니까 인덱스도 이렇게 만들면 될 것 같습니다.CREATE INDEX idx_category_createdON posts (category_id, created_at);그런데 실행 계획을 보니 이런 문구가 나타납니다.Using filesort“인덱스는 정렬되어 있다면서?”“검색하는 컬럼이랑 정렬하는 컬럼까지 다 넣었는데?”흠.. 인덱스에 컬럼이 포함되어 있다는 것만으로는 부족합니다. 어떤 순서로 정렬되어 있는지까지 봐야 합니다.이번에는 복합 인덱스의 순.. 2026. 9. 27. [ Java ] HashSet 시리즈2 - contains()가 O(n)까지 느려진다고? 2026.09.16 - [분류 전체보기] - [ Java ] HashSet 시리즈1 - 중복 검사도 검색도 무조건 O(1)일까? 이전 글에 이어서 hashSet을 뚜드려 패보도록 하겠습니다 트리가 되면 무조건 O(log n)일까?여기서 한 번 더 생각해봐야 합니다.높이가 낮다는 사실과, 검색할 때 한쪽으로만 내려갈 수 있다는 사실은 다릅니다.예를 들어 현재 노드를 보고 왼쪽인지 오른쪽인지 결정할 수 있다면, 하나의 경로만 따라가면 됩니다.하지만 어느 쪽인지 판단할 수 없다면?양쪽을 찾아봐야 할 수도 있습니다.HashMap의 트리 탐색은 우선 해시를 비교합니다. 해시가 같으면 같은 키인지 확인하고, 적합한 Comparable 비교로 방향을 정할 수 있는지도 확인합니다.그런데 아래 조건이라면 문제가 됩니다.. 2026. 9. 17. [ Java ] HashSet 시리즈1 - 중복 검사도 검색도 무조건 O(1)일까? 코테를 풀다 보면, 어떤 값이 이미 존재하는지 확인해야 하는 경우가 정말 많습니다.리스트로 하나씩 확인하면 느릴 것 같으니, 보통 HashSet을 사용하죠.Set visited = new HashSet();visited.add(10);System.out.println(visited.contains(10)); // trueHashSet의 add()와 contains()는 O(1).그런데 문득 이런 생각이 들지 않나요?“값이 엄청 많아져도 무조건 한 번에 찾는 건가?”“서로 다른 값이 같은 위치에 들어가면 어떻게 하지?”흠.. 해시를 사용하니까 빠르다는 건 알겠는데, 그것만으로는 설명이 조금 부족합니다.이번에는 HashSet이 값을 찾는 과정부터, 내부에 레드블랙 트리가 등장하는 이유까지 살펴보겠습니다!Ha.. 2026. 9. 17. [ Java / Spring Boot ] 서비스 객체는 하나인데, 여러 요청을 동시에 처리해도 괜찮을까? Spring Boot에서 서비스를 만들 때 보통 이렇게 작성한다.@Servicepublic class OrderService { // 주문 처리}별도의 스코프를 지정하지 않았다면 이 빈은 기본적으로 싱글톤이다.그런데 여기서 조금 이상한 생각이 든다.“객체가 하나면 요청도 하나씩 처리하는 건가?”“여러 사람이 동시에 호출하면 데이터가 섞이지 않나?”하나의 객체를 여러 스레드가 동시에 사용할 수 있다.그리고 코드를 어떻게 작성했느냐에 따라 데이터가 섞일 수도 있다.(싱글톤이라고 Spring이 줄을 세워주는 건 아니었다.)1. 싱글톤은 정확히 무엇이 하나라는 뜻일까?Spring의 싱글톤 스코프는 기본적으로 컨테이너 하나에서 빈 정의 하나당 인스턴스 하나를 공유한다는 뜻이다.특정 클래스의 객체가 프로그램 .. 2026. 9. 16. 이전 1 2 3 4 ··· 9 다음
