본문 바로가기

PS/BOJ764

[자바] 백준 30646 -최대 합 순서쌍의 개수(java) 목차 문제 : boj30646 필요 알고리즘 누적 합(prefix sum), 해시를 사용한 집합과 맵 누적합과 해시맵을 사용해 풀 수 있다. 물론 언제나 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 보자. 이 문제를 풀기위한 로직을 생각해보면 다음을 알 수 있어야 한다.. 2023. 12. 6.
[자바] 백준 20500 - Ezreal 여눈부터 가네 ㅈㅈ(java) 목차 문제 : boj20500 필요 알고리즘 동적 계획법 (DP), 정수론 정수론 특히 나머지 연산의 성질에 대해 알아야 하고, 효율적으로 풀기 위해 DP가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같이 자리수를 늘려나가 만들어지는 N자리 양의 정수 중 15의 배수가 몇 개인지 구하는 문제이다. 당연하게도 1과 5로 이루어진 N자리 수는 2^N 개나 된다. 2^1515개의 정수는 천문학적인 수치이므로 .. 2023. 12. 5.
[자바] 백준 1612 - 가지고 노는 1 (java) 목차 문제 : boj1612 필요 알고리즘 수학, 정수론 나머지 연산의 성질을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N의 실제 배수를 계산하면서 전부 1로만 이루어져 있는지 확인하는건 상당히 난감하다. 반대로 생각해보자. 결국 1, 11, 111, 1111, .... 이런 수가 결국 N으로 나누어 떨어진다면 N의 배수인거다. 이 경우엔 좀 쉬워진다. 그냥 1, 11, 111, ... 이런 .. 2023. 12. 4.
[자바] 백준 1584 - 게임 (java) 목차 문제 : boj1584 필요 알고리즘 0-1 너비 우선 탐색 (0-1 bfs), 다익스트라 (dijkstra) 간선이 0 또는 1일 경우에 대한 문제이다. 다익스트라로도 풀 수 있고, 0-1 bfs를 쓰면 더 효율적으로 가능하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 맵의 각 지점의 상태는 안전, 위험, 죽음 이다. 죽음은 아예 안가면 되므로 딱히 상관없다. 안전과 위험만 보면 되는데, 안전은 가중치가 0인 셈.. 2023. 12. 1.
[자바] 백준 10448 - 유레카 이론 (java) 목차 문제 : boj10448 필요 알고리즘 브루트 포스 단순히 모든 경우를 살펴보는 것으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제를 약간 바꿔서 생각해보자. X개의 숫자가 주어진다. 그 중 3개를 합한 값이 N인 경우가 있다면 1, 없다면 0을 출력하는 문제이다. 이 때, 단순하게 3개의 수를 골라 합쳐보면서 정말 있는지 없는지 확인해본다고 하자. 이 경우 시간 복잡도는 O(X^3) 이고.. 2023. 12. 1.
[자바] 백준 2036 - 수열의 점수 (java) 목차 문제 : boj2036 필요 알고리즘 그리디 최선의 방법을 찾아 규칙대로 구현하면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력으로 들어오는 값은 결국 음수, 0, 양수 이렇게 3가지 종류이다. 이 때 곱해서 이득이 되는걸 생각해보자. 음수와 음수, 음수와 0, 양수와 양수 이렇게 3가지 경우이다. 그 외의 경우엔 항상 손해이다. 또한 음수와 0 보다는 음수와 음수가 더 이득이다. 그래서 대.. 2023. 11. 30.
[자바] 백준 25381 - ABBC (java) 목차 문제 : boj25381 필요 알고리즘 그리디 적절한 규칙을 적용해 선택해 나가는 방식으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어.. 이럼 되지 않나? 해서 구현해보니 됬다. 그래서 딱히 풀이랄건 없구 규칙을 적어보면 다음과 같다. 1. 'C'를 좌측부터 우측으로 차례대로 찾으면서, 해당 위치 이전에 가장 처음으로 나왔던 'B'와 함께 지운다. 2. 'A'를 우측부터 좌측으로 차례대로 .. 2023. 11. 29.
[자바] 백준 26598 - 색종이와 공예 (java) 목차 문제 : boj26598 필요 알고리즘 애드 혹(ad hoc), 그래프 탐색(dfs, bfs) 이 문제만의 규칙을 찾아 해결하는 애드혹 문제이다. 구현을 위해 그래프 탐색을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 이하의 로직으로 진행했다. 1. 맵의 좌측상단부터 우측 하단으로 진행하면서, 이미 찾은 직사각형임을 찾은 곳은 체크를 해둔다 (다시 직사각형의 여부를 확인하지 않아도 되도록). 2. .. 2023. 11. 28.
[자바] 백준 30536 - 시루의 산책 (java) 목차 문제 : boj30536 필요 알고리즘 그래프 이론, bfs (너비 우선 탐색) 문제에서 제시된 데이터를 그래프로 생각하고, 적절한 방식으로 탐색해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선.. 내 경우 맞왜틀을 많이 외친 문제였다 ㅠ. 그 이유는 아래와 같다. 1. 난 각 기둥의 상태가 'A. 다른 강아지 마킹 있음', 'B. 마킹은 없으나 다른 강아지 냄새가 영향을 끼침', 'C. .. 2023. 11. 28.
[자바] 백준 12886 - 돌 그룹 (java) 목차 문제 : boj12886 필요 알고리즘 그래프 탐색 의외로 탐색 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 문제이다. 예를들어 10개의 정수 중 8개 정수의 합이 100인 정수 8개가 존재하는지 알아내야 한다고 해보자. 직관적으로 우린 그냥 나머지 2개의 합이 '전체의합-100'인 2개가 존재하는지 찾게 될 것이다. 이 문제도 나머지의 관점에서 생각해보자. S=A+B+C라고 해보자. 이 때 A,B.. 2023. 11. 27.

티스토리툴바