목록C++ (18)
컴공댕이 공부일지
[ C++/cpp ] 백준 (9095 1, 2, 3 더하기) ⭐DP
백준 9095번 1, 2, 3 더하기(실버 3) 문제링크 https://www.acmicpc.net/problem/9095 (정답 코드)#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, t; int dp[12]; dp[1]=1; dp[2]=2; dp[3]=4; cin >> t; while(t--) { cin >> n; for(int i=4; i 📖 풀이 이전까지의 값들이 뭔가 메모리제이션되면서 중첩되어 최종 답을 구하게 되는 느낌 == 전형적인 dp 문제다. i-1, i-2, i-3의 값들에 +1, ..
[실전 알고리즘] 0x0B강 | 재귀 (Recursion) - 이론부터 예제 문제풀이까지, 재귀 문제의 구조 완벽 익히기 😎
🔎 재귀(Recursion)란? 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘.재귀가 낯설고 어렵게 느껴지는 이유는 우리가 기존에 생각하던 "절차지향적 사고"를 탈피해야하기 때문. 절차 지향적 사고 vs 귀납적 사고도미노로 예시를 들면, - 절차 지향적 사고1번 도미노, 2번째 도미노, 3번째 도미노 ... 이렇게 순차적으로 쓰러져서 모든 도미노가 쓰러진다 ! => (각 단계가 순차적으로 실행) - 귀납적 사고- 1번 도미노가 쓰러진다.- k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.=> 모든 도미노가 쓰러진다 ! 는 결론에 도달. 이번 글에서는 바킹독 선생님의 강의를 기반으로, 재귀의 기본 개념을 정리하고, 예제 문제를 풀이해볼 것이다. 📝 재귀 함수의 조건특정 입력..
[ C++/cpp ] 백준 (11726 2×n 타일링) ⭐다이나믹프로그래밍 DP
백준 11726번 2×n 타일링(실버 3) https://www.acmicpc.net/problem/11726 (정답 코드)#include #include #define MOD 10007 // 상수값은 깔끔하게 define 해두기using namespace std;// 피보나치 bottomupint solution(int n) { vector v (n+1, -1); // n+1칸 벡터 초기화 v[0]=1; v[1]=1; for(int i=2; i> n; cout 📖 풀이 N=1일 때, 2x1 크기의 직사각형을 채우는 방법은 1가지.|ㅁ|N=2일 때, 2x2 크기의 직사각형을 채우는 방법은 2가지.|ㅁㅁ| (세로로 2개)|ㅡ| |ㅡ| (가로로 2개)N=3일..
[ C++/cpp ] 백준 (5430 AC) ⭐구현, 덱
백준 5430번 AC(골드 5) https://www.acmicpc.net/problem/5430 (정답 코드)#include #include using namespace std;string solution(string &p, int &n, string &arr) { deque dq; string ans = "["; string num = ""; bool is_reverse = false; // 숫자 배열 벡터에 차례로 저장 for(int i=1; i> t; while(t--) { cin >> p >> n >> arr; cout 📖 트러블 슈팅1. 문자열 파싱 오류구분자 ',' 기준으로 끊어 입력받기### 수..
[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦
백준 1654번 문제이름(실버 2)https://www.acmicpc.net/problem/1654 (정답 코드)#include #include using namespace std;int cnt(int x, const vector& num) { long ans = 0; for(int i=0; i& num, int n, long sum) { long left = 1; long right = sum/n; // 토막 가능한 최대 길이 long mid; while(left=n ) { left = mid+1; } else { right = mid-1; } } return rig..
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열
백준 2108번 통계학(실버 3) https://www.acmicpc.net/problem/2108 (정답 코드)#include #include #include #include using namespace std;int findMode(const vector& num, int max_length) { if(num.size() == 1) return num[0]; // 값이 하나뿐이면 그 값이 최빈값 int mode; int l=0; bool finded = false; int start = 0; int end = 0; for(int i=0; i num; vector cnt(8001, 0); // 8001칸 0으로 초기화 ..
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘
백준 1018번 체스판 다시 칠하기 ( 실버 4 ) https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net (정답 코드) #include #include using namespace std; // 8x8 규격 내 바꿔야하는 칸 수 체크하는 함수 int check(int x, int y, const vector& bw, char ch) { int cnt_change = 0; for(int i=0; i m ; vector bw (n, vector(..
백준 2839번 설탕 배달 ( 실버 4 ) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net (정답 코드) #include using namespace std; int sugarDelivery(int n) { int last3mul = -1 ; // 5를 빼며 나온 3 배수 저장 int ans = 0; int copy_n = n; // 5로 나누어떨어지는 경우 5로 나눈 몫 바로 return if(n%5==0) { return n/5; } // 봉지 갯수를..