문제https://www.acmicpc.net/problem/2805 풀이해당 문제는 높이의 최댓값을 구하는 문제로 매개변수 탐색을 통해 해결했습니다.매개변수 탐색으로 해결한 이유는 최댓값을 구하는 최적화 문제이며 이를 결정 문제로 해결하게되면 답을 도출하는 것이 수월하다고 생각했기 때문입니다. 방법은 다음과 같습니다.1. 수열을 입력받으며 배열에 저장하고, 그 값들 중 최댓값을 저장합니다.2. 매개변수 탐색을 하면서 문제에서 원하는 최댓값을 찾습니다.s = 0, e = 입력값들 중 최댓값, while(e > s)mid 값을 구해줍니다.(이때의 mid 값은 높이 입니다.)mid(높이) 값을 기준으로 들고 갈 나무를 셉니다.(N과 높이의 값이 크기 때문에 long 타입으로 리턴해줍니다.)c에서 구한 값 ≥..
문제https://www.acmicpc.net/problem/2412 풀이시작 위치에서 종료 위치까지 도달하기 위해 그래프 탐색을 이용해서 문제를 해결했습니다.해당 문제는 2차원 배열에 위치를 마킹하거나 방문처리를 하게되면 메모리 초과가 발생합니다.따라서 그래프 탐색을 위해 입력받은 값을 y(열)를 기준으로 list 배열에 x(행)값을 저장해두었고현재 행에서 갈 수 있는 열에 대해서, 다음으로 갈 수 있는 유효한 좌표를 탐색했습니다.최단거리를 구해주는 문제이기 때문에T열에 가장 먼저 도달했을 때의 cnt 값을 리턴해주었습니다.(도달하지 못했다면 -1 리턴) 코드import java.io.*;import java.util.*;public class Main { static int N, T; st..
문제https://www.acmicpc.net/problem/1920 풀이특정 값을 찾는 문제로 시간 복잡도를 고려하여 이분탐색 알고리즘을 활용해 문제를 해결했습니다. 입력 받은 수열을 배열에 넣고 정렬했습니다.타겟 값을 찾기 위해 이분탐색을 진행했습니다.s = 0, e = N-1로 두었습니다.while 조건은 e ≥ s로 두었습니다.(e == s 때 리턴해주기 위해)mid 값이 타겟값 보다 클 경우, (더 커질 필요가 없기 때문에) mid ~ e 까지의 후보군을 제외했습니다.이때 e = mid-1로 e값을 변경했습니다.e = mid로 설정하면 s와 e가 같아지는 상황에서 무한루프에 걸리게 되면서 시간 초과가 발생합니다.mid 값이 타겟값 보다 작을 경우, (더 작아질 필요가 없기 때문에) s ~ mid..
문제https://www.acmicpc.net/problem/1516 풀이선행 조건을 해결해야하는 문제 특성상 위상정렬을 이용해서 문제를 해결했습니다.입력을 받으면서, 정보를 저장했으며(진입차수, 건물 건설시간, 선행 건설 건물정보)진입차수가 0인 건물을 큐에 넣고 그래프 탐색을 진행했습니다. 이때, 건물이 동시에 지어질 수 있기 때문에건물 중 가장 오래걸리는 시간을 찾아서 ans 정답 배열에 저장해주었고진입차수를 1 감소시킨 값이 0이라면 큐에 넣어주었습니다. 그래프 탐색을 마친 후건물을 순회하면서 도출된 정답 배열 값 + 현재 건물을 건설하는 데 걸리는 시간을 더해주어 출력했습니다. 코드import java.io.*;import java.util.*;public class Main { stati..
문제https://www.acmicpc.net/problem/16900 풀이KMP 알고리즘을 사용하는 문제입니다.가장 짧은 문자열을 구하기 위해서는 두개를 최대한 많이 겹쳐내야 합니다. 이를 실패 배열을 통해 찾아냈습니다.실패 배열의 값은 접두사와 접미사가 같아지는 최대 길이를 의미합니다.예를들어, ada에서 0번째 인덱스와 2번째 인덱스는 접두사와 접미시가 일치하는 부분이며이러한 일치하는 길이는 1입니다.table[N-1]는 문자열 마지막 인덱스 위치까지, 사이에 겹쳐지는 길이의 최댓값을 의미합니다.이를 바탕으로, N + (K - 1L) * (N - table[N-1])를 구해줍니다.원본 문자열 길이 + (몇 번 반복 - 1) * (원본 문자열 길이 - 접두사와 접미시가 최대로 겹쳐지는 수)(몇 번 ..
문제https://www.acmicpc.net/problem/16570 풀이KMP 알고리즘을 사용하는 문제입니다.입력 값을 역순으로 arr 배열에 담고 이를 바탕으로 테이블을 형성해줍니다.(sb.reverse().toString()으로 넘겨주고, s.charAt(i)를 이용해서 풀면 예제만 맞고 3%에서 틀림..) 형성한 테이블의 인자 값들은 i번째 인덱스까지의 연속 부분수열의 길이의 최댓값을 의미합니다.따라서 테이블값을 순회하며1) table[i]가 기존에 저장된 값(length = 0 초기화)보다 클 경우, res를 table[i] 및 cnt = 1(몇 번 반복했는지)로 갱신해줍니다.2) table[i]가 기존에 저장된 값과 같을 경우, table[i] == res라면 cnt를 ++해줍니다. 순회를 ..
문제https://www.acmicpc.net/problem/9120주어진 문자열 T, P에서 T 문자열 내에 P가 몇 번 나타내는지 출력하는 문제입니다. 풀이접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.테스트 케이스 별로 아래의 순서대로 했습니다. 1. 문자열 P(pattern)를 이용해서 테이블을 형성하고2. 만들어진 테이블과 문자열 T와 P를 이용해서 비교를 진행합니다.2-1. 비교과정에서 P문자 == T문자일 때, idx == plen-1 라면(T에 P와 동일한 값이 있다면) 카운트를 증가시킵니다.3. 카운트를 출력해줍니다. 코드import java.io.*;import java.util.*;public class Main { static int N; ..
문제https://www.acmicpc.net/problem/11585주어진 문자열 T, P에서 T 문자열 내에 P가 몇 번 나타내는지 출력하는 문제입니다.주어진 문자 T는 원형입니다.'몇 번 나타내는지 / 문자열에서 발생할 수 있는 경우의 수'를 기약분수로 출력합니다. 풀이접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.이때 원형으로 이루어진 T 문자열을 체크하기 위해, T+T 문자열을 바탕으로 P와 비교했습니다. 1. 문자열 P(pattern)를 이용해서 테이블을 형성하고2. 만들어진 테이블과 문자열 T와 P를 이용해서 비교를 진행합니다.3. 비교를 마친 후, 기약 분수로 결과 값을 출력하기 위해 GCD를 구합니다.4. 값을 출력합니다. 코드import java...
