나의개발일지

https://www.acmicpc.net/problem/24479 자칭 DFS, BFS 기계로서,, 문제 읽고 10분만에 구현 끝냈는데,, 제출하니 1초만에 틀렸다고 나왔다,,아무리 이것저것 테케 넣어봐도 맞는데,, 하다가 발견했다 내가 문제를 잘못 이해했다는 것을,,!!!말 그대로 방문순서를 저장했었어야 했는데 나는 DFS 재귀에 cnt 넣어서 시작점으로부터 거리가 얼마나 떨어져 있는 지를 저장하고 있었음,,무튼 이거 제외하면 단순 DFS 구현 문제였다!다만, 오름차순 정렬만 주의 하면 된다. 아래가 제출 코드(정답)이고,package STUDY;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

https://www.acmicpc.net/problem/2343  글을 읽으면서 블루레이의 크기를 mid로 두고 조건을 만족하는 경우의 최솟값을 구하면 됨을 알 수 있었다.조건은 calc 함수를 통해 arr을 순서대로 탐색하며 현재 블루레이 크기 mid인 경우 만들어지는 블루레이 개수 cnt 를 구해 비교해보면 된다.이때, 블루레이 크기보다 강의의 크기가 커서 담기지 않는 경우를 꼭 고려해주어야 한다.또한, 블루레이가 다 찬 경우 시작값에 현재 강의 시간을 잘 담아서 다시 계산해주어야 한다.마지막으로, 블루레이 개수가 꼭 m과 같아야하는 것이 아닌 작을 때도 고려해서 최솟값을 갱신하면 된다! start 값은 1 end 값은 총 강의 시간을 넘어가진 않을 것이므로, 총 강의 시간으로 설정했다.packag..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 시간의 최솟값을 구해야하고, 범위로 알 수 있듯 이분탐색 문제였다.문제를 읽으면서 우선 시간을 mid로 설정하고 구하면 되겠다 싶었는데, 문제는 조건을 어떻게 설정하냐 였다.주어신 심사대에서 처리 가능한 인원수 = 현재 주어진 시간(mid) / 각 심사대에서 걸리는 시간 을 이용하면 되는 문제였다.(즉, 만약 30시간이 걸린다고 했을 때 주어진 테케에서는 1번 심사대: 30/7 = 4.XX명, 2번 심사대: 30/10 = 3명으로 최대 7명 처..

https://www.acmicpc.net/problem/2512 이 문제의 경우 예산액의 범위가 1 이상 100,000 이하여서 굳이 이분탐색이진 않아도 될 거 같긴 하다만, 이분탐색으로 풀었음.지방 예산액과 총 예산액이 주어졌을 때, 해당 총 예산액을 만족하는 최대 예산 상한액을 구하는 문제.그렇다면 이 최대 예산 상한액을 m으로 두고 1 ~ 최대 지방 예산액 사이에서 조건을 만족하는 m 값을 구하면 된다.조건을 만족하는 지 확인하는 코드는 다음과 같다. // 총 예산 계산int sum = 0;// 모든 지방의 예산의 예산 상한액보다 작을 경우 idx의 default값은 n이어야 함int idx = n;// 1. 현재 예산 상한액(m) 보다 작은 지방 예산의 합 = arr[i]원for(int i=0;..

https://www.acmicpc.net/problem/11561   처음에 이분탐색이라는 아이디어를 떠올리는 게 어려운 문제였다,,근데 자세히 보면 N의 범위로 보아 선형탐색은 절대 아니고, 두 번째 점프부터 이전 점프 + 1 긴 거리를 점프한다는 점에서 등차수열을 떠올릴 수 있다.그리고 최대 수이니 결국은 무조건 다음 식을 만족한다. => 다음 점프 = (이전 점프 + 1)그렇다면, 몇 개의 징검다리를 건넜을 때가 최대 징검다리가 될 까? 이 징검다리 수를 m으로 두고 이분탐색을 통해 조건을 만족하는 최대 m 값을 구하면 된다.그리고 조건은, m * (m + 1) / 2기 N의 값에 가장 가까우면 된다. (등차수열의 합 공식 사용)주의점은 N의 최대 범위를 고려하여 자료형을 long으로 사용해야 한..

https://www.acmicpc.net/problem/2776 앞선 문제에 이어 골라본 이분탐색 문제.자신 있게 풀다가 잊고있던 StringBuilder의 위력을 다시금 일깨워주었다,, package BOJ;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ_2776 { static int T; static int n, m; static int[] arr; static StringBuilder sb; public static void b..

https://www.acmicpc.net/problem/1072 승률이 달라지기위한 게임 횟수를 구하는 문제였다.처음엔 1부터 탐색했는데 생각해보니 X의 범위를 고려했을 때 최악의 경우 10억까지 탐색해야 했다. O(N)따라서 이분탐색으로 풀어야 하는 문제였다. O(logN) package STUDY;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Day01_BOJ_1072 { static int x, y; static int res; public static void main(String[] ..