유에스비 어딨니?

생각2차 배열로 주어진 등산로에서 가장 긴 등산로를 찾는 문제이다. 등산로는 높은 숫자에서 낮은 숫자로만 이동할 수 있다. 이 때, K 값이 주어지는데 이 K는 한 등산로를 만들 때 한 번만 사용할 수 있는 지형을 파괴할 수 있는 높이이다. 만약 처음 등산로가 9로 시작하면 근처에 있는 9로는 못가게되지만 파괴를 한 번 할 수 있는 기회를 사용해서 K=1 일 경우 다음 9를 8로 만들어서 진행 할 수 있다. 처음 생각우선 List를 이용해서 처음에 등산로의 숫자를 입력받는 부분에서 가장 높은 숫자가 나오면 List에 추가해 주어 등산로의 출발 경로를 설정하였다.▶ Max가 바뀔 경우 List를 초기화 하여 이전 출발 경로들을 없애고 새로 넣어준다. 다음 생각등산로의 출발 점을 하나씩 DFS 탐색하면서 가..

1) 생각 12달 동안의 월별 수영장 이용 일 수와 1일, 1달, 3달, 12달 이용권의 가격이 주어진다. 최소한의 금액으로 수영장을 다닐 수 있겠끔 최소 금액을 출력하여라. 처음 생각DFS를 이용해서 1일 1달과 한달은 idx+1을 3달은 idx+3을 1년은 idx+12를 하여 idx가 12보다 크거나 같아지면 해당 값까지의 sum 값의 최소값을 구하였다. 다음 생각위의 방식으로는 대다수의 case는 통과하였지만 1개가 통과되지 않았다. 3달을 구할 때 무작정 더하면 안됐던 것이다. 세달 연속 이용 일 수가 모든 달이 0 0 0 이면 이용하지 않아도 되기 때문에 해당 조건을 추가해주었다. 마찬가지로 달마다의 금액도 해당 달의 이용일 수가 0보다 클 경우에만 더해주었다. 2) 방안 1) 재귀를 이용한 D..

1) 생각 n개의 숫자와 n-1개의 연산자를 줄 때 만들 수 있는 가장 큰 숫자와 가장 작은 숫자의 차이를 구하여라(연산은 무조건 앞에서 부터 진행한다.) 처음 생각맨 처음 숫자를 필두로 1개식 연사자를 바꿔가며 모든 경우를 만들어 보면 되므로 재귀로 해결하였다. 2) 방안 1) 재귀의 인자를 4개의 연사자를 다 넣을지 배열로 넣을지 고민하다 그냥 다 넣었다.2) 재귀에서 가장 중요한 점은 가지치기 이므로 idx를 벗어나지 않도록 idx의 값이 n까지 다달으면 max와 min을 갱신해주고 return 해주었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.io.IOE..

1) 생각 배틀 필드 게임을 개발하려고 한다. 주어진 조건에 맞게 구현하여라. 처음 생각조건에 맞춰 구현을 하는 시뮬레이션 문제이다. 다음 생각기본 적인 구현을 한 뒤, LEFT RIGHT UP DOWN 방향을 알고 있어야 SHOOT을 그 방향으로 할 수 있으므로 Field 선언을 통해 항상 탱크의 방향을 갱신해주었다. 다다음 생각'Fail'이 떠서 머가 문제인지 찾기 어려웠으나 시뮬레이션은 문제가 답이므로 문제를 더 꼼꼼히 읽어본 결과 SHOOT을 하였을 때, 벽(*)을 만났을 경우 메소드를 종료시키지 않고 있었다. 2) 방안 1) SHOOT을 할 때 방향 변수에 따라서 4개의 조건으로 나뉘고 그 이후를 탐색한다. '#'을 만나면 바로 종료하고 '*'을 만나면 지도 배열을 '.'로 바꿔주고 종료한다. ..

1) 생각 괄호가 올바로 짝지어지면 1 그렇지 않으면 0을 출력하라. 처음 생각한 바퀴를 쭉 돌면서 괄호를 시작하는 경우인 "(,{,[,"일 경우에는 해당 배열을 -1 해주어 마지막에 음의 값을 가지고 있는 배열이 있을 경우는 0을 그렇지 않으면 1을 출력하였다. 다음 생각주어진 문자열에서 하나의 괄호만 잘못 되었어도 0을 출력해야 한다. 따라서 -1을 하기전 해당 배열이 0이라면 바로 반복문을 종료하였다. 2) 방안 1) switch 문을 사용해서 코드가 길어져서 solve() 메소드로 따로 빼내어 처리를 해주었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.IOExc..

