젠의 전공공부

[C++] 1463번 1로 만들기

문제https://www.acmicpc.net/problem/1463풀이1. 접근 방식현재 숫자 i를 1로 만드는 최소 연산 횟수는 이전 숫자들의 연산 결과를 이용해 계산할 수 있음DP 테이블 정의dp[i]: 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수2. 점화식숫자 i에서 가능한 연산을 고려하여 최소값을 계산1을 뺀 경우: dp[ i ]=dp[ i − 1 ] + 12로 나눈 경우 (i가 2로 나누어 떨어질 때만): dp[ i ] = dp[ i / 2 ] + 13으로 나눈 경우 (i가 3으로 나누어 떨어질 때만): dp[ i ] = dp[ i / 3 ] + 1=> dp[ i ] = min⁡(dp[ i − 1 ] + 1, dp[ i / 2 ] + 1 (if  i % 2 == 0), dp[ i / 3 ..

[C++] 1003번 피보나치 함수

문제https://www.acmicpc.net/problem/1003풀이2025.01.13 - [분류 전체보기] - [C++] 다이나믹 프로그래밍 [C++] 다이나믹 프로그래밍다이나믹 프로그래밍(Dynamic Programming)은 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 기법, 최적 부분 구조와 중복된 하위 문제가 있는 문제에 적합 재zenstudy.tistory.com1. 문제 분석F(0)이 호출될 때마다 0이 출력되고, F(1)이 호출될 때마다 1이 출력문제는 F(n)을 계산할 때 총 몇 번 0과 1이 호출되는지를 구하는 것재귀의 비효율성단순히 재귀로 계산하면, 같은 값에 대해 중복 호출이 많이 발생하여 비효율적F(5) 계산 시:F(5)는 F(4)와 F(..

[C++] 다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)은 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 기법, 최적 부분 구조와 중복된 하위 문제가 있는 문제에 적합 재귀 방식의 비효율성int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2);}=> 중복된 하위 문제를 반복 계산1. 메모이제이션(탑다운 방식)재귀 호출 중 계산 결과를 저장(캐싱)하여 중복 계산을 방지#include #include using namespace std;vector dp(100, -1); // -1로 초기화 (아직 계산되지 않음)in..

[C++] map, unordered_map

map은 C++의 표준 라이브러리 에 정의된 키-값(key-value) 쌍을 저장하는 연관 컨테이너, 각 키는 고유하며, 자동으로 정렬unordered_map은 정렬 X, 빠른 검색/삽입/삭제가 중요한 경우 사용  1. 삽입map[key] = value;: 키를 이용해 값 저장 (기존 값이 있으면 덮어씀)insert({key, value});: 쌍을 삽입map["key"] = value;map.insert({"key", value});2. 검색map[key];: 키로 값 검색 (없는 키를 참조하면 기본 값이 생성됨)find(key);: 키를 찾고 iterator 반환 (end()이면 키 없음)if (map.find("Alice") != map.end()) { std::cout 3. 삭제erase(k..

[C++] 재귀 함수

C++ 재귀 함수에 대한 설명재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법재귀 함수의 기본 구조void recursiveFunction() { // 종료 조건 (Base Case) if (/* 조건 */) { return; } // 자기 자신 호출 (Recursive Case) recursiveFunction();}Base Case (종료 조건): 재귀 호출을 멈추는 조건, 종료 조건이 없으면 무한 루프가 발생하여 프로그램이 중단됨Recursive Case (재귀 호출): 함수가 자기 자신을 호출하여 문제를 더 작은 단위로 해결재귀 함수 예제1. 팩토리얼 계산팩토리얼은 n! = n * (n-1) * (n-2) * ... * ..

[C++] String

C++에서 std::string 사용법 정리C++ 표준 라이브러리의 std::string은 문자열을 처리할 때 사용하는 강력한 클래스입니다. 다음은 std::string의 주요 사용법과 활용 예제입니다.1. 문자열 초기화 및 선언기본 선언 및 초기화std::string str1; // 빈 문자열std::string str2 = "Hello"; // "Hello"로 초기화std::string str3("World"); // "World"로 초기화std::string str4(5, 'A'); // "AAAAA" 생성 ('A'를 5번 반복)2. 문자열 입력 및 출력표준 입력과 출력std::string name;std::cout > nam..