전체 글1047 [자바] 백준 12886 - 돌 그룹 (java) 목차 문제 : boj12886 필요 알고리즘 그래프 탐색 의외로 탐색 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 문제이다. 예를들어 10개의 정수 중 8개 정수의 합이 100인 정수 8개가 존재하는지 알아내야 한다고 해보자. 직관적으로 우린 그냥 나머지 2개의 합이 '전체의합-100'인 2개가 존재하는지 찾게 될 것이다. 이 문제도 나머지의 관점에서 생각해보자. S=A+B+C라고 해보자. 이 때 A,B.. 2023. 11. 27. [자바] 백준 14567 - 선수과목 (Prerequisite) (java) 목차 문제 : boj14567 필요 알고리즘 위상 정렬 위상 정렬을 응용해서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 위상 정렬을 응용해서 해결했다. 아래와 같이 해당 정점에서 선수과목이 몇 개 인지 따로 기록해둔다. 이걸 차수라고 하겠다. 선수 과목이 없는 과목부터 몇 학기에 이수했는지(거리) 알기 위해 bfs를 돌린다. 이 때 큐에 넣을 시 차수를 1씩 빼고, 해당 정점의 차수가 0이 되면 큐에 넣는다.. 2023. 11. 26. [자바] 백준 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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 105 다음
