본문 바로가기
728x90
반응형

전체 글77

[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.
[algorithm] 백준 - 외판원 순회 2 이 문제는 brute force문제이다. 한 도시를 출발하여 n개의 도시를 다 거치고 원래 도시로 돌아오는 방법 중 최소 비용을 출력하는 문제이다. 시작점과 동일한 도시이고 n개의 도시를 순회했을 경우 최소비용을 구하도록 했다. if(start == y && target == n){ if(sum < minSum){ minSum = sum; } return; } 그리고 y에서 시작했을 때 도시를 순회하기 위한 비용이 최소 비용을 넘지 않을 경우 계속해서 순회를 하도록 했다. for(int i = 0; i < n; i++){ if(visited[y] == 1 || path[y][i] == 0) continue; if(sum < minSum){ visited[y] = 1; dfs(start, target + .. 2020. 11. 6.
[algorithm] 백준 - 숨바꼭질 4 이 문제는 bfs로 숨바꼭질과 비슷한 문제이다. 다른 점은 수빈이가 동생을 찾기위해 이동 경로를 출력해야한다는 것이다. 따라서 이동하고자 하는 위치를 인덱스로 하고, 현재 위치를 값으로 하는 배열을 추가하여 이문제를 해결했다. 조심해야할 부분은 수빈이의 위치인 n과 동생의 위치인 k가 같을 때 예외처리를 해주어야한다는 것이다. 예외처리를 하지 않을 경우 trace값이 k가 나올 때까지 무한루프를 돌면서 값들이 stack을 가득채워서 메모리 초과를 야기한다. //숨바꼭질 4 #include #include #include using namespace std; int weight[100001] = {0,}; int visited[100001] = {0,}; int trace[100001] = {0,}; vo.. 2020. 11. 5.
[algorithm] 백준 - 숨바꼭질 6 이 문제는 유클리드 호제법으로 푸는 문제이다. 모든 동생을 찾기 위한 D의 값을 정하기 위해 최대 공약수를 구하는 문제이다. 동생의 위치에서 수빈이의 위치를 빼고 절댓값을 씌운 후 그 값들을 유클리드 함수에 집어 넣어 최대 공약수를 구한다. //숨바꼭질 6 #include #include using namespace std; int uclid(int a, int b){ while(a % b != 0){ int temp = b; b = a % b; a = temp; } return b; } int main(void){ int n, s, num, gcd; vector sisterVector; cin >> n >> s; for(int i = 0; i > num; sisterVect.. 2020. 11. 4.
728x90
반응형

티스토리툴바