본문 바로가기

공부65

배낭 문제(Knapsack Problem) 제한된 용량을 가진 상태에서 여러 개의 아이템을 선택하여 최대 가치를 구하는 방식입니다. 이때 아이템의 무게를 나눌 수 있는지 없는지로 나눠집니다. 1. 0-1 배낭 문제 각 아이템은 선택하거나(1) 선택하지 않거나(0) 두 가지 경우만 존재할 경우DP를 사용하여 해결하며, 시간 복잡도는 O(nW)문제 정의배낭의 최대 용량이 Wn개의 아이템이 있으며, 각 아이템 i는 무게 w[i]와 가치 v[i]를 가진다.배낭에 넣을 수 있는 최대 가치를 구하는 것이 목표이다. 코드# 0-1 Knapsack Problem (Dynamic Programming)def knapsack_01(W, weights, values, n): dp = [[0] * (W + 1) for _ in range(n + 1)] .. 2025. 2. 28.
알고리즘 접근 방법 1. 문제를 읽고 이해한다.2. 문제를 익숙한 용어로 재정의한다.3. 어떻게 해결할지 계획을 세운다.4. 계획을 검증한다.5. 프로그램으로 구현한다.6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. 나는 보통 계획을 세운 후(3번) 바로 구현하려고 하는데 검증하는 과정(4번)을 추가해야겠다. 작은 기능에서 시작해서 점차 키워가기 => 점진적 개선문제를 풀 수는 없더라도 해결법을 알아가는데 도움을 줌 2025. 2. 24.
C++ - stack, que, deque, priority_que 자료구조 특징 삽입 삭제조회Stack (LIFO)후입선출push()pop()top()Queue (FIFO)선입선출push()pop()front(), back()Priority Queue우선순위 높은 원소가 먼저 나감push()pop()top()Deque양쪽 삽입/삭제 가능push_back(), push_front()pop_back(), pop_front()front(), back() 어떤 것을 써야 할까?스택: "뒤집기", "DFS", "연산기록 저장"큐: "선입선출", "BFS", "작업 스케줄링"우선순위 큐: "최댓값/최솟값 관리", "힙(Heap) 활용"덱: "양방향 삽입/삭제", "슬라이딩 윈도우" 2025. 2. 22.
String을 replace 하는 방법들 방법사용목적코드str.replace(위치, 길이, 새 문자열)특정 위치의 문자열을 변경str.replace(6, 5, "C++");std::regex_replace()여러 개의 특정 문자열 변경(정규식 가능)std::regex_replace(str, std::regex("apple"), "banana")std::replace()특정 문자 변경std::replace(str.begin(), str.end(), 'a', 'X');std::string::find() + replace()문자열 전체 변경 (반복)while ((pos = str.find(...)) != std::string::npos) str.replace(...);std::erase() + std::remove()특정 문자 제거str.erase(.. 2025. 2. 22.
C++ 자료형과 변수 C++에서는 일반적으로 기본 자료형으로 정의한 것을 변수, 사용자 정의 자료형으로 정의한 것을 객체라 함. //! 정의 : 자료형 변수명;bool b; /// 기본 자료형 정의 및 초기화int n = 0;int n(0);int n = {0};int n{0};// 64bit systembool b = true; // mov BYTE PTR [rbp-1], 1 # 1 bytechar c = 'a'; // mov BYTE PTR [rbp-2], 97 # 1 byteint n = 0; // mov DWORD PTR [rbp-8], 0 # 4 byte (rbp-8 ~ 5까지)long l = 0; .. 2025. 2. 21.
다익스트라(Dijkstra) - Python, heapq 코드import heapqimport sysdef dijkstra(graph, start): INF = float('inf') n = len(graph) distance = [INF] * n distance[start] = 0 pq = [] heapq.heappush(pq, (0, start)) # (거리, 정점) while pq: dist, now = heapq.heappop(pq) if distance[now]  과정  거리 배열 초기화: 시작 정점에서 모든 정점까지의 최단 거리를 무한(∞)으로 설정, 시작 정점의 거리는 0으로 설정우선순위 큐(Priority Queue) 사용: 시작 정점을 큐에 넣음 (우선순위 큐는 Python.. 2025. 2. 7.

티스토리툴바