본문 바로가기

전체 글1104

[자바] 백준 2632 - 피자판매 (java) 목차 문제 : boj2632 필요 알고리즘 누적 합 (prefix sum), 해시를 사용한 집합과 맵 누적합을 통해 구간의 합을 빠르게 구하고, 그 값을 빠르게 찾을 수 있으면 된다. 다만 원형이므로 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 누적합 알고리즘을 모르면 풀기 매우 어려워지고, 어렵지 않으면서 엄청 자주 쓰이는 알고리즘이므로 모른다면 이 글을 먼저 읽자. 문제를 좀 단순화해서.. 2023. 7. 20.
[자바] 백준 1263 - 시간 관리 (java) 목차 문제 : boj1263 필요 알고리즘 그리디 잘 생각해보면 어! 이렇게 하면 되지 않나? 싶은 룰이 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 물어보는건 모든 일을 끝낼 수 있는 가장 늦은 시간이다. 근데 좀 바꿔서 생각해보자. 애초에 모든 일을 끝낼 수 있나 없나를 어떻게 판단할 수 있을까? 중요한건 S값이다. 언제 시작하는진 상관없고, 아무튼 N개의 일들에 대해 각 S값 이내로만 끝낼 수 있으.. 2023. 7. 20.
한별이 하악.. 솔브닥 굿즈 도착! 솔브닥 시즌 2 통계 풀 세트 굿즈 도착! 배경을 시즌1 플래2달성 배경으로 해서, 시즌1 플래2 -> 시즌2 다야5 까지 현재 시즌 2개 다 통계로 볼 수 있도록 신청했다. 전체적으로 퀄리티가 좋아서 완전 맘에 들었다. 2023. 7. 19.
[자바] 백준 28276 - Yawned-Zoned (java) 목차 문제 : boj28276 필요 알고리즘 이분 탐색(binary search), 매개 변수 탐색(parametric search) 이분 탐색을 응용한 매개 변수 탐색 알고리즘 문제이다. 흔히 결정 문제라고 부르는 형태의 문제이다. 물론 결정 문제로 어떻게 만들지는 아이디어가 떠올라야 하긴 하다. 분리 집합(disjoint set) 결정 문제로 풀고자 할 경우, 분리 집합을 써야 효율적으로 짤 수 있다. 애초에 시간 제한이 빠듯한 문제라 다른 방법으론 통과가 힘들 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보.. 2023. 7. 18.
[자바] 백준 2343 - 기타 레슨 (java) 목차 문제 : boj2343 필요 알고리즘 매개 변수 탐색 (parametric search), 이분 탐색 (binary search) 이분 탐색을 응용한 매개 변수 탐색을 사용해 푸는 문제이다. 이런류는 매개 변수 탐색할 값에 대한 정의만 잘 세우면 갑자기 문제가 쉬워진다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일단 순차적으로 생각해보자. 1. 우선 isPossible(int limit) 이라는 함수를 생각해보자... 2023. 7. 17.
[종만북] CHILDRENDAY - 어린이날 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-CHILDRENDAY 풀이 만약 특정 자릿수(D)만을 포함하여 만든 십진수에 대해 N으로 나누어 떨어지는 가장 작은 수를 구하는 문제가 있다고 해보자. 이 경우 웰-논한 방법이 있는데, 나머지 연산의 성질을 이용하면 된다. 사용할 수 있는 자릿수가 '1, 2, 3'일 경우 1을 뒤에 붙이는 경우, 2를 붙이는 경우, 3을 붙이는 경우가 있을 것이다. 이런식으로 해보면 다음과 같이 진행될 것이다. 각 단계마다 진행하다가 N으로 나눈 나머지가 0일 경우 멈추면 된다. 이 때 구하려는 수를 C라 할 때, C는 엄청 커다란 수가 될 수 있다. 대충 N이 10000이므로 총 1만자리까진 가능 할 것같다. 따라서 이걸 큰 수로 계산하게 되면 시.. 2023. 7. 17.
[종만북] SORTGAME - Sorting Game (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-SORTGAME 풀이 우선 생각해야 할 부분은, '한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수' 라는 지문 부분이다. 1부터 1백만 사이로 입력이 들어오는게 의미가 있을까? 어차피 대소 관계 순서만 동일하다면 전혀 상관 없다. 따라서 값 압축을 통해 1부터 N까지의 값으로 우선 압축해서 생각하자. 예를들어 N개가 '1000000 4 2 5000' 이렇게 들어왔다면, 압축해서 '4 2 1 3'와 같이 생각하면 된다. 또한 N은 최대 8 이므로, 정수 하나로 표현할 수 있다. 즉 위의 '4 2 1 3'은 '4213'에 해당한다. private int compressedNum(int .. 2023. 7. 17.
[자바] 백준 14204 - 표 정렬 (java) 목차 문제 : boj14204 필요 알고리즘 그리디, 애드 혹 일반적인 풀이 유형이 없는 애드 혹 문제이다. 내 경우엔 그리디한 방식으로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 참고로 '행 우선 순서' 라는 말은 아래처럼 행으로 쭉 정렬되어있음을 뜻한다. 1 2 3 4 5 6 '열 우선 순서' 라면 아래와 같은 형태다. 1 3 5 2 4 6 처음엔 원래 있어야 할 위치 기준 맨허튼 거리를 공책에 써보니 나름 .. 2023. 7. 13.
[자바] 백준 24395 - 명진이의 신년계획 (java) 목차 문제 : boj24395 필요 알고리즘 DP, 냅색 흔히 냅색이라 부르는 유형의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 기본적인 냅색 문제인데, 2차원으로 진행된다는 점만 주의하면 된다. dp[x][y]를 빨강 알약 x개, 파란 알약 y로 처방 가능한 위험도의 최대치라고 하자. 이 경우 처방할 빨강, 파랑 알약의 수가 r과 b라고 한다면, dp[x][y] = max(dp[x][y], dp[x-r].. 2023. 7. 13.
[자바] 백준 17365 - 별다줄 (java) 목차 문제 : boj17365 필요 알고리즘 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static.. 2023. 7. 10.

티스토리툴바