Algorithm

안녕하세요, iOS 개발하는 루피입니다. 오늘은 백준 1629번 곱셈 문제를 풀어보겠습니다. 바로 시작합니다.풀이#includeusing namespace std;typedef long long ll;ll func(ll a,ll b,ll c) { if(b==1) return a%c; // 기저 사례 ll ret = func(a,b/2,c); ret = (ret*ret)%c; if(b % 2 ==1) ret = (ret*a)%c; return ret;}int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); ll a,b,c; cin >> a >> b >> c; cout 핵심은 ..

안녕하세요, iOS 개발하는 루피입니다. 오늘은 백준 4375번 1 문제를 풀어보겠습니다. 바로 시작합니다.https://www.acmicpc.net/problem/4375풀이#includeusing namespace std;int main() { int num; while(cin>>num) { int k=1; int i =1; while(1) { // 핵심 코드 if(k%num == 0) { cout 코드가 짧기 때문에 핵심 코드 부분만 정리해 보도록 하겠습니다. k = k*10 +1 을 모듈로 계산하고 넣지 않을 경우 수가 너무 커지기 때문에 시간 초과가 날 것입니다.따라서 k = (k*10+1..

안녕하세요, iOS 개발하는 루피입니다. 오늘은 백준 9375번 패션왕 신해빈 문제를 풀어보겠습니다. 바로 시작합니다.https://www.acmicpc.net/problem/9375풀이#includeusing namespace std;int main() { int testCase; cin >> testCase; for (int i=0;i> num; mapm; for (int j=0;j> name >> type; m[type]++; } int res = 1; // 핵심 로직 for(auto it : m) res *= (it.second+1); cout 문제를 풀면 사실 상 name은 사용..

안녕하세요, iOS 개발하는 루피입니다. 오늘은 백준 9996번 한국이 그리울 땐 서버에 접속하지 문제를 풀어 보겠습니다. 바로 시작합니다. https://www.acmicpc.net/problem/9996풀이#includeusing namespace std;int main() { int testCase; cin >> testCase; string pattern; cin >> pattern; long long divide = pattern.find('*'); string prefix = pattern.substr(0,divide); string suffix = pattern.substr(divide+1); for ( int i=0;i> str; string t..

안녕하세요, iOS 개발하는 루피입니다. 오늘은 백준 10808 문제를 2가지 방법으로 풀어 보겠습니다. 바로 시작하겠습니다.https://www.acmicpc.net/problem/10808단순 구현을 통한 풀이#includeusing namespace std;int main() { string str; cin >> str; int a[26] = {}; for (int i=0;iMap을 이용한 풀이#includeusing namespace std;int main() { mapm; string str; cin >> str; for ( int i=0;i오늘도 화이팅입니다.

안녕하세요, iOS 개발하는 루피입니다. 오늘은 순열과 조합의 방식으로 백준 일곱 난쟁이 문제를 풀어보도록 하겠습니다. 바로 시작합니다.https://www.acmicpc.net/problem/2309이번 문제는 순열과 조합으로 접근하여 문제를 풀 수 있습니다. 순열과 조합에 대한 알고리즘은 익혀두고 있으면 좋을거 같습니다.순열을 이용한 풀이#includeusing namespace std;int main() { vectorv(9); for ( int i=0;i> v[i]; sort(v.begin(),v.end()); do { int sum = 0; for (int i=0;inext_permutation()을 이용해 매번 다른 순열을 만듭니다.새로 만들어진 ..

안녕하세요, iOS 개발하는 루피입니다! 오늘은 Shuffle 알고리즘에 대해 간략하게 정리해보겠습니다.Fisher-YatesFisher-Yates 셔플 은 유한 시퀀스의 무작위 순열을 생성하는 알고리즘 입니다 . 쉽게 말하면 이 알고리즘은 시퀀스를 셔플합니다.동작원리추출할 대상 인덱스 j를 랜덤하게 선택arr[i]와 arr[j]를 swapvar arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]for i in 0...9 { let j = Int.random(in: i...9) let origin = arr[i] arr[i] = arr[j] arr[j] = origin}// 실행결과: [6, 3, 7, 8, 10, 5, 1, 2, 9, 4] -> 매번 다른 결과 출력됨출처셔플 ( Shuf..

#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); long long N,S; cin >> N >> S; long long arr[1000001]= {0}; long long sum = 0, cnt = 0; for ( long long i=0;i> num; sum += num; arr[sum % S]++; if(sum % S==0) cnt++; } for (int i = 0; i  위 문제를 저는 누적합 방식을 이용하여 풀이 했습니다. 결국 가장 이해가 안되는 로직이자 핵심 부분은 아래  두 부분이라..

#include#include#includeusing namespace std;int main(int argc, char** argv){ int num,testCase; cin >> num >> testCase; vectorv(num); for ( int i=0;i>v[i]; } for( int i =0;i> a >> b; int sum = 0; for ( int j=a;j 소수점 셋째 자리에서 반올림을 진행하기 때문에 소수점을 고정 할 필요가 있습니다.fixed는 소수점 아래 이후부터 고정시키겠다는 표현입니다.cout.precision를 호출하여 출력되는 숫자의 자릿수를 결정하게 됩니다.fixed를 사용하지 않으면, 전체 모든 숫자의 갯수로 설정하게 ..

#include #include using namespace std;bool visited[501];vector graph[501];void DFS(int now, int depth) {/// 본인의 친구와 본인의 친구의 친구까지 참가하기에 깊이 2를 넘어갈 필요가 없다. if (depth == 2) { return; } for (int i = 0; i > n >> m; int res = 0; for ( int i=0;i> a >> b; graph[a].push_back(b); graph[b].push_back(a); } visited[1] = true; DFS(1, 0); /// visited == true 갯수 반환..