Dazzling 개발 노트

[백준] 2805 - 나무 자르기 (Java) 문제 https://www.acmicpc.net/problem/2805 풀이/후기 이코테 책에서 푼 문제와 유사해서 복습 느낌으로 금방 끝날 줄 알았는데, 삽질하는데 시간을 엄청 투자했다,,, - 일단 처음 오답이 나온 부분은 long처리였다. 나무의 합 sum 은 long형태로 사용해야 한다. 이거 외에 별다른 오답 부분이 없는데 왜 자꾸 오답처리가 되는지 한참 고민했다. 결국 찾아낸 부분은 처음 start와 end 설정 부분이었는데, 내가 배열을 정렬한 후 arr[0] 과 arr[N-1]로 지정한 부분이 문제였다. 이렇게 지정하면 배열의 값이 하나인 경우 start와 end가 잘 작동하지 않게 된다. 그리고 내 처음 생각으론 start가 가장 짧은 막대 ..

[백준] 10815 - 숫자 카드(Java) 문제 https://www.acmicpc.net/problem/10815 풀이/후기 수 범위도 정수 범위 내여서 그냥 이진탐색 구현해주면 가볍게 풀 수 있다. 이제 이정도는 가볍게 풀 수 있나보다,,^^; 코드 package BinarySearch; import java.io.*; import java.util.*; public class Problem10815 { static int N, M; static int[] arrN; static int[] arrM; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStream..

[백준] 14501 - 퇴사 (Java) 문제 https://www.acmicpc.net/problem/14501 풀이/후기 5월에 브루트포스 문제 풀다가 만난 문제로 그때 당시 DP 풀이를 보고나서 도망갔던 문제를 다시 풀어보았다. 이제는 DP가 익숙하지만 점화식을 세우는 것은 여전히 어려웠다... 이미 나와있는 점화식을 보고도 이해하는데 한참 걸리니,,^^; 아직도 갈 길이 멀다 싶다 ㅋㅋ 그래도 계속 보다보니 이해가 가긴 한다! 이게 어디야,, dp[t[i] + i] = Math.max(dp[t[i] + i] , dp[i] + p[i]); 그리고 작업을 진행하지 못한 날은 0이 아니라 그 전에 최대값으로 채워줌 dp[i+1] = Math.max(dp[i], dp[i+1]); 코드 import jav..

[백준] 13203 - ABCDE (Java) 문제 https://www.acmicpc.net/problem/13023 풀이/후기 단순 DFS가 아닌 고려해야할 것이 많은 문제 - DFS로 해당 경로 탐색 시 5 이상의 경로가 아니면 방문처리를 다시 false로 수정 필요 : 직접 반례 케이스를 찾아봐야함 - 시간초과 : 구글링으로 고려해야할 부분도 다 고려해줬는데 계속 시간초과가 발생했음 : 모두 배열 형태의 ArrayList를 사용했는데, 난 구조상 이차원배열을 사용해도 될 것 같다고 판단하고 계속 고집함 결국 이차원배열을 ArrayList로 바꾸자마자 정답 처리가 되었다는 후기,,^^; 남들이 안한 이유는 다 있다,, list를 사용해야 시간초과가 나지 않는 이유는 dfs내에서 반복문을 돌 때 N번..

[백준] 2417 - 정수 제곱근 (Java) 문제 https://github.com/allrightDJ0108/CodingTestStudy/commit/26429316cf03dd26ace86644eec2a95eb941a0d7 풀이/후기 BigInteger를 자료형으로 이용해야 한다 long을 이용하여 풀면 틀렸습니다 처리가 된다..ㅎ 0부터 N까지 start, end시점 잡아서 mid보다 큰지 작은지를 따져서 답을 구해주면 된다. 코드 package BinarySearch; import java.io.*; import java.math.*; public class Problem2417 { public static void main(String[] args) throws IOException { Buff..

[백준] 17822 - 원판 돌리기 (Java) 문제 https://www.acmicpc.net/problem/17822 풀이/후기 내가 문제를 풀면서 찾은 포인트, 메모들 - 배열에서 양 끝 값들의 인접 처리 : 어려울 줄 알았는데 그냥 맨 끝과 1 비교하면 됨 - 인접한 항목이 존재하지 않음 판단 : before배열 만들어서 변경 전 후 비교 카운트로 해결함. 어차피 초기화하느라 배열 한 번 더 탐색해야해서 그 반복문 그대로 이용 - 평균 구할 때 double 이용 : 연산에 들어가는 숫자들도 double형태로 해야됨. - 삭제하는 부분 DFS/BFS로 하지 않아도 됨. 유사하게 check[][]를 이용해서 풀었음 - 회전시킬 때 괜히 반복문 한 번씩 아끼려다가 arr[i] = temp 이런 짓 해서..

[백준] 21609 - 상어 중학교 (Java) 문제 https://www.acmicpc.net/problem/21609 풀이/후기 내가 처음 풀었던 풀이는 visited에 블록 그룹 번호를 부여해서 해당 그룹이 가장 크면 그룹 번호를 이용해 삭제하는 로직을 이용했다. 근데 이렇게 하니 무지개 블록 처리가 애매해졌다. list를 이용해서 가장 큰 블록 그룹에서 사용한 무지개 블록을 담아두고 추후에 삭제하는 방향으로 수정도 해보았는데 계속 오답처리가 되더라. 이 방법으로 꼭 완성해보고 싶었는데 결국 방향을 바꿨다. visited는 boolean으로 둔다 매 블록 그룹을 찾기 전에 무지개 블록의 visited는 다시 false로 돌려준다. 이 경우 나중에 블록을 제거할 때의 방법이 고민이었는데 그냥 BFS를..

[백준] 15988 - 1,2,3 더하기 3 (Java) 문제 https://www.acmicpc.net/problem/15988 풀이/후기 이것 또한 9095 문제를 풀었다면 점화식은 동일하게 사용할 수 있다. 근데 몇 번을 제출해도 계속 오답처리가 됨. 포인트는 자료형이었는데, 처음에 인식하고 있었으나 Integer.MAX_VALUE 값을 찍어보니 문제에서 다루는 수가 더 적은 것 같아서 int를 사용해서 틀린 것. (당연하지 연산 결과가 훨씬 크게 나오는데 난 무슨 생각을 한걸까?) 아무튼 자료형을 long으로 바꿔주면 아주 편안해진다 그리고 실행시간이 좀 걸리길래 코드를 좀 수정했는데 dp 반복문은 어차피 N과 별도로 실행되어도 되는 부분이므로 테스트케이스 돌아가는 반복문 밖에서 실행하고 해당 반..