STL 컨테이너란?Standard Template Library템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스메모리 자동관리 -> 메모리 단편화💡 std::vector 란?std::vector는 C++ STL에서 제공하는 동적 배열 컨테이너배열처럼 인덱스로 접근이 가능하면서도, 크기를 유동적으로 조절할 수 있다.push_back() 등 다양한 메서드를 통해 요소 추가/삭제가 쉽고 직관적이다.배열의 단점을 보완한, 가장 자주 쓰이는 컨테이너 📍 특징특징설명연속된 메모리 공간일반 배열처럼 빠른 접근(인덱스 접근 가능) - O(1)동적 크기 조절push_back, resize 등으로 자동 확장다양한 멤버 함수insert, erase, clear, swap 등범위 기반 반복 지원for (int x ..

문제 링크: 백준 8979번 - 올림픽🔍 문제 요약목표: 주어진 국가들의 금, 은, 동 메달 정보를 기반으로 등수를 구하기규칙:금메달 수가 많을수록 우선금이 같다면 은메달 수로 비교금, 은이 같다면 동메달 수로 비교모두 같다면 공동 순위입력:국가 수 N, 등수를 알고 싶은 국가 번호 K각 국가: 국가번호 금 은 동 💡 문제 분석국가의 수는 최대 1,000메달 수 총합은 1,000,000등수를 정하기 위해 모든 국가 정보를 정렬한 뒤 K번 국가의 순위만 찾으면 됨🧩 풀이 전략입력값 저장: vector로 국가별 정보를 저장 ([id, gold, silver, bronze])정렬: compare 함수를 사용하여 금-은-동 순으로 정렬등수 계산:이전 국가와 메달 수가 같다면 같은 순위다르면 현재 인덱스 +..

📌 문제 개요🔗 백준 25644번: 최대상승문제 설명주가가 N일간 어떻게 변할지 알 때,주식 1주를 적절한 날에 사고 팔아 최대 이득을 구하기조건날짜 수 N (1 ≤ N ≤ 200,000)각 날의 주가 a₁ ~ aₙ (1 ≤ aᵢ ≤ 10⁹)목표한 번만 사고, 한 번만 팔때 최대 이익 계산💡 문제 분석단 한 번의 매수/매도 → 이전 최솟값 대비 최대 이익두 수 i i a[i] > a[j]라면 이득 = 0🔑 아이디어 도출브루트포스 O(N²) ❌ → 시간초과 발생한 번의 순회(O(N))로 해결 가능🚫 잘못된 접근 – 완전탐색 ❌for (int i = 0; i 모든 쌍 (i, j)에 대해 이익 계산 → O(N²)최대 4 × 10¹⁰ 연산 → 시간 초과 확정🧩 풀이 전략핵심 아이디어현재 가격이전까지 ..

백준 4782번 사탕 가게 문제는 정해진 예산 안에서 최대 칼로리를 얻는 방법을 찾는 문제로,Unbounded Kapsack (중복 구매 가능) 유형의 전형적인 DP 문제 입니다.🔍 문제 요약문제 링크: 백준 4781번 사탕가게 목표: 총 예산 T센트를 초과하지 않으면서 최대한 많은 칼로리의 사탕 구매조건:사탕 개수 N (1 사탕 가격 P , 사탕 칼로리 C사탕은 중복 구매 가능하다제한:T 100.00 달러에서 센트로 정수 전환 필요출력:최대로 얻을 수 있는 칼로리 값1. 💡 문제 분석무제한 중복 구매 가능 -> Unbounded Knapsack 문제가격이 float(달러)로 주어짐 -> int(센트)처리같은 사탕을 여러 번 살 수 있음.2. 🔑 아이디어 도출가격 단위를 센트 단위로 정수 변환DP..

배낭 문제 (Knapsack Problem)🎒📌 1. 0/1 배낭문제 (0/1 Knapsack Problem)문제설명물건이 N 개, 각 물건은 weight[i] 와 가치 value[i] 존재최대 무게 `W` 제한각 물건은 한 번씩만 선택 가능목표 : 무게 조건내용중복 선택❌목표최대 가치시간 복잡도O(N * W)알고리즘DPDP 정의 및 점화식dp[i][w]: i번째 물건까지 고려, 총 무게 w일 때 최대 가치if (w >= weight[i]) dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]); else dp[i][w] = dp[i-1][w]; 최적화 (1차원 DP)for (int i = 0; i = weight[i]; w--) { ..

STL 컨테이너란?Standard Template Library템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스메모리 자동관리 -> 메모리 단편화💡 std::queuedeque란?양쪽 끝에서 삽입/삭제가 가능한 동적 배열 컨테이너빠른 삽입과 삭제 연산이 필요할때 사용한다.deque는 스택과 큐의 장점을 결합한 자료구조특징시간 복잡도 인덱스 접근 O(N)삽입 / 삭제 O(1)양방향 삽입 & 삭제랜덤 엑세스 지원 : 인덱스로 접근 가능메모리 분할 저장 : 연속된 메모리 블록이 아닌 여러 블록을 연결하여 저장중간 삽입/삭제시 속도 향상 : 랜덤접근이 가능하며, vector 보다 효율적자동 크기 조절 : vector 처럼 동적으로 크기가 조정된다. 📍 queue 사용 예제#include #inclu..

2025.02.17 - [C++] - [C++] STL 컨테이너 - Stack 메모리 단편화💡 std::stack스택이란?LIFO (Last-in First-out)후입선출 자료구 - 마지" data-og-host="my-twinkle-tech-tales.tistory.com" data-og-source-url="https://my-twinkle-tech-tales.tistory.com/1" data-og-url="https://my-twinkle-tech-tales.tistory.com/1" data-og-image="https://scrap.kakaocdn.net/dn/k3vPE/hyYfHOGt9j/ZNhZXC8TvxWKFQDK4J54W0/img.png?width=512&height=512&face..

STL 컨테이너란?Standard Template Library템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스메모리 자동관리 -> 메모리 단편화💡 std::stack스택이란?LIFO (Last-in First-out)후입선출 자료구 - 마지막에 들어온 데이터가 가장 먼저 나가는 구조연속적인 메모리를 사용하지 않고 동적 크기 조절이 가능하다.시간복잡도 - O(1)stack의 주요 연산s.push(x) - 스택의 맨 위에 x 삽입s.pop() - 스택의 맨 위 요소 제거s.top() - 스택의 맨 위 요소 반환s.empty() - 스택이 비어있는지 확인 (boolean)s.size() - 스택의 현재 크기 반환C++에서 스택 사용법#include #include // stack 라이브러리usi..