1) 생각 도시들과 그 도시들간 이동할 때 발생하는 비용이 주어졌을 때, 외판원이 한 곳에서 출발해서 모든 도시를 돌고 다시 돌아왔을 때 최소의 비용을 구하라는 문제로 그리디적으로 접근 할 수도 있겠지만 항상 정답을 보장하는 것이 아니고 10개의 도시가 최대이므로 완전 탐색을 이용해서 답을 구해보았다. 2) 방안 한 번 방문한 도시는 출발할 때의 도시를 제외하고는 다시 방문해서는 안되므로 방문을 체크하는 배열을 만들고, DFS로 도시들을 방문하면서 방문한 도시를 방문체크 한 뒤 탐색을 진행한다.이 때, Count 변수인 cnt의 체크와 함께 처음 시작한 곳으로 다시 돌아와주었는지도 체크함으로써 모든 곳을 방문하였는가가 아닌 순회를 하였는가를 체크해주었다.이동하는 비용이 정해지면 이동중에 비용이 작아지는 ..
1) 생각 첫 번째 생각시작이 '0'이 될 수 없으므로 시작은 무조건 '1'로 한다. 그 이후에 가장 마지막 값을 확인해서 0일 때만 0과 1 둘을 붙여서 계속 탐색하고 마지막 값이 '1'일 경우에는 0만 붙여서 탐색하였다.'시간초과'의 결과가 나왔다. 두 번째 생각간단한 문제이므로 알고리즘에는 잘못이 없다 생각하였고 몇 가지 Case를 적어보자 n = n-1 + n-2라는 피보나치의 점화식이 보여 DP를 적용하여 풀었다. 2) 방안 기존의 재귀를 이용한 완전 탐색을 DP를 적용하여 반복문을 이용하여 풀었다.N의 값이 커질경우 int형 범위를 넘어가 Overflow가 발생하므로 long 타입으로 해결하였다. 12345678910111213141516171819202122232425import java.i..
1) 생각 문자가 주어지면 각 문자들을 숫자로 바꾸어서 가장 큰 숫자를 만들어야한다. 분류에는 백트래킹으로 되어있는걸로 봐서는 바꿔가면서 해보라는 뜻이겠지만 다른 방법을 사용하여 간단히는 아니지만(오류가 있었다..) 간단히 풀었다.예제를 살펴보면 다음과 같다. 입력 출력 2 1998 AAA AAA 가장 큰 수를 만드려면 가장 큰 자리수를 큰 숫자로 만들어야한다. 따라서 위의 예제의 경우 A가 9가 되어야한다. 하지만 다음과 같다면 어떨까 입력 출력 2 1878 BCA AAA B와 A중에 A가 9의 값을 가져야 더 큰값이 된다는 것을 알 수 있지만 자리수로만 따져 B가 9 가되면 가장 큰 숫자가 되지 못한다. 따라서 가중치를 모아서 가장 큰 가중치를 가진 문자가 9부터 차례대로 값을 가져야한다.2번째의 경..
- Total
- Today
- Yesterday