나의개발일지

https://www.acmicpc.net/problem/2170 처음엔 pq를 사용했는데 시간초과가 떠서 방법을 변경했다.정렬 후에는 이후 값이 무조건 직전값에 영향을 받을 수 밖에 없기에 그때그때 확장하는 방법이 가능해진다. 1. x값 오름차순 정렬 x값이 같다면, y값 오름차순 정렬2. 만약 다음 값이 이전 값에 걸친다면 끝 좌표만 확장2. 만약 걸치지 않는다면 이전 선의 길이를 계산해 저장한 후, 현재 x, y를 새로운 시작과 끝 값으로 정의3. 마지막 선 길이까지 더한 후 결과 출력 package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

https://www.acmicpc.net/problem/1374 뒤에 오는 강의의 시작 시간이 앞 강의에 포함되는 지 확인하면 되는 문제이다.(단, 여러 강의실이 사용되고, 각 강의실마다 끝나는 시간이 다르니 이 경우를 모두 확인해 주어야 한다.)1. 우선 1차로 강의 시작시간을 오름차순으로 정렬하고, 시작시간이 같을 땐 종료시간을 기준으로 오름차순 정렬한다.(람다식 사용)2. 첫 번째 강의의 종료 시간을 pq에 넣는다. (가장 빨리 끝나는 강의실에 다음 강의를 배정해야하므로 우선순위큐를 사용했다.)3. 이전 강의의 가장 빨리 끝나는 시간이 현재 강의의 시작 시간보다 클 경우 (강의 시간이 겹칠경우) 강의실 수(cnt)를 1 증가시키고, 이전 강의 종료 시간과 현재 강의 종료 시간을 모두 pq에 넣는다..

https://www.acmicpc.net/problem/2212아 오늘은 아이디어를 떠올리는 게 쫌 어려웠다,,처음엔 이전 집중국과의 거리와 다음 센서 사이의 거리를 비교해서 더 이득인 경우를 택하는 형식으로 구현했는데,이 경우 집중국의 개수는 맞았지만 거리를 계산할 때 거리의 최솟값을 만족하지 못했다..그래서 고민고민하다가 구글링으로 스리슬쩍 구경했느데와 역으로 제일 먼 거리를 빼면 되는 아주 간단한 아이디어 였다,,그래서 결론은 1. 받은 센서의 좌표를 오름차순으로 정렬한다.2. 센서 사이의 거리를 구해서 배열에 저장한다.3. 이 센서 사이의 거리를 정렬해서 가장 거리가 먼 경우를 k-1 개 제외한 거리의 값을 더하면 최솟값이다.(k=2 일 때, 1(k-1)번 나누면 2그룹으로 나뉘고 이 2그룹에 ..

https://www.acmicpc.net/problem/31926요 문제를 통해 '애드 혹'에 대해 찾아봤다. 애드 혹은 특정 상황에서만 정답이 되고 일반화될 수 없는 것을 의미한다. (cf.달디달고 달디단)처음엔 그리디 문제 같아서 입력크기 잘 안봤다가 디피로 만들어서 메모리가 터졌다.그리고는 규칙을 찾으려고 주석에 분석했는데 (요런 문제가 헷갈려서 더 어려운 거 같다 ㅠ)앞 달디달고는 무조건 8이 되고, 뒤 달디단은 홀수 짝수 인 경우에 조금은 달라지긴 하지만 결국 2가 된다는 것을 알 수 있다.그리고 중간의 달디달고는 1, 2, 4, 8 씩 복사를 통해 생성된다는 것을 알 수 있다.따라서 10은 고정이고, n을 2로 나누면서 반으로 쪼개는 횟수를 더해주면 답이 된다. package Study.We..

https://www.acmicpc.net/problem/2847점수를 최소한으로 내려서 레벨점수를 증가하게 만들어야 하는 문제이다.이 경우 뒤에서부터 순차적으로 탐색하는 경우 최소한으로 만들 수 있다.뒤 점수보다 앞 점수가 같거나 크면 뒤 점수보다 1만큼만 작게 만들어줄 때 최소한으로 점수를 감소시키면 된다.** 1감소가 1점이므로 절댓값으로 계산해주어야 한다 package STUDY.Week03;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Day16_BOJ_2847_게임을만든동준이 { public static void main(String[] args) th..

