유에스비 어딨니?

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) 생각 숫자 N을 주어준 후 1부터 N까지 숫자를 쭉 이었을 경우 그 숫자의 자리수를 구하라.1) 첫번째 생각시간이 1초로 주어졌고 N의 범위가 1부터 1억 까지이므로 될까? 싶어서 반복문을 통해 1부터 N까지 돌리면서 그 숫자의 길이를 구해 계속 더해주었다. 약간 느리고 메모리를 많이 잡아먹었지만 '맞았습니다'가 표시되었다. 아마 위의 방법으로는 숫자가 좀 더 크게 주어지면 '틀렸습니다'가 표시될 것이므로 다른 방법을 생각해보았다.2) 방안더 좋은 방법이 무엇일까? 처음 N이 100으로 주어지면 1~99 까지는 무조건 포함이 된다. 여기에 다음과 같은 규칙이 들어간다.1~9는 9개10~99는 90개100~999는 900개... 뒤에는 계산해 보지 않았지만 계속 저렇게 늘어날 것이 분명하다. 자연에는..

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) 생각 무슨말일까 했는데 아래와 같은 블록의 형태를 의미한다. 다른 블록의 형태의 경우에는 탐색을 통해 만들 수 있지만 'ㅜ' 형태의 모양은 만들기 어렵다.딱, 저형태만 되는것은 아니고 저 도형이 회전한 모양이면 어느 모양이던 가능하다.처음 Stack으로 DFS를 구현해보고 재귀를 통해서도 구현해 본결과 Stack으로 구현할 경우 '맞았습니다'는 뜨지만 반복작업이 많아지므로 메모리와 실행시간이 다음과 같이 차이가 나게된다.그리고 이 문제처럼 입력이 띄엄띄엄 많이 주어진 경우 Scanner와 BufferedReader의 능력 차이를 쉽게 알아볼 수 있으므로 같은 코드에서 문자열 입력을 다르게 했을 때 생기는 차이는 다음과 같다.(Scanner는 1024chars의 버퍼 사이즈를 BufferedReade..