알고리즘을 처음 공부할 때, 많은 사람들이 어려워하는 개념이 바로 "동적계획법(DP)"입니다. 이 글에서는 DP를 어떻게 접근하고, 어떤 기준으로 적용할지 명확히 이해할 수 있도록 안내하겠습니다. 📌 동적계획법(DP)이 어려운 이유DP는 문제를 작은 문제로 나누고, 그 결과를 활용하여 큰 문제를 해결하는 방식입니다. 하지만 처음부터 DP가 적용된다는 것을 떠올리기 쉽지 않죠. 문제를 보면 막막하게 느껴지기 때문입니다.📌 DP를 명확히 적용하는 3가지 기준다음의 기준을 보고 DP 적용 여부를 쉽게 판단해보세요.반복되는 부분 문제가 있는가?배수, 비율 등 간단한 규칙으로 최적이 가능한가? (그리디로 해결 가능)작은 문제의 해답을 큰 문제에서 활용할 수 있는가? (점화식 판단)이 기준을 충족하면 DP로 접..

컴퓨터 프로그래밍에서 숫자를 입력받는 것은 흔히 있는 일이지만, 그 내부의 원리를 정확히 이해하고 있는 사람은 많지 않습니다. 이번 글에서는 숫자 입력을 처리할 때 흔히 사용하는 공식인 n = n * 10 + (c - '0')의 원리와 수학적 의미를 상세히 다뤄보겠습니다.✅ 왜 이 주제를 다루는가?처음 이 공식을 접하면 직관적으로 이해하기 어렵습니다.저 또한 처음에는 “왜 갑자기 *10을 곱하지?“라는 의문을 가졌습니다.이 글은 저와 같은 고민을 한 분들에게 직관적인 이해와 명확한 설명을 제공하기 위해 작성되었습니다.✅ 기본 공식 (n = n * 10 + (c - '0')) 설명하기이 공식은 문자열로 입력받은 숫자를 정수형으로 변환할 때 사용되는 표준 알고리즘입니다.예시로 숫자 “371”을 살펴봅시다.읽..

