세모

[백준/실버1] 백준 28117번 prlong longf - c++ (dp) 문제 모든 int가 longlong으로 바뀐 문자열이 주어진다. 가능한 원래 문자열은 모두 몇 가지인가? -> longlong을 int로 바꿀 수 있는데 만들 수 있는 문자열의 개수 문제 해설 long => A로 치환 int => B로 치환 AA -> B로 바꿀 수 있음 long의 개수 나올 수 있는 경우 경우의 수 A(1) / 0 X 1 AA (2) AA / B 2 AAA (3) BA / AB / AAA 3 AAAA (4) BAA / ABA / AAB / BB / AAAA 5 (2+3) AAAAA (5) BAAA / ABAA / AABA / AAAB BBA / BAB / ABB / AAAAA 8 (3+5) AAAAAA (6) ..

알고리즘/C++ 2024. 4. 11. 18:23

[백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp) 어렸을 때 풀었던 그냥 값을 무작정대입하는 방정식과 같은 문제다. 다른 dp문제는 점화식 세울 때 초기 값을 세우기 쉬웠는데 예) 피보나치 1 1 .. 이건 초기값이 하나밖에 주어지지 않았다. 그래서 거꾸로 가는 방식으로 채택해야하는데 이것도 초기값이 주어진게 하나밖에 없어서 쉽지 않았다. 그래서 어렸을 적 배운 방정식을 이용해보았다. 1 2 3 4 5 6 a b a+b a+2b 2a+3b 3a+5b 이렇게 나온다. 그래서 이걸 어떻게 구현해줄수 있을까... 고민하였다. 사실 저 식은 진짜 금방알아냈는데 이걸 코드로 어떻게 구현하고, 시간 초과가 되지 않을지 너무너무 고민되었다.. 스택으로 풀어야할지.. 그냥 단순하게 변수로 개수를 정..

알고리즘/C++ 2024. 4. 10. 11:52

[백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬 하나하나 비교해가면서 풀면 100% 시간초과가 날 것이다. 해당 문제는 이분 탐색의 교과서 같은 문제 이분 탐색은 맨 오른쪽, 왼쪽 점을 잡은 뒤 mid 를 정하고 또 이걸 반복해주는 것이다. 중요한 것은 "정렬"을 해줘야 한다는 점이다. 그래야 12345 라고 쳤을 때 mid인 3보다 목표 숫자가 작으면 그 앞에 있거나 없거나 하고 크면 뒤에 있거나 없거나 하면서 비교해볼 수 있기 때문이다. 1) 직접 구현 #include using namespace std; int n,m, num; vector v; int binary_search(int a){ int r=n-1, l=0; while(r>=l){ int mid = (r..

알고리즘/C++ 2024. 4. 4. 13:21

[백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹) N과 M 시리즈는 엄청 많아서 1을 통해 dfs랑 백트래킹을 익히는 것에 초점을 뒀다. 그리고 해당 코드를 암기해서 다른 것들에 응용하는게 수월할 것 같다. 코드 #include using namespace std; int n, m; int arr[9]; int arred[9]; void dfs(int idx){ if(idx == m){ for(int i=0; i dfs(2) -> if문 실행 > arred[2] =0; 2)(idx ==1 인 상태) arred[3] ==0 -> arr[1] =3 arred[3] =1; -> dfs(2) -> if문 실행 -> arred[3] =0; 3)(idx ==1 인 상태) arred[4]..

알고리즘/C++ 2024. 3. 23. 18:26

[백준/실버4] 백준 10610번 30 - c++ (수학/그리디 알고리즘/ 문자열/ 정렬/ 정수론) 문제 해석/코드 설명 중요 포인트 - N는 최대 10^5개의 숫자로 구성 - 30의 배수의 특징 1. 0이 들어가 있어야 한다. 2. 원소의 합이 3의 배수여야 한다. 코드 #include #include using namespace std; int main (){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string num=""; //10^5까지니깐 string으로 받아줌 cin >> num; sort(num.begin(), num.end(), greater()); //내림차순 정렬 bool zero=0; long lo..

알고리즘/C++ 2024. 3. 18. 20:51

[백준/실버5] 백준 10814번 나이순 정렬 - c++ (정렬 알고리즘) 문제 해석/코드 설명 코딩테스트 타파하기 1주차 - 3번 문제 해석 1. 나이 순으로 정렬 2. 나이가 같으면 가입한 순 (값이 들어간 순서대로) 중요한 함수 sort() 기존 순서를 보장하지 않는다. stable_sort() 기존 순서를 보장한다. 문제에서 입력된 순서로 출력을 원했으니 stable_sort를 이용해줘야한다. vector v; // 에 값 넣는 법 cin >> age >> name; v.push_back(make_pair(age, name)); vector v(n); // -> 크기 지정 cin >> v[i].first >> v[i].second; 전체 코드 #include #include #include usi..

알고리즘/C++ 2024. 3. 14. 11:49

[백준/실버3] 백준 2108번 통계학 - c++ (수학/ 구현/ 정렬 알고리즘) 문제 해석/코드 설명 코딩테스트 타파하기 1주차 - 2번 문제 해석 산술평균 : N개의 수들의 합을 N으로 나눈 값 => 들어오는 값들을 다 더하면 된다. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 => 사이즈에서 /2를 해주면 그 인덱스가 중앙값이 된다 (주의 : 무조건 수의 개수가 홀수이기 때문에 case를 수가 짝수인지 홀수인지로 안나눠도 된다.) 최빈값 : N개의 수들 중 가장 많이 나타나는 값 => 배열을 생성해서 각 인덱스 별로 몇개가 있는지 알아둔다. 만약 maxidx가 1보다 크면 같은게 여러개니깐 '두 번째'수를 출력해줘야한다. 범위 : N개의 수들 중 최댓값과 최솟값의 ..

알고리즘/C++ 2024. 3. 12. 19:36

[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 코딩테스트 타파하기 1주차 - 1번 주요 키 포인트 유클리드 호제법 (최대공약수) 2개의 자연수(또는 정수) a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (이때, a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 아래의 코드를 살펴보면 int gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b, a%b); } 연쇄적으로 최대공약수를 찾아가는 것을 볼 수 있다. 성질에 따라서 b를 r로 나눈 나머지를 구하고 다시 이것들을 연쇄적으로 진행해서 나머지가 0이 되었을 때 나누는 수 ((a%b)에서 b)가 a와 b..

알고리즘/C++ 2024. 3. 12. 15:43