우주수첩의 우주먼지

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #include #include #include #include using namespace std; // 비교하고자 하는 문자열을 아예 저장을 한 후에 진행하였. 땨. string WB[8] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" }; string BW..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net #include #include using namespace std; int main() { int n; cin >> n; pair arr[50]; int rank[50]; for (int i = 0; i > x >> y; arr[i] = make_pair(x, y); } for (int i = 0; i < n; i++) { int cn..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net #include using namespace std; int main() { int n; cin >> n; for (int i = 1; i < n; i++) { int sum = i; int temp = i; while (temp) { sum += temp % 10; temp /= 10; } if (sum == n) { cout

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 브루트 포스 단계에 진입하여땨! 학기중이라 아무것도 안하고 있다가 다시 백준 문제 풀기를 시작하여땨 #include using namespace std; int main() { int n, m; cin >> n >> m; int input_arr[100]; for (int i = 0; i > input; input_..

Hㅏ.... 알응 시험이 4일 남았.땨. 유클리드 호제법을 냅다 공부하다가 tie를 만나서 소개하러 왔당. #std::tie pair, tuple로 묶인 data들을 여러 변수에 한 번에 받아올 수 있다. ex) tuple gcd(int a, int b){ if(b==0){ return{1,0,a}; }else{ int x,y,g; tie(x,y,g)= gcd(b,a%b); return { y, x-(a/b)*y, g}; } } gcd를 구하는 함수를 작성하여 tuple로 반환하도록 하였.땨. 결과 값을 tie를 사용해서 한번에 받아올 수 있겠 된다.

https://codeforces.com/problemset/problem/633/A #include #include using namespace std; int main() { int a, b, c, d, check; cin >> a >> b >> c; /* * ax + by = c일 때 * by = c-ax이고 * 이는 c-ax가 b의 배수임을 알 수 있다. * 완전 탐색을 사용하여 c-ax의 값이 b의 배수인지 찾아낸다. */ check = 0; for(int i=0; i

이전 포스팅 https://dusty-wznt.tistory.com/85 에서 Prime에 대해 다뤘고 그와 동시에 에라토스 테네스의 채의 원리를 너무나도 완 벽 하 게 이해를 해버렸.땨. # 에라토스 테네스의 체 주어진 integer x가 prime인지에 대한 여부를 쉽게 판별할 수 있도록 processing 해주는 알고리즘. prime 여부는 크기가 n인 array에 저장되며 (이해를 돕기 위해 sieve라고 하겠다. sieve == 체) i>2에 대하여 sieve[i] ==0이면 i는 prime이고 sieve[i]==1이면 i는 !prime이다. 이처럼 배열은 해당 index가 prime인지에 대한 여부를 저장한다. 여기서 에라토스 테네스의 채를 구현할 때 key idea가 될 조건은 앞서 포스팅 ..

거 참 제목 하나 영어로 썼다고 간지나는 거 보소. 이전에 에라토스 테네스의 체를 포스팅 한 적이 있다. https://dusty-wznt.tistory.com/19?category=1061713 이때는 그냥 코드 구현만 하고 자세한 설명이 없었는데 수업을 듣다가 원리를 깨달아 버렸다. 만약 N이 prime이 아니라면 두 positive integer a,b >1에 대하여 n=a*b로 나타낼 수 있다. 이 경우 a or b는 반드시 √n 을 넘지 않는다. bool prime(int n){ if(n

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1659 Online Judge Our Patreons Diamond Sponsors Steven & Felix Halim Reinardus Pradhitya Gold Sponsors --- YOUR NAME HERE ---- Silver Sponsors --- YOUR NAME HERE ---- Bronze Sponsors Christianto Handojo Krzysztof Adamek Fatima Broom Amal Augustine Contribute Bitcoin onlinejudge.org N | M 의 계산 값이 최대가 되는 L과 U 사..

Greedy 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. # 동작하기 위한 조건 Logical oprimum의 존재 greedy한 방법으로 global optimal solution에 도달 가능하다는 것을 증명 가능해야 함 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. # 문제 해결 방법 선택 ..