728x90 반응형 알고리즘5 [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. [algorithm] 백준 - 조합 0의 개수 우선 곱셈으로 0을 어떻게 만들 수 있을까? 2와 5가 곱해졌을 때 10으로 0의 개수가 1이다. 4와 25가 곱해졌을 때 100으로 0의 개수가 2이다. 즉 2와 5는 0을 만드는 구성원이라는 것을 알 수 있다. 그렇다면 2가 1개 5가 1개일 때 0 1개를 만들 수 있다. 2가 2개 3개더라도 5는 1개이면 0은 언제나 1개이다. 즉 2와 5의 개수 중 가장 작은 수가 0의 개수이다. 조합은 라는 식을 갖는다. 그렇다면 n!에서의 2의 개수 - k! 에서의 2의 개수 - (n-k)! 에서의 2의 개수와 n!에서의 5의 개수 - k! 에서의 5의 개수 - (n-k)! 에서의 5의 개수 중 가장 작은 수는 0의 개수라는 것을 알 수 있다. cout 2020. 11. 4. [algorithm] 백준 - 리모컨 brute force 문제이다. 가능한 모든 리모컨 채널을 돌리면서 최소 몇번 눌러지는 지를 체크하면 된다. 1. 모든 가능성을 열어두기 위해 중복순열로 자릿수는 0부터 6까지 모든 경우를 구했다. 만약 테스트 케이스가 10 2 1 0 이런 경우 자릿수가 1인 9로 이동하는 채널 수가 적기 때문이다. 따라서 모든 자릿수에 대한 채널을 구해야한다. 그리고 이동하려하는 리모컨 채널 - 만들어진 리모컨 + 리모컨을 누른 값 중 가장 작은 값을 구한다. 2. 현재 채널인 100에서 이동하고자 하는 리모컨 채널을 뺀 값과 위에서 구한 값을 비교해서 가장 작은 값을 출력한다. 코드는 이렇다. #include #include #include using namespace std; unsigned long answer .. 2020. 11. 4. 이전 1 2 다음 728x90 반응형
