유에스비 어딨니?

1) 생각 항상 짝수로 주어지는 N명의 사람이 2개의 팀으로 나뉘어 경기를 할 때 팀이 되는 사람들은 서로에게 시너지 효과를 불어넣어 능력치를 향상시킨다. 이때 양팀의 능력치가 최소값이 되도록 팀을 꾸려라.처음 생각처음에는 탐색에서 left 팀과 right 팀을 각각 더해가면서 left의 개수와 right의 개수가 둘 다 n/2개가 되면 두 값을 - 시켜서 그 값의 최소값을 구하는 방향으로 시도하였다. => 탐색을 할 때마다 2개의 반복문을 돌면서 계속적으로 더하였기에 값을 구하기가 쉽지 않았다. 다음 생각두 팀의 숫자가 n/2로 같으므로 한 팀이 꾸려지면 다른 팀은 자연스럽게 꾸려질 수 있다. 따라서 한 쪽 팀만 체크를 하면서 탐색을 하고 n/2 가 되면 미리 구해둔 배열의 합 값에서 해당 값을 빼주었..

1) 생각 N개의 숫자와 N-1개의 연산자가 주어집니다. 조건은 다음과 같습니다.1) 연산자의 종류에 상관없이 앞에서부터 계산을 합니다.2) 숫자는 바뀌지 않고 읽어들인 순서대로 쭉 갑니다.이 때, 연산자를 이리저리 넣어봤을 때 최소값과 최대값을 출력하시오.연산결과의 범위가 -10억 ~ 10억 이므로 int형 변수를 선언하여도 풀이가 가능합니다. 연산자를 숫자사이에 이리저리 넣어봤을 때 최소값과 최대값을 출력해야하므로 어떤게 최소값과 최대값이 될지 모릅니다.주어진 시간초가 2초이고 N의 개수의 최대값이 11 이므로 모든 조건을 따져보아도 시간내 탐색이 가능합니다.2) 방안 DFS를 통해 + - * / 의 경우를 해당 숫자 카운트를 하면서 하나씩 들어가서 모두 탐색해주었습니다. 탐색을 처음 시작할 경우 맨..

1) 생각 오름차순으로 숫자 배열이 주어지면 오름차순으로 6가지 숫자를 조합할 수 있는 경우를 만들어라. 우선 입력으로 주어지는 k의 값이 7~12 이므로 완전탐색을 통해 충분히 문제를 해결할 수 있으며, 반복문으로 나타내려면 어렵지만 재귀로 구현하면 쉽게 구현 할 수 있는 문제다. 오름차순으로 출력을 해야한다는 조건이 있지만 이미 오름차순으로 입력이 주어지기때문에 재귀를 통해 DFS 탐색을하면 자동으로 순서대로 출력이된다. 2) 방안 재귀를 통해 탐색을 하면서 자신을 포함할 때와 그렇지 않을 때를 넘겨준다. 끝낼 조건을 위해 Count 변수인 cnt가 6이 되었을 때, 그리고 계속 나아가는것을 막기위해 인덱스를 나타내는 idx 값이 주어진 수 k와 같아질 경우 return을 하도록 하였다.처음에 sol..

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번째의 경..

1) 생각 주어진 부등호 조건을 만족하는 제일 작은 수와 제일 큰 수를 구해야한다. 특징으로 0도 포함된다. 모든 수를 한 번씩만 쓸 수 있으므로 방문 조건을 추가해서 각 수마다 0~9까지 비교해서 판단하였다. 0부터 쭉 비교해서 나아가면 자연스럽게 List에 추가되어있는 수중 Index 0에 저장된 수가 작은 수 마지막에 저장된 수가 가장 큰 수가 된다. 조건 문을 통해 를 판단하고 if문을 통해 이전 숫자와 현 숫자를 비교하였는데 자꾸 오류가나서 살펴보니 한 줄이라 조건문에 { } 를 사용하지 않고 작성하였더니 이클립스가 맨 위의 if문과 짝지어져어할 else if문을 문단에 상관없이 계속 바로 위의 if문과 짝지어줘서 그런것이였다. 2) 방안 조건문에 { }를 추가하여 구분하여줬다. 0~..

1) 생각 문제는 아주 심플하다 1) 첫번째 생각M,N 값에 대응하는 값을 1부터 쭉 올리면서 M,N에 도달하면 없는것으로 판단하여 -1을 출력하였다.위의 시도는 바로 '시간초과'를 받았고 다른 생각을 해보아야했다. 2) 두번째 생각M값을 고정시키고 N을 +M만큼 해준 후 차이를 N 범위를 넘어서게되면 -N을 해주어 처리를 하였다.처음 M 값을 고정했을 때의 N에 대응하는 값을 가지고 새롭게 변한 tN 값과 비교를 해주면서 tN값이 다시 처음의 N 값으로 돌아왔다면 한 바퀴를 돌았다는 것이므로 대응하는 숫자가 없다고 판단하고 '-1'을 출력하였다.=> 이경우 -N으로 처리하였는데 '틀렸습니다'가 아닌 '시간초과'를 받았기에 잘못된 부분을 발견하는데 조금 걸렸다.M이 클경우 tN값에 +M을 해주어 N이 넘..

1) 생각 큰 고민없이 리모콘 숫자만 맞추는 식으로 코드를 작성한 후 '틀렸습니다'를 맛보고 고민을 해서 코드를 작성하였다. 2) 방안 최대 999999 개만 살펴보면 되므로 모든 Case를 살펴보았고, 각각의 숫자를 검사하여 고장난 버튼의 숫자가 있으면 건너뛰고 그렇지 않으면 N값 과의 차이와 그 숫자를 min으로 저장해 둔 후 min의 최소값이 되는시점(N값과의 차이가 가장 작은시점 -> 0부터 검사하므로 점점 작아지다 최저 값을 찍은 뒤 점점 커짐) 에서 반복문을 빠져나왔다.이후 한 번 더 틀린것을 확인하고 101 같은경우 위의 반복문만 확인하면 4가 나오겠지만 기본 채널이 100번이므로 +1만 해주면되는것을 발견하고 100과 N의 차와 위에서 구한 최소값을 비교하여 최소값을 출력하였다. 12345..

1) 생각 우선 이동해야하는것이 2가지이다. 하나는 고슴도치(S)이고 다른 하나는 물(*)이다. 비버(D)와 돌(X)은 움직이지 않으므로 if 문 처리만 잘 해주고 신경쓰지 않는다.침수 예정 지역으로 고슴도치가 이동해서는 안되므로 맨 처음에 물을 먼저 퍼트리는것이 편하다 생각하였다. 2) 방안 물을 맨 처음 퍼트리면 이것은 예상 경로를 미리 놓은 것이기 때문에 물이 한 턴 앞서나가게된다. 따라서 반복문에 들어가기전 한 번 수행후 물의 퍼트림을 1번 쉬어줌으로서 맨 처음 예상 침수 경로만 만들어 놓고 진행하였다. 물의 경우 마지막 퍼트린 지점만 알고있으면 되고, 또 물이 처음에 여러개 등장할 수 있으므로 list로 만들어준후 이전 좌표를 List에서 제거하면서 생성하였다.고슴도치와 물의 이동경로 좌표를 위..