Algorithm

안녕하세요, 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..

안녕하세요, iOS 개발하는 루피입니다.  이번 글에서는 DFS 문제인 백준 1012 문제를 공부 해보려합니다. 이 문제의 목표는 2차원 배열로 표현된 배추밭에서 상하좌우로 연결된 배추들을 하나의 군집으로 보고, 그 군집의 개수를 세는 것입니다. 이 과정에서 DFS를 사용해 여러 방향으로 연결된 배추들을 한 번에 탐색할 수 있을거 같습니다.전체적인 플로우는 이렇게 될 거 같은데요..배추 좌표를 입력받고 배열에 기록.배추밭을 순회하며 아직 방문하지 않은 배추를 찾는다.DFS를 통해 연결된 배추들을 하나의 군집으로 보고 탐색을 완료.군집의 수를 카운트한 후 출력합니다.변수 설정int board[51][51]; // 배추밭을 표현하는 배열 (최대 50x50 크기)int visited[51][51]; // ..

안녕하세요 iOS 개발하는 루피입니다.  오늘은 백준 13458번 시험 감독 문제를 풀어 보았습니다. 삼성 기출 문제를 풀던 와중 등급이 낮아 쉽게 성공할 줄 알았지만, 예상외로 그렇지 못해 블로그에 작성해보려 합니다.첫 접근 방법처음 총 감독관이 감시할 수 있는 학생수를 제외하고, 필요한 감독관 수를 증가시킨다.나머지 학생수를 부 감독관이 감시할 수 있는 학생 수 만큼 계속 빼고, 이때 필요한 감독관 수를 증가시킨다.이렇게 작성하니 지속적으로 학생수를 빼야 하기에 시간 초과가 났습니다. 브론즈 문제라 사실 시간 초과를 신경 쓰지 않았지만, 이번 기회에 한번 메모리 제한을 생각해야겠다는 생각을 하였습니다.두 번째 접근 방법시간 초과의 원인을 For문을 통한 뺄셈으로 파악했습니다.이를 나누기 방식으로 바꾸..

#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 갯수 반환..

범위 : a 이상 b 이하인 수조건 : 소수출력 : 소수들의 합 #include using namespace std;bool IsPrime(int n) { if(n == 1) return false; for(int i = 2; i > a >> b; int sum = 0; for ( int i=a;i

범위 : a 이상 b 이하 수조건 : 3의 배수인 수 || (3 또는 6 또는 9) 가 포함 된 수출력 : 갯수를 출력 #include #include #include using namespace std;void print(int a, int b) { vectorv; for ( int i = a; i> a >> b; print(a,b); return 0;}정리C++ string 변수에서 해당 숫자가 존재하는지 확인하기 위해 str.find() 함수를 사용했습니다. str.find('?') 함수는 해당 문자가 존재할 경우 찾고자 하는 문자열의 시작 위치를 반환합니다.만약 문자가 없을 경우 -1이 반환되는 것이 아니라 쓰레기 값이 반환되는데, 이를 이용하여 str.find("?") !=..

GCD"2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."LCM"두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. "#include using namespace std;// 최대 공약수int GCD(int a,int b) { if(b == 0) return a; return GCD(b,a%b);}// 최소 공배수int LCM(int a, int b) { return a * b / GCD(a,b);}int main() { // 여기에 코드를 작성해주세요. int a,b; cin >> a >> b; cout

num : 각 자리수의 합을 구하고 싶은 숫자sum : 각 자리수의 합#include using namespace std;int printSum(int num) { int sum = 0; while (num > 0) { sum += num % 10; num /= 10 ; } return sum;}int main() { int num; cin >> num; cout