BOJ735 [자바] 백준 11066 - 파일 합치기 (java) 목차 문제 : boj11066 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법), 누적합 분할정복 느낌으로 생각해보면 풀이법을 찾을 수 있다. 그리고 구현을 위해 DP와 누적합을 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선, 이 문제의 경우 연속된 파일끼리만 합칠 수 있다는 점을 주의해야 한다. 만약 아무 파일이나 합칠 수 있었다면 그리디로 매번 합쳐진 파일들 중 가장 가중치가 낮은 2개를 합치.. 2023. 8. 10. [자바] 백준 14938 - 서강그라운드 (java) 목차 문제 : boj14938 필요 알고리즘 플로이드-워셜 (floyd-warshall) 플로이드 워셜을 안다면 쉽게 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 플로이드 워셜은 O(N^3)인 알고리즘이지만, 모든 정점에서 모든 정점으로의 최단거리를 알 수 있어서 아주 강력한 알고리즘이다. 심지어 코드도 엄청나게 간단하고 이해하기도 직관적이라 익히기도 쉽다! 모른다면 이번 기회에 익혀보자. 물론 다익.. 2023. 8. 8. [자바] 백준 1311 - 할 일 정하기 1 (java) 목차 문제 : boj1311 필요 알고리즘 bit DP (비트 필드를 이용한 다이나믹 프로그래밍) 비트 단위 DP로 푼 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 좀 더 간소화시켜서, N이 항상 3이라고 해보자. 이 때 dp[A][B] 를 A번 사람을 B라는 일의 조합으로 진행한 경우 비용의 최솟값이라고 정의하자. 이 경우 B는 3개의 일을 가지고 할 수 있는 모든 경우를 나타낼 수 있으면 된다. 0. .. 2023. 8. 3. [자바] 백준 1956 - 운동 (java) 목차 문제 : boj1956 필요 알고리즘 플로이드-워셜 (floyd-warshall) 다른 그래프 탐색 알고리즘으로 되긴 하겠지만, 이 문제는 플로이드 워셜이 매우 편하긴 하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단방향 그래프에서 '1번 마을에서 1번 마을로 가는 최소 거리, 2번 마을에서 2번 마을로 가는 최소 거리, ... , V번 마을에서 V번 마을로 가는 최소 거리' 중 최소값을 출력하면 되는 문제이다... 2023. 8. 3. [자바] 백준 11812 - K진 트리 (java) 목차 문제 : boj11812 필요 알고리즘 최소 공통 조상 (LCA) LCA 문제이다. 근데 몰라도 푸는데 딱히 지장은 없다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 LCA를 안다면 그걸로 바로 접근 가능하고, 몰라도 딱히 상관은 없다. 어차피 첫 깊이엔 1개, 두번째 깊이엔 K개, 세번째 깊이엔 K^2개, ... 의 노드가 존재할꺼다. 그러므로 x와 y를 입력받을 시, K로 나누다보면 점점 부모 노드의 번호를 알 .. 2023. 8. 3. [자바] 백준 1103 - 게임 (java) 목차 문제 : boj1103 필요 알고리즘 깊이 우선 탐색, DP, 사이클 판정 memoization을 통해 연산 횟수를 줄이면서 DFS를 진행하는 문제이다. 또한 사이클 판정하는 방법도 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 로직을 말로 하면 간단하다. 1. 가장 왼쪽 위부터 DFS를 진행한다. 2. 사이클이 한번이라도 생기는 경우 -1을 출력하고 끝낸다. 3. 사이클 없이 가장 멀리 간 거리를 .. 2023. 7. 26. [자바] 백준 1684 - 같은 나머지 (java) 목차 문제 : boj1684 필요 알고리즘 정수론, 유클리드 호제법 의외로 GCD 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다. 따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크.. 2023. 7. 25. [자바] 백준 9241 - 바이러스 복제 (java) 목차 문제 : boj9241 필요 알고리즘 그리디 알고리즘 그리디 풀이는 바로 보일 것 같다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 개인적으로 약간 선 넘는 문제였다. 일단 입력받은 문자열이 A, B 라고 한다면 A와 B 각각 앞부터와 뒤부터 동일한 부분이 어디까지인지 파악한다. 선 넘는다고 생각한 부분은, 당연히 하나 이상의 DNA는 바꿔야 된다고 생각했다. 예를들어 입력이 AAA와 AA일 경우 'AA' 를 제거 .. 2023. 7. 25. [자바] 백준 16491 - 대피소 찾기 (java) 목차 문제 : boj16491 필요 알고리즘 선분 교차 판정 선분 교차 판정만 할 줄 알면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 10밖에 안되므로, 단순하게 모든 경우 O(N!)을 보면 된다! 즉, N개의 로봇에 N개의 대피소를 모두 배치해보면서 조건을 만족하는 경우가 생기면 출력하면 된다. 조건을 만족하는 경우는, 현재까지 선택된 모든 로봇-대피소 쌍에 대해 선분 교차 판정을 해보면 된.. 2023. 7. 24. [자바] 백준 16965 - 구간과 쿼리 (java) 목차 문제 : boj16965 필요 알고리즘 너비 우선 탐색 (bfs) 뭔가 bfs와 관련없어 보이지만, bfs 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 우선 '이 글'을 참고해보자. 결국 이 문제에서 중요한건 '구간 (x1, y1)에서 구간 (x2, y2)로 이동하려면 x2 < x1 < y2 또는 x2 < y1 < y2를 만족' 이 부분이다. 처음엔 서로소 집합 (disjoint set)으.. 2023. 7. 23. 이전 1 ··· 3 4 5 6 7 8 9 ··· 74 다음
