[c++] 백준 1850 최대공약수 : 유클리드 호제법(GCD)

문제 https://www.acmicpc.net/problem/1850막 어려운 문제는 아닌데 유클리드 호제법 까먹어서ㅎ... 문제 분석최대 공약수(GCD, Greatest Common Divisor)란 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미한다.처음에는 뭔가 싶고 문제가 막 어렵게 꼬여있는것 같아 보이지만, 규칙을 찾아내면 쉽다.test1) 3 4  ans) 1 -> 3과 4의 최대공약수 == 1 -> 1을 1번 출력test2) 3 6  ans) 111 -> 3과 6의 최대공약수 ==3 -> 1을 3번출력결국 주어진 두 수의 최대공약수를 구하면되는데, 그 수가 좀 클 뿐이다.그래서 유클리드 호제법을 이용해서 구해주는것이 옳다.  유클리드 호제법 증명- 참고 : https://ddddewan..

• format_list_bulleted 백준
• · 2024. 10. 22.
• textsms

[c++] 백준 1339 단어 수학 : 그리디

문제https://www.acmicpc.net/problem/1339 문제 분석아 뭐야 줫나 쉽네 자릿수 높은거에 높은 숫자 주면 되잖아ㅋㅋㅋ하면 실패다.ACDBB  BFGC이렇게 두개 들어오는경우 C보다 B에 큰수를 줘야한다.  아 그러면 더 많이 나오는거에 큰수를 주면 되겠구나!ACBHICC   BDEFGC인경우 C가 더 많이 나왔지만 B에 더 큰수를 할당해줘야한다. 아 자릿수가 높으면 더 큰 수를 줘야하는구나! -> 자릿수가 높을수록 높은 가중치를 줘서 가중치가 가장 높은 문자에 높은 숫자를 할당하자! 정답코드//24.9.28(토) 1339 단어수학#include#include#include#include#includeusing namespace std;int main(){ ios::sync_..

• format_list_bulleted 백준
• · 2024. 9. 29.
• textsms

[c++] 백준 17298 오큰수 : 스택

문제https://www.acmicpc.net/problem/17298 문제 분석Ai의 오큰수 : Ai 보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수우선 뒤에 계속 들어오는데 크다 어찌다 그러면 스택 의심해봐야할듯  대충 들어오는 수가 냄비뚜껑 이라고 생각하고 내가 커버할 수 있는 그릇들 찾는다고 생각햇다.7 4 3 들어오면 아래처럼 되고  만약 5짜리가 들어오면 3이랑 4는 커버 되지만 7짜는 크기 5짜리 뚜껑으로는 커버 안되겠지 정답코드//24.9.28(토) 17298 오큰수#include#includeusing namespace std;int main(){ ios::sync_with_stdio(0);cin.tie(0); int n; cin>>n; int ret[..

• format_list_bulleted 백준
• · 2024. 9. 28.
• textsms

[c++] 백준 2812 크게 만들기 : 그리디

문제https://www.acmicpc.net/problem/2812 문제 분석우선 앞자리가 크면 숫자가 커짐!! -> 나보다 다음 수가 더 크면 나를 지워서 뒷 숫자가 더 앞자리에 오도록 함을 반복하면 된다.   정답코드//24.9.22(일) 크게 만들기 -> 앞자리수가 크면 암튼 큰거!#include#include#includeusing namespace std;int main(){ int n,k;cin>>n>>k; string str; cin>>str; deque dq; //뒤로 넣고 앞부터 출력할거라 dq.push_back(str[0]); for(int i=1;i 지금보면 덱 쓸거면 큐를 임포트 해야하는데 왜 스택해놨냨ㅋㅋㅋㅋㅋ 그래도 뭐... 통과 하긴 함 .... 그..

• format_list_bulleted 백준
• · 2024. 9. 27.
• textsms

[c++] 백준 11053 가장 긴 증가하는 부분 수열 : DP

문제https://www.acmicpc.net/problem/11053 문제 분석음 분석이라기 보다는 디피인거 스포당해서;;;처음에는 그냥 thisSum totalSum 이용해서 풀었는데(올라가다가 꺾이면 totalSum을 update 하는 방식-> 한번만 훑으면 됨) 어차피 틀린 매커니즘이라 자세한 설명은 생략. 저 방식의 문제는 다음과 같은 테케를 해결하지 못한다. 81 8 9 9 9 2 3 4 이 경우 위와같은 방식으로 구하면 1,8,9 이렇게 하고 3이 나오는데,사실 1,2,3,4 이렇게 증가하면 4가  된다.  즉 1->8 이렇게 가야할지 1->2 이렇게 가야할지 모르니까 다 확인해봐야함..... -> 근데 반복적으로 필요한 값이 있으니 매번 계산하지 않고 기록해뒀다가 이후에도 이용하겠다 -> ..

• format_list_bulleted 백준
• · 2024. 9. 25.
• textsms

[c++] 백준 1629 곱셈 : 분할 정복을 이용한 거듭제곱

문제https://www.acmicpc.net/problem/1629 문제 분석에 사실 이걸 거창하게 '분할 정복을 이용한 거듭제곱'이라고 할것도 없이 간단한 수학이다.저런식으로 재귀 돌리면 끝! 정답코드#includeusing namespace std;long long a,b,c; long long recur(int n){ //base step if(n==1){ return a%c; } //recursive step long long tmp = recur(n/2); if(n%2){ //홀수일때 return (tmp*tmp%c*a)%c; } else{ //짝수일떄 return (tmp*tmp)%c; }}i..

• format_list_bulleted 백준
• · 2024. 9. 12.
• textsms