알고리즘2 토너먼트 방식으로 2번째로 작은 수 찾기 문제 임의의 숫자들을 토너먼트 방식으로 비교하여 제일 작은 수를 가려냈을 때, 여기서 2번째로 작은 수를 찾는다. 설명 처음에는 모든 수를 작은 순으로 정렬한 것과 헷갈렸는데, 토너먼트는 정렬과 완전히 다르다. 한 라운드에서 묶여서 비교되는 2개의 수 중 작은 수가 다음 라운드로 올라가는 방식이기 때문에 비교 쌍들끼리는 서로 연관성이 없다. 비교되기 위해 묶이는 두 개의 수만이 부분적으로 정렬되는 것이다. 따라서 모든 수를 고려할 필요없이 2번째로 작은 수와 비교된 수들만을 고려하면 된다. 2번째로 작은 수는 반드시 최솟값과 비교됐을 것이며, 따라서 최솟값과 비교된 수들 중 최솟값이 찾는 답이 된다. 따라서 이 후보들을 배열에 저장하여 이 배열 속 최솟값을 찾으면 된다. 코드 class second{ i.. 2020. 1. 8. BAEKJOON(백준) 1463번 C++17 풀이 문제 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 설명 Dynamic Programming 문제이다. Dynamic Programming이란 Divide&Conquer 방식과 많이 비교되는 알고리즘이다. 둘 다 큰 문제를 작은 문제로 쪼개서 접근한다. 작은 문제의 답을 통해 큰 문제의 답을 도출해낸다. 그래서 함수의 재귀호출이 주로 사용된다. 단, Dynamic Programmin.. 2020. 1. 7. 이전 1 다음