https://www.acmicpc.net/problem/13417 카드를 순서대로 하나씩 가져오면서 사전 순으로 가장 빠르게 정렬하는 것. 이때 가장 왼쪽 또는 가장 오른쪽에만 둘 수 있다.핵심 아이디어는 문자를 하나씩 보면서 맨 앞 문자보다 순서가 빠르면 (아스키코드 값이 작으면) 맨 왼쪽에 두고,맨 앞 문자보다 순서가 느리면 (아스키코드 값이 크면) 맨 왼쪽에 두어야 겠다고 생각했다.그리고 자료구조는 Deque 또는 ArrayList 중에 고민하다가 후자를 택해 구현했다.(Deque를 사용한다면 peekFirst와 addFirst / add 를 사용하면 된다) package STUDY.Week03;import java.io.BufferedReader;import java.io.IOException;..

https://www.acmicpc.net/problem/14916동전의 개수를 최소로 사용하려면 5원을 최대한 사용해야한다.그리고 2원으로 나눠져야 하므로 5원을 가지고 짝수로 만들어야 함을 알 수 있다.따라서. n이 홀수일 때와 짝수일 때를 나누어 홀수면 5를 최대의 홀수번으로 나누고, 짝수면 5를 최대의 짝수번으로 나누고자 했다. *** 5미만이 들어오면 짝수일 때는 2로 나누어지지만, 홀수일 때는 낼 수 있는 방법이 없으니 -1을 출력해야한다.package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Day14_BOJ_14916_거스름돈..

https://www.acmicpc.net/problem/27961 이런문제는 결과값을 가지고 입력값을 만들어가는 경우를 생각해야 한다.그리고 그 과정에서 최소 연산을 할 수 있도록 해야하는데, 이 문제의 경우는 생성과 복제 중 복제이다.결과값에서 최대한 복제를 할 수 있는 한 하고 생성을 해서 입력값으로 만들어 가는 연산의 수를 구하면 된다.즉, 6일 때 -> 3(최대 2배로 복제) -> 2(최대 2배 이하로 복제할 경우) -> 1(최대 2배로 복제) -> 0(생성) => 4가 된다.이를 코드로 구현하면 아래와 같다.** 입력값이 0일 경우엔 무조건 0임을 고려해주어야 한다 package STUDY.Week02;import java.io.BufferedReader;import java.io.IOExce..

https://www.acmicpc.net/problem/1080A 배열을 차례대로 탐색하다가 B 배열과 다른 부분에서 3x3 만큼을 뒤집는다.종료후, B 배열과 동일한지 확인한다. (0, 0)부터 (n-1, m-1)범위의 값을 모두 비교하고 뒤집었는데, 제출하니 틀렸다.무조건 3x3 배열만큼을 뒤집어야 하기에 아래와 같이 설정해야 한다.또한, 배열 크기가 3미만이지만 A 배열과 B 배열이 애초에 동일한 경우에는 0으로 결과값이 나와야 한다.for(int i=0; i 1. A 배열과 B 배열과 동일하면 0 출력2. 입력 받은 배열의 크기가 3미만이면 -1 출력3. (0, 0) 부터 (n-3, m-3) 까지 탐색하며 B 배열과 다른 값을 찾으면 A배열의 해당 위치부터 3X3 만큼 뒤집는다. 4. A배열과 ..

https://www.acmicpc.net/problem/1138 처음엔 순서대로 주어진 위치만큼 앞에 자리를 남겨두고 저장하고, 기존 수와 비교하며 뒤로 밀고 넣으면 되겠다하고 구현 했다.하지만 그렇게 하니 예제 4에서 결과값이 6 2 3 4 5 7 1 이 나왔다.작은 키부터 넣으면 앞에 큰 키의 개수를 제대로 고려하지 못하는 것이었다. 그래서 큰 키부터 넣어야 된다는 것을 깨달았다.1. 큰 키서부터 주어진 위치만큼 앞에 남겨두고 위치시킨다.2. 만약 해당 자리에 값이 이미 들어있다면 해당 값은 무조건 더 큰 값이 있을 것이므로 뒤로 쭉 밀고, 지금 값을 자리에 위치시킨다.3. 그렇게 위치시킨 값을 출력하면 끝! package BOJ.Greedy;import java.io.BufferedReader;i..