컴공댕이 공부일지

백준 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..

🔎 그리디 알고리즘(탐욕법)이란? 전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데, 쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다. 단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다. 📖 그리디 알고리즘 문제 출제 경향 단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다. 근사한 해만을 구할 수 있는 경우가 대부분입니다. 그리디 알고리즘은 계산 속도가 빠르기에, 시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다. 그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고, " 탐욕법을 사용해도..

보호되어 있는 글입니다.

백준 2840번 행운의 바퀴(실버 4) https://www.acmicpc.net/problem/2840 2840번: 행운의 바퀴첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓www.acmicpc.net (정답 코드)#include #include using namespace std; // 시계 방향으로 바퀴가 돌면, 바퀴를 고정된 배열로 뒀을 때, 화살표는 반시계로 도는 것이다. // 양의 방향을 반시계방향이라 가정하고, 모듈러 연산을 통해 바퀴를 채워나갈 것이다. // 바퀴에 같은 글자는 두 번 이상 등장하지 않는다 !!!!!!!! int setWheel(int ..

📝 에라토스테네스의 체 소수를 구하는 쉽고 빠른 방법 소수를 판별할 때, 아래와 같이 배수들을 지워나가면서 남은 수들을 소수로 판별하는 과정 ! 이거 중딩? 때 다 해봤을거다ㅎㅎ 위의 그림에서 우린 1부터 50까지 소수를 판별하려고 한다. 그래서 1부터 50까지 다 하나하나 배수를 지워야할 것 같지만, 실제로는 √50 이하의 수들만 확인하면 된다. 왜일까? 왜 하필 루트를 씌운 제곱근 값일까? 🔍 소수 판별 시에 제곱근 이하만 확인하면 되는 이유 🤔 1과 자기 자신이 아닌 약수가 하나라도 있다면, 그것은 소수가 아니다. 8 = 1 * 8 = 2 * 4 = 4 * 2 = 8 * 1 곱해서 8이 되는 조합들이다. 즉, 약수가 1,2,4,8이므로 소수가 아니다. 근데 여기서, 2가 나누어떨어지는 걸 봤는데, ..

유클리드 호제법이란? 두 양의 정수의 최대공약수를 구하는 알고리즘 중 하나로, 두 수가 반복적으로 서로 나누어지면서, 나머지를 구하며 최대공약수를 얻게 된다. 유클리드 호제법의 기본 원리 📝 A,B의 최대공약수 = A-B, B의 최대공약수 * GCD : 최대 공약수( Greatest Common Divisor ) 아하 ! 그러면 A, B의 최대공약수를 구하는 대신, A-B, B를 이용하면 빠르겠군 ! 그런데 A와 B의 차가 크다면 ...? 가령, 1024와 2라고 해보자. GCD (1024, 2) GCD (1022, 2) GCD (1020, 2) GCD (1018, 2) . . . GCD (2, 2) 이걸 어느 세월에....ㅜ 그래서 나온 또 다른 증명 ! 📝 A,B의 최대공약수 = A%B, B의 최대공..

백준 10814번 나이순 정렬 (실버 5) https://www.acmicpc.net/problem/10814 (정답 코드) #include #include #include using namespace std; typedef pair p; bool cmp(const p &a, const p &b) { // 나이순 정렬 if(a.first!=b.first) { return a.first < b.first; } // 나이가 같으면 변화없이 그대로 ! else { return false; // 원래 순서 유지 ! } } void sortUser(vector& user) { // 입력 순서를 보존하는 안정적인 정렬을 보장하는 sort_stable stable_sort(user.begin(), user.end()..

백준 11650번 좌표 정렬하기(실버 5) https://www.acmicpc.net/problem/11650  (정답 코드)#include #include #include using namespace std;typedef pair p;// & : 레퍼런스// const : 상수// 비교함수 정의bool cmp (const p &a, const p &b) { if(a.first!=b.first) { return a.first & xy) { // 참조를 이용한 전달. 벡터 직접 수정 가능 sort(xy.begin(), xy.end(), cmp); }int main(){ ios::sync_with_stdio(false); cin.tie(NULL);..