핵심 개념Quicksort는 pivot 1개를 사용해 배열을 두 부분으로 나누지만, Dual-Pivot Quicksort는 pivot 2개를 사용해 배열을 세 부분으로 나눕니다.각 구간을 재귀적으로 정렬하는 고성능 분할 정복 기반 정렬 알고리즘입니다.Arrays.sort()에 사용되고 있습니다.분할 방식(Pivot 2개 → 3 구간)pivot1 배열을 다음 3개의 부분으로 나눔:arr[i] pivot1 ≤ arr[i] ≤ pivot2arr[i] > pivot2이 3개 구간을 각각 재귀적으로 정렬동작 절차 구현아래 소스는 이해를 위해 만든 로직입니다. Arrays.sort()와는 접근 방식이 다릅니다.결과값은 같습니다.void dualPivotSort(int[] arr, int left, int right..

1. 왜 만들어 졌을까?어원(When)Dynamic: 시간에 따라 변하는 걸 의미하는 것이 아님!Programming: 코드 작성이 아니라, 계획(Plan)을 짠다는 의미즉, 유동적으로 결정하는 계획 정도의 뜻누가 만들었나?Richard Bellman(리처드 벨만), 1950년대미 국방성 프로젝트 중 최적화 문제를 해결하기 위해 개발 왜? ‘Dynamic Programming’이라 이름 붙였나?벨만의 유명한 일화에 따르면:내가 일하던 국방 프로젝트는 ‘수학’이나 ‘과학’이라는 단어에 거부감을 가진 관리들이 있었지그래서 그들이 이해 못할 단어를 골라야 했어. 그래서 ‘다이내믹 프로그래밍’이라고 불렀지즉, 본래 의미보다 정치적 이유(!)로 지어진 네이밍…어떤 알고리즘이야?큰 문제를 작은 문제를 나눠서 푼 ..

메모리 사용량1. 비트셋(BitSet)의 메모리 사용고정 비용: 비트셋은 내부적으로 long[] 배열로 비트를 저장합니다.예를 들어 new BitSet(1_000_000)은 약 1,000,000 비트(≈125 KB) + 배열 오버헤드(약 몇십 바이트) 정도를 사용합니다.저장 가능한 값의 최대치(=capacity)에 관계없이, capacity/8 바이트를 항상 차지합니다.장점:대량의 연속된 정수 범위에서 “존재 여부”만 저장할 때 가장 압축적입니다.단점:실제로 저장된 요소가 적더라도, 범위 전체에 대해 메모리를 할당합니다. 2. 해시셋(HashSet)의 메모리 사용가변 비용: HashSet은 내부적으로 HashMap을 쓰고, 키마다 Node 객체(엔트리)와 버킷 배열(참조 배열)을 유지합니다.버킷 배열:..

시리즈2025.03.11 - [Java/자료구조] - 스택? 큐?2025.03.11 - [Java/자료구조] - Deque?2025.03.11 - [Java/자료구조] - 덱(Deque) 보다 큐(Queue)와 스택(Stack)이 더 좋은 경우?자바 기반 설명이며 개념에 관한 내용을 다룹니다.📌 핵심내용

시리즈2025.03.11 - [Java/자료구조] - 스택? 큐?2025.03.11 - [Java/자료구조] - Deque? 자바 기반 설명이며 개념에 관한 내용을 다룹니다.📌 핵심내용큐와 스택의 장점을 취하고 단점을 보완한 자료구조로더 유연하고 안정적인 데이터 관리가 가능합니다.다만, 성능은 상황에 따라 달라져 구조를 알고 효율적으로 사용해야 적절합니다.Deque(덱)가 등장한 배경과 필요성Deque(Double-ended Queue, 덱)는 큐와 스택의 단점을 보완한 자료구조로, 양쪽에서 삽입과 삭제가 가능한 형태입니다.1. Deque가 등장한 이유큐(Queue)와 스택(Stack)은 각각 단순한 선형 자료구조이지만, 다음과 같은 문제점이 존재합니다.큐(Queue)의 문제점FIFO 구조로 인해 한쪽..

시리즈2025.03.11 - [Java/자료구조] - 스택? 큐?2025.03.11 - [Java/자료구조] - Deque? 자바 기반 설명이며 개념에 관한 내용을 다룹니다.📌 핵심내용스택(Stack)과 큐(Queue)는 기본적인 자료구조로동기화(스레드 세이프), 시간 복잡도, 알고리즘 적용 방식에 따라 성능과 활용도가 크게 달라집니다. 본 글에서는 실무에서 발생하는 문제와 해결 방안을 중심으로 심화 내용을 다룹니다. 1. 스택(Stack)과 큐(Queue)의 차이점구분스택(Stack)큐(Queue)구분스택(Stack)큐(Queue)구조후입선출(LIFO)선입선출(FIFO)동기화Stack (Thread-safe X)ConcurrentLinkedDeque (Thread-safe O)LinkedList (T..

자바 기반 설명이며 개념에 관한 내용을 다룹니다.📌 핵심내용데이터 구조는 Object의 특성에 따라 적절하게 선택해야하는데스택(Stack), 큐(Queue), 해시맵(HashMap), 트리(Tree), 그래프(Graph) 등 다양한 데이터 구조가 존재하며 각각의 특성이 달라상황에 맞는 데이터 구조 선택이 성능 최적화의 핵심이다.1. 데이터 구조별 특징데이터 구조설명사용 사례배열(Array)인덱스를 통한 빠른 접근 가능리스트, 행렬 연산 (예: Java의 ArrayList)연결 리스트(Linked List)동적 크기 조정 가능, 삽입/삭제 용이LRU 캐싱 (예: Java의 LinkedList)스택(Stack)후입선출(LIFO)함수 호출 스택 (예: Java의 Stack 클래스)큐(Queue)선입선출(FI..

시프트를 활용한 기본적인 연산인 N번째 비트를 핸들링하는 방법과 프로그래밍하는 방법에 대해서 알아보겠습니다. 1. GET - N 비트 가져오기2. SET - N 비트 true3. CLEAR - N 비트 false4. CLEAR LEFT - N 비트 왼쪽으로 false5. CLEAR RIGHT - N 비트 오른쪽으로 false6. UPDATE - N 비트 true/false 제어하기 1. GET - N 비트 가져오기boolean getBit( int num, int N ) { return num & ( 1 num = 13; 0b1101;N = 3;1을 왼쪽으로 N번 만큼 쉬프트하고 AND 연산을 통해 있다면 true 없다면 false를 반환하여 2. SET - N 비트 tureint setBit( in..