본문 바로가기

BOJ737

[자바] 백준 17365 - 별다줄 (java) 목차 문제 : boj17365 필요 알고리즘 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static.. 2023. 7. 10.
[자바] 백준 15681 - 트리와 쿼리 (java) 목차 문제 : boj15681 필요 알고리즘 DFS, 트리DP DFS로 트리DP를 진행하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 간선들을 입력받고, 루트가 주어져 있으므로 루트부터 DFS를 진행한다. 이 때 dfs() 함수는 리턴으로 자기자신을 포함해 자신 이하의 서브트리의 갯수를 리턴하는 것으로 정의한다. 그럼 이하처럼 코드를 짤 수 있고, 루트부터 시작해 모든 정점에 대해 DFS 진행하면서 dfs.. 2023. 7. 10.
[자바] 백준 3174 - 나누기 (java) 목차 문제 : boj3174 필요 알고리즘 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 우선 경우의 수를 어떻게 구할 수 있는지부터 생각해보자. 예제 입력 1을 보자. abcd 4 a b cd ab abcd 라는 문자열에서 우선 첫 번째 문자인 a부터 시작해보자. a부.. 2023. 6. 28.
[자바] 백준 9202 - Boggle (java) 목차 문제 : boj9202 필요 알고리즘 브루트포스, 백트래킹, 그래프 탐색(dfs 혹은 bfs 등), 트리, 트라이(Trie) 원래 플래급 가면 여러가지 섞어야 하는 경우가 많긴하다. 내 경우엔 메인 알고리즘은 트라이였고, 나머진 트라이로 로직 구현을 위한 부가적인 부분이었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일단 내 경우엔 트라이로 풀었는데, 의견쪽을 보니 시간이 널널해서 그냥 해싱 처리해도 된다고 한다... 2023. 6. 27.
백준 1002 자바 - 터렛 (BOJ 1002 JAVA) 문제 : https://www.acmicpc.net/problem/1002 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1002.java 피타고라스 정리 정도만 알면 풀 수 있는 문제이다. 다만 상당히 귀찮은 문제이긴 한데, 모든 경우에 대해 분기를 쳐서 답을 구해야 한다. (그래서 문제를 푼 사람이 많은 문제임에도 정답 비율이 21%로 낮은 편이다.) GPS 삼각측량처럼 위치를 계산하는건데, 2개의 지점에 대해 측량하므로 모든 케이스에서 정확한 위치를 알 순 없다. 각 점에서 r을 반지름으로 하는 원을 그렸을 때 서로의 원이 만나는 지점이 결국 류재명이 있는 위치라 할 수 있다. 그러니 모든 케이스를 생각만 해.. 2023. 6. 22.
[자바] 백준 12893 - 적의 적 (java) 목차 문제 : boj12893 필요 알고리즘 이분 그래프, 그래프 탐색(BFS, DFS 등) 이분 그래프가 만들어지는지 파악할수만 있으면 풀 수 있다. 일반적으로 이분 그래프 판정을 위해 DFS나 BFS를 사용한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각과정은 다음과 같다. 1. 적의 적은 친구라고 계속해서 연결해나갈 때, 결국 어느 누구의 관점에서 보든 서로 연관이 있는(간선이 연결되어진) N명이 정확히 적과 .. 2023. 6. 18.
[자바] 백준 27988 - 리본 (Hard) (java) 목차 문제 : boj27988 필요 알고리즘 그리디 알고리즘, 정렬 문제를 좀 더 간단히 생각해보면 동일한 규칙을 적용시켜서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 다음과 같다. 1. 일단 입력으로 들어온 데이터부터 좀 더 이해하기 편하게 바꿔보자. X위치에 달린 길이 L의 구부릴 수 있는 리본이라 함은 결국 [X-L, X+L] 에서 다른 색상을 만나기만 하면 되는 리본이라 볼 수 있다. [.. 2023. 6. 16.
[자바] 백준 1083 - 소트 (java) 목차 문제 : boj1083 필요 알고리즘 그리디 알고리즘 최선의 방법을 정해 매번 시도하면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 다음과 같다. 1. N이 50인데 S가 100만?! -> 버블 정렬 생각해보면 결국 N(1+N)/2번 수행되면 어차피 내림차순으로 가능하므로, S가 큰건 의미가 없다. S가 1275 초과일 경우 어차피 의미 없는 값이므로, 100만이라도 문제없음! if.. 2023. 6. 14.
[자바] 백준 21278 - 호석이 두 마리 치킨 (java) 목차 문제 : boj21278 필요 알고리즘 플로이드 와샬, BFS, 다익스트라 등 최단 거리 알고리즘 아무거나 최단 거리를 구할 수 있는 알고리즘으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 생각 과정은 이하와 같다. 1. 모든 건물에 대해 모든 쌍에 대한 최단 거리를 알 수 있다고 해보자. 2. 그렇다면 N개 중 2개의 건물을 고르기로 확정하고, '1'에서 구한 거리 정보로 '최단 시간의 총합.. 2023. 6. 13.
[자바] 백준 27468 - 2배 또는 0.5배 (java) 목차 문제 : boj27468 필요 알고리즘 애드 혹 이 문제에 맞는 규칙을 찾아 푸는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 힌트는 서브태스크 2번에서 얻었다. N은 4의 배수에 배점이 있는걸보고 4의 배수면 쉽겠구나 생각했다. 손으로 그려보면서 찾아보니 1,3,2,4 / 5,7,6,8 / ... 이런식으로 4의 배수는 무한정 가능함을 확인했다. 그리고 4로 나눈 나머지가 1인 경우도 문제없고(1,3.. 2023. 5. 15.

티스토리툴바