PS831 [자바] 백준 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. [자바] 백준 19845 - 넴모넴모 2020 (java) 목차 문제 : boj19845 필요 알고리즘 이분 탐색 의외로 이분 탐색 문제이다! 물론 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 설명이 좀 복잡해서 그렇지 잘 생각해보면 해야하는건 단순한 편이다. 배열 arr에다가 arr[1]부터 arr[n] 까지에 입력으로 주어진 N개의 정수 a를 순서대로 담아두었다고 해보자. 우선 오른쪽으로 나가는 레이저로 몇 마리가 제거되는지만 생각해보자. 이 경우 입.. 2023. 7. 22. [자바] 백준 2374 - 같은 수로 만들기 (java) 목차 문제 : boj2374 필요 알고리즘 분할정복 등 뭘 해야하는지만 파악했다면, 풀이는 다양하다. 내 경우엔 분할정복으로 처리했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일단 뭘 해야하는지 생각해보자. 대충 A를 그렸을 때 아래처럼 그림이 나올꺼다. 그럼 어차피 Add 연산만 있으니, 결국 모든게 최고지점을 향해 맞춰져야 한다. 근데 Add를 하면 인접한 같은 수도 같이 증가하므로, 모든 A[1], A[2],.... 2023. 7. 20. [자바] 백준 1490 - 자리수로 나누기 (java) 목차 문제 : boj1490 필요 알고리즘 브루트포스, 수학 오히려 무지성으로 풀면 정답인 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최악의 경우는 123456789 또는 987123456 처럼 1~9 모두로 이루어진 값이 입력으로 들어오는 경우이다. 이 때 lcm(1,2,3,...9)는 2520이다. 따라서 최악의 경우라도 9876543210000 이내로는 2520의 배수가 존재한다. 그러므로 생각보다 정답의.. 2023. 7. 20. 이전 1 ··· 5 6 7 8 9 10 11 ··· 84 다음
