PS/BOJ764 [자바] 백준 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. [자바] 백준 2632 - 피자판매 (java) 목차 문제 : boj2632 필요 알고리즘 누적 합 (prefix sum), 해시를 사용한 집합과 맵 누적합을 통해 구간의 합을 빠르게 구하고, 그 값을 빠르게 찾을 수 있으면 된다. 다만 원형이므로 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합 알고리즘을 모르면 풀기 매우 어려워지고, 어렵지 않으면서 엄청 자주 쓰이는 알고리즘이므로 모른다면 이 글을 먼저 읽자. 문제를 좀 단순화해서.. 2023. 7. 20. [자바] 백준 1263 - 시간 관리 (java) 목차 문제 : boj1263 필요 알고리즘 그리디 잘 생각해보면 어! 이렇게 하면 되지 않나? 싶은 룰이 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 물어보는건 모든 일을 끝낼 수 있는 가장 늦은 시간이다. 근데 좀 바꿔서 생각해보자. 애초에 모든 일을 끝낼 수 있나 없나를 어떻게 판단할 수 있을까? 중요한건 S값이다. 언제 시작하는진 상관없고, 아무튼 N개의 일들에 대해 각 S값 이내로만 끝낼 수 있으.. 2023. 7. 20. 이전 1 ··· 5 6 7 8 9 10 11 ··· 77 다음
