본문 바로가기

BOJ747

[자바] 백준 18436 - 수열과 쿼리 37 (java) 목차문제 : boj18436  필요 알고리즘세그먼트 트리, 펜윅 트리, 제곱근 분할법위 알고리즘 혹은 자료구조 중 아무꺼나 쓰면 된다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  세그먼트 트리, 펜윅 트리, 제곱근 분할법 등 풀 수 있는 방법은 많다. 아무튼 단일 업데이트, 범위 쿼리를 유효한 시간 내에 처리 가능한 코드를 짜면 된다. 이하 코드는 펜윅 트리를 사용해 풀었다. 펜윅트리에 대한 설명은 '이 글'에서 볼 수.. 2024. 5. 24.
[자바] 백준 2026 - 소풍 (java) 목차문제 : boj2026  필요 알고리즘브루트포스, 백트래킹백트래킹을 써서 모든 경우를 살펴보면 된다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  그냥 백트래킹 섞어서 브루트포스로 해보고 안되면 다른 방법을 찾으려고 했는데 통과됬다. 초기 명분(?)은 어차피 최악의 경우 K가 62일 경우, 최소로 필요한 간선은 62*61 = 3782개인데 F가 최대 5600이라서 최악의 경우라도 5600개 중 3782개가 쓰여야 되므.. 2024. 5. 23.
[자바] 백준 21610 - 마법사 상어와 비바라기 (java) 목차문제 : boj21610더보기  필요 알고리즘시뮬레이션제시된 대로 구현하면 된다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  그냥 문제에 제시된대로 구현하면 되서 풀이는 필요없을 것 같다. 이하 코드는 그냥 풀긴 좀 심심할 것 같아서 2차원 배열을 쓰지 않고 풀어봤다. 그러니 2차원 배열 안쓰고 푸는걸 참고하려면 코드를 확인해보자. 각 단계별로 처리하는 코드는 주석을 달아두었다. 2차원 배열로 문제에 제시된대로 구현.. 2024. 5. 23.
[자바] 백준 27501 - RGB트리 (java) 목차문제 : boj27501  필요 알고리즘트리 DP (트리 + 동적계획법)트리에서 DP를 사용해 푸는 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  '백준 1149 RGB거리' 문제의 트리버전이라고 보면 된다. 그러니 저걸 안풀었다면 저것부터 풀어보자. 1149를 못푸는데 이 문제를 풀 수 있을 가능성은 없다.   우선 간소화해서 생각해보기 위해, 이 문제를 1149번 문제처럼 트리긴한데 그냥 1차원이었다고 생.. 2024. 5. 23.
[자바] 백준 2981 - 검문 (java) 목차문제 : boj2981  필요 알고리즘유클리드 호제법, 정수론gcd를 구해서 풀 수 있는 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  N개의 숫자를 M으로 나누었을 때, 나머지가 모두 같게 되는 2이상의 M을 모두 찾는 문제이다. 이 경우, 우선 가장 큰 M만 찾으면 된다. 왜냐면 나머지 M은 가장 큰 M의 약수들을 찾아주면 되기 때문이다. 그럼 문제는 N개의 숫자를 M으로 나누었을 때 나머지가 모두 같게 .. 2024. 5. 22.
[자바] 백준 27650 - 마법박스 (java) 목차문제 : boj27650  필요 알고리즘매개 변수 탐색 (이분 탐색), 에라토스테네스의 체문제에서 제시된 것의 규칙을 찾아, 20번 내에 물어볼 수 있는 방법을 찾아야 한다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  처음엔 무지성으로 단순히 최대 500만개짜리 배열 만들어두고, 2부터 시작하면서 물어보고 1이라고 하면 2의 배수 전부 체크하는 식으로 생각했었다. 문제는 인터랙티브 문제라 틀렸습니다라고 안떴다는 점이.. 2024. 5. 17.
[자바] 백준 19700 - 수업 (java) 목차문제 : boj19700  필요 알고리즘그리디, 이분탐색그리디 아이디어만 있으면 난이도가 확 줄어드는 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  하나의 아이디어를 넣으면 난이도가 급하락하는 좋은 문제이다. 입력받은 h와 k를 h 기준으로 내림차순으로 정렬한다고 해보자. 그리고 h가 높은 순서대로 확인을 할껀데, 이래도 되는 이유가 '학생들의 키는 모두 다르다' 라는 조건이 있기 때문이다.   이렇게되면 난.. 2024. 5. 16.
[자바] 백준 1342 - 행운의 문자열 (java) 목차문제 : boj1342  필요 알고리즘수학 (순열 개념) 또는 브루트포스 + 백트래킹순열 개념을 사용해서 풀 수도 있고, 백트래킹을 써서 풀 수도 있다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  우선 순열 개념으로 푸는건 뒤로 미루고 브루트포스+백트래킹으로 푸는 것 부터 살펴보자.단순히 생각해보면 dfs로 모든 경우를 백트래킹하면서 찾은 후, 이미 나온 문자가 아니라면 카운팅하는 방법이 있을 것이다. 대강 O(10.. 2024. 5. 16.
[자바] 백준 24461 - 그래프의 줄기 (java) 목차문제 : boj24461  필요 알고리즘그래프 이론, 브루트 포스별다른 알고리즘 지식은 필요하지 않긴한데, 구현이 어려울 수 있다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  아래와 같은 그래프를 생각해보자.    각 정점에 대해 현재 연결된 간선의 수를 적어보면 아래와 같다. 이번에 제거될 가장자리 정점은 연결된 간선의 수가 '1'인 정점들임을 알 수 있다.    한 번 삭제된 후엔 아래와 같이 된다. 그리고 그래.. 2024. 5. 15.
[자바] 백준 11909 - 배열 탈출 (java) 목차문제 : boj11909  필요 알고리즘DP (동적 계획법)DP를 알고 있다면 쉽게 해결 가능한 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  need(X, Y)를 X 좌표에서 Y 좌표로 갈 때 필요한 비용이라고 하자. 예를들어 X가 (1,1), Y가 (1,2) 이고, 배열의 값이 각각 3과 5였다면 need(X, Y)는 3이다.   이 때 dp[a][b]는 (a, b) 좌표로 가는데 필요한 최소 비용이라고 .. 2024. 5. 14.