1) 생각 [SW Expert] 1226. [S/W 문제해결 기본] 7일차 - 미로1 문제와 99.9999999998% 똑같다. 처음 생각똑같은 미로 찾기다. 이전 문제의 16으로 짜여있는 배열의 크기를 100으로 바꿔주었다. 2) 방안 1) 배열의 크기와 반복문의 범위를 100으로 수정하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import ..

1) 생각 미로가 주어진다 출발점은 2, 도착점은 3으로 표현되어 있을 때, 도착점까지 갈 수 있는지를 판단하여라. 처음 생각미로 탐색이므로 BFS를 통해서 풀이를 하였다. 다음 생각16 x 16으로 크기가 작게 정해져 있으므로 DFS를 이용해 풀어도 빠르게 풀릴 것 같다. 2) 방안 1) BFS를 사용해서 풀이를 하였다.▶x와 y의 좌표를 class를 따로 만들어 사용하지 않고 Queue 2번 넣어줘서 풀이를 해보았다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import java.io.BufferedReader;import java.io.IOExcept..

1) 생각 수열의 개수 N과 숫자 K가 주어진다. 수열에서 수를 합 하였을 때, K가 되는 경우의 수를 구하여라. 처음 생각DFS를 통해 수열에서 그 숫자를 포함하고 가는경우와 포함하고 가지 않는 경우로 나누어 탐색을 진행한다.▶재귀를 통해 구현하여 가지치기를 잘 해주어야 한다. ▶이 문제의 경우 숫자의 합이 k에 도달 했을 때, Index 변수가 N에 도달하였을 때, 마지막으로 숫자의 합이 k를 넘어 섰을 경우 return 해주었다. 2) 방안 1) 재귀를 통해 구현을 하였다.▶반복문의 경우 충분히 큰 숫자까지 돌 수 있지만 재귀의 경우에는 10만 번 정도 이상을 들어가게 되면 스택 오버플로우 에러가 나게된다. 따라서 재귀를 사용한 탐색의 경우 항상 가지치기를 잘해 주어야한다.▶이러한 문제는 재귀를 통..

1) 생각 올림픽 종목을 추가하기 위한 투표를 한다. 올림픽 종목과 투표위원회가 각각 주어진다.올림픽 종목은 재미있는 순서대로 나열되어있고 숫자는 해당 index 올림픽의 개최 비용을 나타낸다.투표위원회의 주어지는 각각의 숫자는 그 개최비용 이하에 투표한다. 이 때, 가장 재미있는 종목에 투표한다. 처음 생각각각을 배열로 저장한 뒤 투표위원회에서 하나를 꺼내어 올림픽 종목과 앞에서 부터 비교를 한다.▶올림픽 종목은 재미순으로 정렬되어 있기 때문에 앞에서부터 비교를 하면서 해당 투표위원회의 비용 이하의 종목이 나오면 결과 배열의 해당 종목의 인덱스를 +1 시켜준 뒤 바로 반복문을 종료한다. 2) 방안 1) 모든 케이스에 대해서 가장 많은 표를 획득한 경기는 1경기만 존재한다.▶ 조건 문을 처리해 줄 때, ..

1) 생각 4 x 4 격자 판이 주어졌을 때, 7개를 탐색했을 경우 나올 수 있는 숫자의 개수를 구하시오(중복 비허용)처음 생각우선 4 x 4이고 시간도 Java의 경우 4초를 주기때문에 충분히 완전탐색으로 해결할 수 있다고 생각하였다.따라서 DFS를 이용하여 탐색을 진행하였다. 다음 생각DFS를 진행하면서 7개의 탐색을 진행하면 방문 배열을 통하여 이미 온곳이면 return하고 방문하지 않았던 곳이면 방문표시를 한 뒤, 개수 변수를 result++ 해준 뒤, return 처리를 하였다. 알고리즘을 다 완성하고 나서 보니 HashSet 자료구조를 쓰는것이 더 좋을 것 같아 수정하였다. 다음 생각HashSet의 제너릭 타입을 String으로 해주었는데 아무래도 객체들을 다루다보니 속도가 느리고 메모리를 많..