본문 바로가기

BOJ749

[자바] 백준 21740 - 도도의 수학놀이 (java) 문제 : boj21740 필요 알고리즘 개념 그리디, 정렬, 문자열 그리디로 풀 수 있는 문제이다. 다만 플래문제답게 세세하게 예외를 생각해봐야하고, 구현이 좀 까다로울 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 이 문제가 플래인 이유는 '단 한 번, 한 수를 두 번 사용할 수 있다.' 이것 때문이다. 아마 저 조건이 없었으면 실버급이었을 것 같다. 그러므로 우선 '단 한 번, 한 수를 두 번 사용할 수 .. 2023. 1. 11.
[자바] 백준 20303 - 할로윈의 양아치 (java) 문제 : boj20303 필요 알고리즘 개념 분리집합 또는 dfs 또는 bfs DP로 실제 답을 구하는 로직 이전에 아이들의 그룹을 만들기 위해 분리집합 알고리즘(union-find) 혹은 그래프 탐색이 필요하다. 이하 풀이는 분리집합으로 풀었다. DP (Knapsack) DP 활용법 중 유명한 냅색류의 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 연결된 아이들의 그룹별로 선택할 수 밖에 없다. 따라서 만약.. 2023. 1. 11.
[자바] 백준 8783 - Architektura niezależna (java) 문제 : boj8783 필요 알고리즘 개념 - 그래프 탐색 (bfs, dfs) 단순히 bfs 혹은 dfs로 그래프 탐색만 해주면 된다. 다만 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 bfs를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 문제 자체는 간단하다. '#'으로 둘러싸인 부분 내부의 빈칸까지 포함해서 넓이를 구하면 된다. 예를들어 예.. 2023. 1. 10.
[자바] 백준 2571 - 색종이 - 3 (java) 문제 : boj2571 필요 알고리즘 개념 누적 합 (prefix sum) 2차원 누적합 문제인데, 빈 공간을 포함하지 않기 위한 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 누적합 알고리즘으로 O(N^4)으로 풀었다. 다만 실제로 N^4은 아니고, 약간의 백트래킹도 포함되었고, 한쪽 방향으로 탐색 범위를 고정했으므로 4중 반복문이긴 하지만 N^4보단 낮다. 우선 2차원 누적합 알고리즘으로 직.. 2023. 1. 10.
[자바] 백준 14927 - 전구 끄기 (java) 문제 : boj14927 필요 알고리즘 개념 브루트 포스, 그리디 약간의 브루트 포스 + 그리디가 필요하다. 둘 다 알고리즘이라기보다는 개념적인 부분이라, 구현이 크게 어렵지 않은데 아이디어가 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 보통 2차원 문제는 1차원으로 먼저 생각하면 더 쉽게 아이디어를 떠올릴 수 있다. 문제를 간단히 하기 위해 1차원에서만 우선 생각해보자. A. 1차원에서 생각해보자. 선택.. 2023. 1. 6.
[자바] 백준 9024 - 두 수의 합 (java) 문제 : boj9024 필요 알고리즘 개념 정렬, 투 포인터 투 포인터로 해결 가능한 문제이다. 투 포인터 사용을 위해 정렬도 해줘야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 두 정수의 합이 K와 가장 가까운 두 정수의 조합의 수를 찾는 문제이다. 얼핏 K와 동일한 수가 아니라 K와 가장 가까운 두 정수를 찾는거여서 투 포인터로 해결이 안된다고 생각할 수 있다. (예를들어 K=8이고, 두 정수의 합이 8인 경우가.. 2023. 1. 4.
[자바] 백준 2843 - 마블 (java) 문제 : boj2843 필요 알고리즘 개념 오프라인 쿼리 (offline query) 쿼리(질의)의 순서를 변경해서 푸는 아이디어를 생각해낼 수 있어야 한다. 분리 집합 (disjoint set) 분리 집합 개념과, 분리집합에서 집합이 합쳐지는 방향을 강제할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 조약돌이 멈추는 정점을 묻는 쿼리와 간선을 지우는 쿼리가 존재한다. 일반적으로 간선을 지우.. 2023. 1. 2.
[자바] 백준 23324 - 어려운 모든 정점 쌍 최단 거리 (java) 문제 : boj23324 필요 알고리즘 개념 분리 집합 (disjoint set) 그룹의 갯수를 알아야 풀 수 있으므로 내 경우엔 분리 집합 알고리즘을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 풀이는 금방 생각나긴했지만 가중치가 1과 0이라는 점과, 실제로 탐색을 통해 모든 정점에서 최단 거리를 판단할 경우 무조건 시간초과가 발생하도록 문제가 세팅되었다는 점에서 출제 아이디어가 좋다고 생각했다. 그래프쪽.. 2023. 1. 1.
[자바] 백준 8111 - 0과 1 (java) 문제 : boj8111 필요 알고리즘 개념 수학 나머지 연산의 규칙에 대해 알고 있어야 풀 수 있다. 너비 우선 탐색 (BFS) 수학적으로 풀 방법이 생각났다면, 이후 BFS를 적용해서 구현할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS를 모른다면 이 글을 참고하자. 문제 조건 자체는 그리 어렵지 않다. 테스트 케이스야 동일 동작이니 일단 생각하지 말자. 그냥 1부터 시작해서(시작이 0이면 안된다고 .. 2022. 12. 27.
[자바] 백준 9465 - 스티커 (java) 문제 : boj9465 필요 알고리즘 개념 동적 계획법 (Dynamic Programming, DP) DP로 풀 수 있는 문제이다. DP는 알고리즘이라기 보단 문제 푸는 방식? 같은 거라 생각한다. 어쨌든 어떤건진 미리 알고 풀어야 생각해낼 수 있을 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 스티커 위치가 아래와 같다고 해보자. A C E B D F 이 때, 각 스티커의 가치 중 음수인 것은 없으므로 결국 우측.. 2022. 12. 21.

티스토리툴바