본문 바로가기

PS/BOJ743

[자바] 백준 24891 - 단어 마방진 (java) 목차 문제 : boj24891 필요 알고리즘 브루트 포스 그냥 모든 경우를 다 확인해보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최악의 경우가 20개의 단어 중 5개를 순서대로 뽑는 경우이므로 20P5 = 20*19*18*17*16 번 정도면 모든 경우를 다 확인할 수 있다. 그리고 마방진임을 확인하는데에는 최대 L^2 이면 확인 가능하다. 결론적으로 그냥 브루트포스로 모든 경우를 확인하면 되는 문제이다. O(.. 2024. 3. 20.
[자바] 백준 2473 - 세 용액 (java) 목차 문제 : boj2473 필요 알고리즘 투 포인터 또는 이분 탐색 투 포인터를 쓰거나, 이분 탐색을 써서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 처음 생각난 아이디어는, 어차피 n이 5000이므로 2개를 고정시켜놓고, 나머지 하나의 값을 이분 탐색으로 찾는 방법이었다. 이 경우 O(N^2 * logN). 예를들어 현재 고정시켜둔 2개의 값이 -97와 -2라면, -(-97-2) = 99 .. 2024. 3. 20.
[자바] 백준 14503 - 로봇 청소기 (java) 목차 문제 : boj14503 필요 알고리즘 구현, 시뮬레이션, 탐색 (bfs, dfs 등) 그냥 문제에 제시된 대로 구현하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 딱히 풀이라 할 부분은 없을 것 같다. 문제에 제시된대로 구현하면 된다. 따라서 내 코드를 기준으로 어떤식으로 구현했는지만 얘기해보겠다. 우선 '방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 .. 2024. 3. 19.
[자바] 백준 19953 - 영재의 산책 (java) 목차 문제 : boj19953 필요 알고리즘 정수론, 비둘기집의 원리 비둘기집의 원리로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 실제로 시뮬레이션을 돌려보게 된다면, O(t) 이므로 시간초과가 나게 된다. 따라서 시간을 줄일 아이디어를 찾아야 하는데, 내 경우에 비둘기집의 원리로 시간을 줄였다. n+1마리의 비둘기가 n개의 비둘기집에 들어간다면 자명하게도 최소 1개 이상의 비둘기집은 2마리 이상의.. 2024. 3. 18.
[자바] 백준 1953 - 팀배분 (java) 목차 문제 : boj1953 필요 알고리즘 이분 그래프 (bipartite graph), 그래프 탐색 (BFS, DFS 등) 이분 그래프에 대한 개념이 있다면 좀 더 쉽게 풀 수 있는 그래프 탐색 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 2년전에 못 푼 기록이 있어 풀어봤다. 별 어려움 없이 바로 푼걸 보면 발전은 있었나보다. 2년전엔 HashSet을 사용해 넣을 때 마다 겹치는게 있는지 검색해본 것 같다. .. 2024. 2. 26.
[자바] 백준 16935 - 배열 돌리기 3 (java) 목차 문제 : boj16935 더보기 필요 알고리즘 구현력(?) 그저 제시된 대로 구현만 잘 하면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 그냥 제시된 대로 동작하도록 구현만 해주면 되는 문제이다. 경우에 따라 쉽지 않을 수 있긴 하다. 그래도 RPG Extreme (백준 17081) 같은 구현문제보다는 귀여운 편이다. 기왕 구현하는거 최대한 깔끔하게 한번 짜보면 개발 연습도 되고 좋다. 코드 :.. 2024. 2. 26.
[자바] 백준 17436 - 소수의 배수 (java) 목차 문제 : boj17436 필요 알고리즘 포함 배제의 원리 (inclusion and exclusion) 포함 배제의 원리로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 예제 입력 2를 생각해보자. 2 100 2 3 직관적으로 우린 이걸 푸는 방법을 알고 있다. 100 이하의 자연수 중 2로 나누어 떨어지는 수는 100/2 = 50개가 존재한다. 그리고 3으로 나누어떨어지는건 100/3 = 33개.. 2024. 2. 24.
[자바] 백준 24956 - 나는 정말 휘파람을 못 불어 (java) 목차 문제 : boj24956 필요 알고리즘 DP (동적 계획법) DP로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 'WHE'가 가능한 경우의 수를 찾는다고 생각해보자. 이 경우 매우 직관적으로 가능한데, 하나씩 문자를 살펴보면서 'W'라면 이전까지 나온 W의 수+1, 'H'라면 현재까지 'WH'가 가능했던 경우의 수 + 이전까지 나온 'W'의 수, 'E'라면 현재까지 'WHE'가 가능했던 경.. 2024. 2. 24.
[자바] 백준 16563 - 어려운 소인수분해 (java) 목차 문제 : boj16563 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본.. 2024. 2. 23.
[자바] 백준 3142 - 즐거운 삶을 위한 노력 (java) 목차 문제 : boj3142 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 완전제곱수인지 우선 생각해보자. 내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다. 예를들어서 예제 입력 2를.. 2024. 2. 23.