728x90 반응형 분류 전체보기82 [algorithm] 백준 - 숨바꼭질 2 이 문제는 숨바꼭질 문제와 이어지는 bfs 문제이다. 추가되는 부분은 가장 빠른 시간으로 찾는 방법이 몇가지인지 구해야한다는 것이다. 예를 들어 수빈이는 1 에 위치해 있고 동생은 4에 있다고 가정하면, 가장 빠른 시간으로 찾기 위해선 여러 경우로 가지가 뻗어나갈 때, 동일한 시간에 두가지 방법이 있다는 것을 알 수 있다. 만일 queue에 값을 넣을 때 방문여부를 체크하게 된다면 1+1이나 1*2 중 가장 먼저 값이 넣어지는 경우의 방법만 찾을 수 있게 된다. 그러므로, queue에 값을 넣을 때 방문여부를 체크하지 말아야한다. 그렇다고 모든 방문 여부를 체크하지 말아야할까? 아니다, 방문 여부는 반드시 체크해야한다. 그러지 않으면 숨바꼭질은 끝나지 않는다. 그럼 방문 여부는 언제 체크해야할까? 최소 .. 2020. 11. 17. [algorithm] 백준 - 스타트와 링크 이 문제는 재귀 문제이다. 사람을 스타트팀에 넣는 경우, 링크 팀에 넣는 경우로 재귀 함수를 구현한다. 스타트팀에 구성된 인원 수 : n/2 링크 팀에 구성된 인원 수: n/2 가 아닌 경우도 포함되겠지만, N(4 ≤ N ≤ 20, N은 짝수) 이므로 2초를 넘을 위험은 없다. start.push_back(index); permutation(index + 1); start.pop_back(); link.push_back(index); permutation(index + 1); link.pop_back(); 스타트팀과 링크팀에 구성된 인원 수가 n/2로 채워졌을 때, 능력치를 더하고, 가장 능력치 차가 나지 않는 경우의 수를 저장한다. if(index == n){ if(start.size() ==n / 2.. 2020. 11. 17. [algorithm] 백준 - 단어수학 이 문제를 greedy로 풀었다. 알파벳 별로 자릿수를 더한 수를 구한 후 배열 내에 담는다. ABCA A) 1001 B) 100 C) 10 for(int i = 0; i = 0; j--){ word[wordVector[i][j] - 'A'] += powNum; powNum *= 10; } } 그리고 알파벳 배열을 내림차순으로 정렬 후 9부터 0까지 자릿수를 더한 수와 곱하면 알파벳 수의 합을 최대로 만들 수 있다. 9009 + 800 + 70 = 9879 sort(word, word + 26, compare); int number = 9, answer =.. 2020. 11. 14. [algorithm] 백준 - 소인수분해 브루트 포스로 해결할 수 있다. n이 1이 될 때까지 나누어준다. //소인수분해 #include using namespace std; int main(void){ int n, k = 2; cin >> n; while(n != 1){ if(n % k == 0){ n = n / k; cout 2020. 11. 13. [algorithm] 백준 - 부분 수열의 합 2 brute force 문제이다. 정수의 개수는 40개이므로 2 ^ 40 번의 연산을 필요로 하니까 시간 제한 내에 풀기 위해 반으로 쪼개서 연산해야한다. 절반을 기준으로 leftDfs rightDfs로 나누어서 풀었다. leftDfs의 경우, 부분 수열의 합의 개수를 저장하고, rightDfs에서는, 구하고자 하는 합 - rightDfs에서 연산한 부분 수열의 합이 있는지 찾은 후 answer에 추가시키는 방식으로 풀었다. 그리고 구하고자 하는 합이 0일 경우, leftDfs에서 부분 수열의 합에 포함되는 수가 없는 경우, rightDfs에서 부분 수열의 합에 포함되는 수가 없는 경우로 동일한 경우가 2번 연산되므로 한번 빼준다. //부분 수열의 합2 #include #include #include #i.. 2020. 11. 10. [algorithm] 백준 - 카잉 달력 이 문제는 시간 제한이 1초인 것에 유의해야하는 문제이다. 두 자연수의 최소 공배수까지 반복문을 돌며 나머지 값과 동일한 경우를 구하게 되면 40000 * 40000 이상의 연산은 1초를 넘게 되서 시간 초과가 난다. 참고로 최소 공배수까지 반복문을 도는 이유는, 최소 공배수를 기점으로 나머지가 0이 되기 때문에 x: y 또한 m: n이 될 것이므로, 그 이상의 수를 반복시킬 이유는 없어진다. 예를 들어 m:n = 10 : 12 일 경우, 최소 공배수는 60으로 x : y k번째 해 10:12 60 1 : 1 61 10: 12 120 1: 1 121 60을 주기로 계속 반복되는 것을 관찰 할 수 있다. 그렇다면 어떻게 시간 제한을 1초 내로 줄일 수 있을까? 반복문은 굳이 최소 공배수까지 돌 필요가 없다.. 2020. 11. 10. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음 728x90 반응형
