본문 바로가기

전체 글1025

[자바] 백준 2190 - 점 고르기 2 (java) 목차 문제 : boj2190 필요 알고리즘 브루트 포스 (brute force) 약간의 아이디어만 더해주면 그냥 브루트포스로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 보통 2차원인 문제는 우선 1차원으로 생각해보면 접근하기 쉬운 경우가 많다. 이 경우에도 그냥 직선에 N개의 x좌표가 주어진다고 하고, 길이 A 짜리 막대로 가장 많은 점을 포함한다고 생각해보자. 이 경우 가장 간단한 방법은 N개의 점을 시작.. 2023. 11. 25.
[자바] 백준 22956 - 소나기 (java) 목차 문제 : boj22956 필요 알고리즘 분리 집합 (union-find) 분리 집합을 활용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기위해 알 수 있어야 하는건 말로하면 간단하다. 인접한 비가 내렸었던 땅들의 그룹들이 있다. 그리고 어딘가 비가 내렸다면, 상하좌우 인접한 비가 내렸던 땅들의 그룹을 합친다. 그리고 그 그룹들에서 가장 높이가 낮은 칸 또는 여러개라면 그 중 가장 .. 2023. 11. 24.
[자바] 백준 28706 - 럭키 세븐 (java) 목차 문제 : boj28706 필요 알고리즘 DP (동적 계획법) DP로 해결 가능한 문제이다. 이하 풀이는 bit DP (비트필드를 이용한 다이나믹 프로그래밍)로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 모든 경우의 수를 본다고 해보자. 1부터 시작해서 차례차례 경우의 수를늘려가는거다. 이러면 당연히 2^200000의 경우의 수가 존재하므로 너무나 천문학적인 수치이다. 그럼 어떻게 해야할까? 이 문제에서 결과.. 2023. 11. 24.
[자바] 백준 23040 - 누텔라 트리 (Easy) (java) 목차 문제 : boj23040 필요 알고리즘 분리 집합 (union-find), 그래프 탐색 (bfs, dfs 등), 트리 (tree) 그래프 탐색과 분리 집합에 대한 개념이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 만약 서로 붙어 있는 빨간 정점 그룹들의 갯수를 알고 있다고 해보자. 그럼 간단하게 모든 검정 정점들에서 간선 1개로 갈 수 있는 모든 정점 중 빨간 정점 그룹의 수를 모두 세주면 끝나는 .. 2023. 11. 22.
[자바] 백준 11108 - TV 전쟁 (java) 목차 문제 : boj11108 필요 알고리즘 동적 계획법 (DP), 그리디 최선의 규칙을 모든 경우에 적용할 수 있는 그리디 문제이고, 직전까지의 최대 값을 알기 위해 DP를 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 시간의 최대값은 10080이다. dp[x]를 '시간 x까지 획득 가능한 선호도의 최대치' 라고 정의해보자. 예를들어 예제 입력 1을 보자. 1 3 3 8 10 1 4 6 6 4 5 d.. 2023. 11. 21.
[자바] 백준 29730 - 임스의 데일리 인증 스터디 (java) 목차 문제 : boj29730 필요 알고리즘 문자열, 파싱, 정렬 문자열을 파싱할 줄 알고, 원하는 방식으로 정렬할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기위해 해결해야 하는건 다음과 같다. 내 경우엔 이하의 코드처럼 해결했다. 1. 'boj.kr/문제 번호' 형태를 판단할 수 있어야 한다. 이 때 '문제 번호'는 정수여야하고 1부터 30000의 범위여야 한다. 테스트 케이스는 모르지만.. 2023. 11. 21.
[자바] 백준 20956 - 아이스크림 도둑 지호 (java) 목차 문제 : boj20956 필요 알고리즘 두 포인터 (투 포인터, two pointer), 정렬 투 포인터로 해결할 수 있는 문제이다. 다만 일반적인 투 포인터 사용 형태와는 약간 다르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력받은 N개의 아이스크림 정보에 대해 양을 a, 번호를 idx 라고 하자. 그럼 우선 입력받은 후 a desc, idx asc로 정렬한다. @Override public int compa.. 2023. 11. 21.
[자바] 백준 3151 - 합이 0 (java) 목차 문제 : boj3151 필요 알고리즘 브루트포스 (brute force) 모든 경우를 보면 되긴한데, 효율적으로 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단순히 생각하면 10000C3을 전부 보면 되는데 당연히 그러면 대충 O(10000^3) 이므로 비효율적이다. 약간 아이디어를 더해보자. N개의 수를 입력 받으면서 어떠한 수가 몇 번 나왔는지 미리 세두자. HashMap으로 처리해도 되고, 그냥 들어.. 2023. 11. 21.
[자바] 백준 14257 - XOR 방정식 (java) 목차 문제 : boj14257 필요 알고리즘 조합론, 수학 수학적인 직관이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 당연히 S와 X를 숫자 그 자체로 생각해보면 딱히 할 수 있는게 없다. 그리고 A+B=S야 그렇다 쳐도, A^B=X 는 어차피 비트단위로 연산되는 녀석이라, 비트단위로 봐야 뭔가 보일꺼라 생각했다. 그래서 비트로 변경해두고 보다보니 풀이가 보여서 풀게 되었다. 일단 당연하게도 A^B의 결.. 2023. 8. 11.
[자바] 백준 28251 - 나도리합 (java) 목차 문제 : boj28251 필요 알고리즘 수학, 분리 집합 (disjoint set, union-find) 기본적인 아이디어는 수학적 직관이 좀 필요하고, 그 직관을 구현하기 위해 분리 집합 알고리즘을 사용해야 하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 4개의 수 a,b,c,d가 있다고 해보자. a와 b를 합치면 ab, c와 d를 합치면 cd가 필요하다. 그 후 ab와 cd를 합쳐보면 아래처럼 식이 나.. 2023. 8. 11.