유에스비 어딨니?

1) 생각 제목의 부제가 S/W 문제해결 기본 1일차이다. 이름에 알맞게 시간초는 20초 제한을 주고있으며, TestCase도 모두 공개하고 있다.현재 빌딩에서 조망권이 방해 받을 수 있는 빌딩은 왼쪽으로 2개 오른쪽으로 2개이다. 맨 왼쪽과 맨 오른쪽 2칸은 빌딩이 없다.따라서 빌딩의 개수 N개에서 4개를 더하여도 되지만 헷갈리니 넉넉히 5개를 더하고 탐색은 Index 2부터 N까지 진행하였다. 2) 방안 현재 빌딩에서 좌로 두개 우로 두개와 크기를 비교하여 만약 현재 빌딩이 크다면(하나라도 현재 빌딩이 작다면 조망권이 좋지 않으므로 다음 빌딩을 탐색한다) 그 차이값을 더하면서 진행하였다.빌딩 크기의 입력이 한 줄로 들어오고 공백으로 구분지어 지고있다. N의 크기가 최대 1000 이므로 Scanner ..

1) 생각 체스판에 N개의 Queen을 겹치지 않는 범위로 놓을 수 있는가에 관한 문제이다.백 트래킹이라하는 알고리즘의 대표적인 문제로 볼 수 있다. 모든 경우의 수를 따져보면서 중간에 아니다 싶으면 백 해서 다시 맞나 살펴보는 형태의 알고리즘이다. 따라서 해당 경로를 방문 표시 할 수 있는 배열을 만들어 주었다.NxN 크기의 배열을 만들어서 진행을 하였는데 다른 풀이들을 보니 1차 배열로도 문제를 풀 수 있는것 같다. 이경우는 좀 더 빠르게 문제를 해결할 수 있을 것이다. 2) 방안 백트래킹을 하며 Queen을 한 줄에 하나씩 놔보면서 진행한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import ..

1) 생각기간 N이 주어지고 N일동안 날마다 할 상담의 보수와 상담에 걸리는 시간이 주어질 때, 최대 보수를 구하는 문제이다.이전에 SW Expert Academy에서 풀었던 [SW Expert] 5215번 햄버거 다이어트 문제와 유사하다.다른 점이 있다면 시간을 신경써줘야 한다는 점이다.2) 방안 해당 날짜에 상담을 시작하면 주어진 시간 만큼 상담을 하지 못하므로 Index 번호를 해당 날짜에 주어진 상담 기간 만큼 늘려주어 해결하였다. 123456789101112131415161718192021222324252627282930313233import java.io.IOException;import java.util.Scanner; public class Main{ static int n; static ..

1) 생각 숫자 n이 주어지면 1, 2, 3을 더해가면서 n이 만들어 질 수 있는 개수를 구하여라. 처음 생각문제 분류를 보면 다이나믹 프로그래밍으로 되어있으나 n의 범위가 11보다 작으므로 완전 탐색을 이용해서 풀었다. 2) 방안 더하고 있는 값이 n보다 커질 경우 탐색에 의미가 없으므로 return 해주었다. 12345678910111213141516171819202122232425262728293031import java.io.IOException;import java.util.Scanner; public class Main{ static int n; public static void main(String[] args) throws IOException { Scanner sc = new Scanne..

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