풀이 이분 탐색을 통해 문제를 해결하면 주어진 시간 안에 문제를 해결하는 알고리즘을 구현할 수 있다.먼저 주어진 나무들의 길이를 배열에 저장하고 Arrays.sort를 통해 빠르게 길이순으로 정렬한다.이분탐색의 탐색범위는 0부터 길이가 가장 긴 나무의 길이까지이며(left = 0, right = arr[arr.length-])mid 는 0부터 시작해 반복문의 매번 마지막에는 (left+right)/2 로 재설정해준다.각각의 반복문이 돌아갈 때마다또 다른 반복문을 통해 mid의 길이에 따른 잘린 나무들의 길이의 합을 구해준다.이 길이가 m과 같으면 mid의 값을 출력하고, 아닌 경우 각각 mid의 값을 갱신하여 반복문을 돌게 한다. 하지만 한 가지 주의해야 할 점이 있는데문제의 조건을 잘 살펴보면, 높이가..

풀이 맨 처음에는 Dynamic Programming 방법으로 문제를 풀려고 시도했으나, 문제를 읽고 예제 몇개를 그림으로 그려가면서 시도를 해보니 DFS로 문제를 푸는 편이 더 간편할 것 같다는 생각이 들었다. DFS로 문제를 푸는 방법은 비교적 간단하다.큰 틀에서 보면 이중 For 문을 돌리는 것인데, 제시된 문제 예제를 기준으로 설명해보자면,1일부터 7일까지 반복문을 돌리면서 각각의 날짜를 시작으로 하는 경로를 찾는다.그리고 각각의 날짜에서 상담을 수행한 후에, 도달하게 되는 날짜를 다시 DFS에 집어넣어 반복한다. 예를 들어 1로 시작했다면, 1로 시작할 수 있는 경로는1 -> 4 ....1 -> 5 ....1 -> 6 ....등이 될 것이다. 이 모든 경로를 탐색하면서 경로에 놓여있는 Pi값을 ..

풀이 가장 긴 증가하는 부분 수열을 구하는 문제는 다이나믹 프로그래밍을 이용하여 해결해야 한다.arr 배열에는 입력받은 input data의 값, 즉 수열의 값들을 저장하고dp 배열에는 그 숫자보다 작은 증가하는 부분 수열의 최대 길이를 저장한다. 예를들어 n = 9 인 데이터가 다음과 같이 들어온다고 가정하자. 10, 15, 40, 20, 15, 50, 35, 80, 100 이 상황에서 arr[0] ~ arr[8]까지의 값은 각각 위의 값을 순서대로 저장할 것이다.그리고 이중 포문을 돌면서 (데이터의 개수가 더 클 때에는 O(NlogN)의 시간복잡도를 갖는 알고리즘을 사용해도 된다.)각각의 인덱스에서 그 인덱스보다 작은 최장 부분 수열의 길이+1 의 값을 dp 배열의 값으로 저장하는 것이다. 10의 d..

풀이 BFS를 이용하여 풀어야 하는 문제였다. 먼저 창고에 있는 토마토들을 쭉 스캔해서 큐에 넣는다.큐는 FIFO(First - In - First - Out)의 성질을 가지는 자료구조이기 때문에큐에 먼저 넣은 토마토들의 상하좌우의 좌표를 먼저 탐색할 수 있다. 창고에 있는 토마토들을 쭉 스캔해서 넣은 다음에는 !q.isEmpty()를 조건으로 while문을 이용한다.큐에서 빼낸 좌표의 상하좌우의 좌표가 유효한지를 먼저 확인하고, (isValid) 그 좌표에 익지않은 토마토가 있다면 토마토를 익게 만들고,원래의 토마토의 날짜에 1을 더해 익은 토마토의 좌표와 함께 큐에 다시 넣어주고 BFS를 반복한다. 즉, 큐에 들어가는 객체는 창고의 x좌표, y좌표, 그리고 경과일수가 들어가며, 맨 처음 스캔할때의 경..

풀이 문제 자체는 다익스트라 알고리즘을 이용해서 한 노드에서 다른 모든 노드들에 이르는최단 경로를 출력하면 되는 간단한 문제였다. 우선순위 큐 (Priority Queue)를 이용해서 다익스트라 알고리즘을 구현했고, 우선순위 큐를 이용하기 위해서 목적지 노드의 인덱스와 시작점으로부터의 거리를 저장하는 Element라는 원소 클래스를 정의하였다. *우선순위큐를 이용한 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)정도이다. 문제는 간단했으나, 문제에 걸린 제약조건이 보기보다 꽤나 까다로웠다. 맨 처음에는 인접행렬과 Scanner를 통해 알고리즘을 수행했으나메모리초과와 시간초과가 동시에 발생하였다. 메모리 초과 이유는 인접행렬을 사용했기 때문인데,예를 들어 2만개의 노드가 존재한다면, Integer형을 ..

풀이 플로이드 와샬 알고리즘을 응용해야 하는 쉽지만은 않은 문제였던것 같다.숫자에 의미를 부여하여 그래프를 구성해야 하고, 이 의미를 부여하여 그래프를 완성하는 과정 자체가생각해내기 쉽지는 않았다. 문제 해결을 위한 생각의 과정은 다음과 같다.예를 들어 1 2 0 이라는 input이 주어지면 1에서 2로 가는 경로를 dis[1][2] 배열에 생성한다. 즉, 0이라는 값을 배열에 넣어준다는 것이다. 그리고 여기서 중요한 것이 2에서 1로 가는 경로가 없지만, 1에서 2로 가는 경로가 있기 때문에양방향의 경로가 연결될 가능성이 있으므로, 1이라는 값을 dis[2][1]에 넣어준다. 다시말해서, 이미 단방향이든, 양방향이든 경로가 있으면 거기에는 도로를 추가할 일이 없으므로 0을 넣어주고단방향의 경로가 없지만..