효율적인 알고리즘 활용: 슬라이딩 윈도우 최댓값과 상위 K개 빈도 요소 찾기
알고리즘 문제 해결 과정에서 흔히 마주치는 두 가지 유형의 문제, 즉 슬라이딩 윈도우 내의 최댓값을 찾는 문제와 데이터셋에서 빈도수가 높은 상위 K개의 요소를 추출하는 문제에 대해 다룹니다. 각 문제에 대한 효과적인 해결 전략과 함께 C++ 구현 예시를 제시합니다.
슬라이딩 윈도우 최댓값 (LeetCode 239번)
주어진 정수 배열 nums와 정수 k가 있을 때, 크기 k의 ...
9월 2일 02:08에 게시됨
LeetCode 문제 풀이: 두 수의 합
두 수의 합 문제:
주어진 정수 배열 nums와 대상 값 target에서 배열 중 두 수를 찾아 합이 target인 두 수의 인덱스를 반환해야 합니다. 배열의 같은 원소를 반복해서 사용할 수 없습니다.
주어진 입력값은 하나의 정답을 가지며, 하나의 정답만 있을 것입니다.
예제:
nums = [2, 7, 11, 15], target = 9
nums[0] + nums[1] = 2 + 7 = 9
따라서 [0, 1]을 반환합니다. ...
8월 30일 04:58에 게시됨
기술 면접 대비 해시 테이블을 활용한 문제 해결 패턴
해시 데이터 구조의 적용 사례와 최적화 기법
알고리즘 문제를 해결하는 과정에서 특정 원소의 존재 유무나 빈도수를 빠르게 확인해야 하는 상황은 매우 흔합니다. 이때 단순한 나열된 데이터를 순회하며 비교하는 방식은 시간 복잡도가 O(N^2)에 달할 수 있어 비효율적입니다. 이러한 경우 선형 시간인 O(1) 검색 성능을 제공하는 해시 테이블 (HashMap 또는 Set) 을 활 ...
8월 13일 22:44에 게시됨
Java 해시맵과 투 포인터를 활용한 네 가지 문제 풀이
1. 454. 네 수의 합 II (4Sum II)
이 문제는 네 개의 배열에서 각각 하나씩 선택하여 합이 0이 되는 조합의 개수를 찾는 문제입니다.
해시맵을 사용하면 시간 복잡도를 O(n²)으로 줄일 수 있습니다. 먼저 첫 번째와 두 번째 배열의 모든 쌍의 합과 그 등장 횟수를 해시맵에 저장합니다.
그 다음 세 번째와 네 번째 배열의 모든 쌍의 합에 대해, 0에서 해당 합을 뺀 값이 ...
6월 25일 16:04에 게시됨
Java HashMap 핵심 소스 코드 직접 구현하기
Java HashMap 핵심 소스 코드 직접 구현하기
이전 글에서는 LinkedList의 핵심 소스 코드를 직접 구현해 보았습니다. 이번에는 Java HashMap의 핵심 소스 코드를 직접 구현해 보겠습니다. HashMap의 원리를 먼저 살펴보겠습니다.
HashMap은 이름에서 알 수 있듯이 hash와 map의 조합입니다. map은 매핑이라는 의미이고, HashMap은 hash를 활용하여 키-값 쌍을 저장하는 ...
6월 22일 19:56에 게시됨
HashMap의 부적절한 사용으로 인한 CPU 100% 문제 분석
이전 프로젝트에서 비슷한 문제가 발생했었는데, 그때는 CurrentHashMap을 사용했습니다. 이 글은 그러한 문제를 재조명하고, 개발자들에게 경고하기 위한 것입니다.
HashMap의 잘못된 사용으로 인해 최근에도 여러 사례가 발생했습니다. 이에 대한 자세한 내용은 다음과 같습니다.
다음 코드는 HashMap의 쓰레드 안전하지 않은 사용으로 인한 데드락(실제로는 데드리프) ...
6월 13일 21:39에 게시됨
Java 주요 컬렉션의 알고리즘 복잡도 분석
1. 알고리즘 복잡도 기초
알고리즘 복잡도는 시간 복잡도와 공간 복잡도로 구성됩니다. 시간 복잡도는 데이터 규모가 증가함에 따라 알고리즘 실행 시간이 어떻게 변하는지 측정하며, 일반적으로 빅오 표기법(Big O notation)을 사용합니다. 공간 복잡도는 알고리즘 실행 중 필요한 추가 메모리 공간과 데이터 규모 간의 관계를 나타냅니다.
1.1 시간 복잡도 분석의 중요 ...
6월 9일 00:29에 게시됨
Java에서의 Map 데이터 구조
Java 프로그래밍 언어에서 기본적인 데이터 구조는 배열과 참조(가상 포인터)로 구성됩니다. 모든 데이터 구조는 이 두 가지 기본 요소를 통해 구현됩니다. HashMap은 배열과 연결 리스트의 결합체로, 데이터 구조에서 일반적으로 "연결된 해시"라고 불립니다.
배열이란?
Java는 동일한 타입의 요소를 저장하는 고정 크기의 연속형 컬렉션을 제공합니다. 이는 배 ...
6월 7일 18:01에 게시됨
HashMap 내부 구조와 작동 원리
데이터 구조
1.7 버전
배열과 연결 리스트의 조합으로, 키-값 쌍은 Entry 내부 클래스 배열에 저장됩니다. 키로부터 계산된 해시값이 배열의 인덱스가 됩니다. 이를 버킷 배열이라고 부르며, 해시 충돌이 발생할 경우 Entry 클래스의 내부 멤버 변수 Entry<k,v> next;를 통해 연결 리스트를 형성합니다. 해시값이 동일한 요소들은 머리 삽입법(head insertion)을 ...
6월 3일 17:20에 게시됨