목록C++ (16)
컴공댕이 공부일지
[ C++/cpp ] 백준 (11726 2×n 타일링) ⭐다이나믹프로그래밍
백준 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; } // 봉지 갯수를..
백준 11268번 절댓값 힙 ( 실버 1 ) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net (정답 코드) #include #include using namespace std; struct cmp { bool operator() (const int& x1, const int& x2) { if(abs(x1) != abs(x2)) { //절댓값 다른경우 절댓값이 작은 수에 우선순위 부여 return abs(x1) > abs(x..
[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이
🔎 그리디 알고리즘(탐욕법)이란? 전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데, 쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다. 단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다. 📖 그리디 알고리즘 문제 출제 경향 단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다. 근사한 해만을 구할 수 있는 경우가 대부분입니다. 그리디 알고리즘은 계산 속도가 빠르기에, 시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다. 그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고, " 탐욕법을 사용해도..
[ 맵과 셋 ] 자료 구조 Map & Set 알아보기 ( + 백준 9375번 패션왕 신해빈 )
📌 맵(Map)맵은 키(key)와 값(value) 사이의 연관성을 나타내는 자료구조맵은 일반적으로 이진 검색 트리를 기반으로 구현되고, 키의 *정렬된 순서를 유지합니다. * 문제에 따라, 정렬된 순서가 필요없다면, 순서없는 맵도 사용하곤 하는데, 밑에서 문제 풀며 자세히 다룸 !!맵(Map)의 주요 특징:키와 값 사이의 일대일 관계 유지마치 한영사전같은 느낌.. key는 사과, value는 apple. 둘이 짝지어져서 사과라는 키 값으로 apple을 서치 가능.키는 중복 X. 즉, 각 키는 유일해야 합니다.한영사전에 사과가 여러개일 순 없져 ㅎㅅㅎ키를 기준으로 정렬됨📌 셋(Set)중복된 값을 허용하지 않는 자료구조집합(set)과 유사하며, 고유한 값들을 저장하고 조회할 수 있음셋도 내부적으로 이진 검..
[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦
백준 2840번 행운의 바퀴(실버 4) https://www.acmicpc.net/problem/2840 2840번: 행운의 바퀴첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓www.acmicpc.net (정답 코드)#include #include using namespace std; // 시계 방향으로 바퀴가 돌면, 바퀴를 고정된 배열로 뒀을 때, 화살표는 반시계로 도는 것이다. // 양의 방향을 반시계방향이라 가정하고, 모듈러 연산을 통해 바퀴를 채워나갈 것이다. // 바퀴에 같은 글자는 두 번 이상 등장하지 않는다 !!!!!!!! int setWheel(int ..