Algorithm65 [백준] 14247번 나무 자르기 자바 문제 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 문제 풀이 처음엔 그날 그날의 나무 중에서 가장 큰 걸 자르도록 구현했는데, 이렇게 하면 주어진 테스트 케이스도 맞추지 못한다. 나무1 나무2 나무3 나무4 나무5 1일째 1 3 2 4 6 2일째 3 10 5 8 1 3일째 5 7 8 12 2 4일째 7 14 11 4 3 5일째 9 7 14 8 4 => 6 + 10 + 12 + 14 + 14 = 56 이므로 최대치가 아니게 된다. 최대치를 구하기 위해서는 성장 속도가 제일 느린 것부터 더해주어야 한다. 왜냐하.. 2022. 6. 17. [백준] 1519번 부분 문자열 뽑기 게임 자바 문제 1519번: 부분 문자열 뽑기 게임 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 dp배열을 이용하여 해당 게임 판에 써져 있는 N에서 진 부분 문자열을 빼서 만들 수 있는 모든 수의 승패여부를 확인한다. dp[x] = 숫자 x에 대해서 패배하는지 승리하는지의 여부 저장 (0:아직 모름/ 패배:-1/ 승리: 승리하기 위한 최소 부분문자열) dp[N+1]로 잡아서 숫자1부터 N까지 담을 수 있도록 한다. 그리고 N이 일의 자리인 경우 부분 문자열을 고를 수 없으므로 무조건 게임에서 지게된다. 따라서 우선 dp[1] ~ dp[9]까지는 -1을 담아 두고, N값에서 부분 문자열을 뺀 값부터 dp적용을 한다. 예를 들어 dp[10]은 .. 2022. 6. 13. [백준] 2075번 N번째 큰 수 자바 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 처음에는 배열의 맨 아래 행만 정렬시킨 후 ArrayList에 담아, 두 개의 포인터를 이용해서 꺼내면서 이동시켜가면서 N번째 수를 구하려고 했는데 우선순위 큐를 이용하면 훨씬 빠르고 간단하게 풀이가 가능하다. ✔️ Priority Queue (우선순위 큐) 일반적인 FIFO인 큐의 구조를 그대로 가지는데, 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 먼저 결정한 후 우선순위가 높은 데이터부터 나가는 자료구조이다. N번째 큰 수를 구해야 하므.. 2022. 6. 11. [백준] 4195번 친구 네트워크 자바 문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 풀이 HashMap을 이용하여 친구의 이름을 숫자로 표현해야 배열 인덱스를 이용할 수 있다. 그리고 union-find함수를 이용하여 두 친구 관계의 집합 크기를 늘려간다. 이때 연결 노드를 저장할 부모 배열외에 몇개가 연결되어있는지 누적하기 위해 count 정수형 배열을 하나 더 사용해준다. count배열에는 처음에 모두 1로 초기화해주고 해당 원소가 다른 원소로 합쳐질 때(부모값이 변경될 때) count값을 해당 원소의 최상위 부모 co.. 2022. 6. 8. [백준] 5397번 키로거 자바 문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 풀이 처음에 ArrayList와 idx변수 하나를 이용해서 list의 인덱스 번호를 옮겨가면서 값을 삽입하는 방법으로 진행을 했는데 시간초과가 떴다. 그래서 구글링해본 결과, Stack을 이용하는 방법과 ListIterator를 이용하는 방법 두 가지가 있었다. 두 가지 모두 풀이에 적용해 보았다. 먼저 ListIterator를 이용하는 방법은 기존 ArrayList에서 index를 바꿔나가는 방법과 로직을 동일하게 사용하고 사용 자료구조와 함.. 2022. 5. 31. [백준] 14501번 퇴사 자바 문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 dp문제인건 바로 알았는데 dp를 너무 못해서 구글링하고서도 이해하는데 꽤 많은 시간이 걸렸다.. 우선 dp의 크기를 N+2 로 두었다. 왜냐하면 마지막 날(N일)까지 일한건 퇴사일(N+1일)에 돈을 받을 수 있으니까 N+1일까지 누적 수익값을 구하기 위해서다. dp[i]는 i일까지의 최대 이익을 저장해둔 것이다. 1일부터 N일까지 반복하면서 해당 날짜로부터 상담을 시작해 상담이 끝난 다음 날의 dp에 해당 수익을 저장한다. 이때 해당 dp에 이미 들어있는 값과 현재 dp[i]의 값 + 현재 날짜에 상담을 함으로써 얻을 수 있는 이익과 비교한다. dp[ i + T[i] ] = Math.. 2022. 5. 28. 이전 1 2 3 4 5 6 7 ··· 11 다음