나의개발일지

https://www.acmicpc.net/problem/1932 아래층으로 내려갈 땐 지금 당장 값이 작아도 끝까지 도착했을 때의 값이 더 클 수 있다.그럼 반대로 생각해보면 된다!위층으로 올라갈 때 직전 값 중 큰 값을 누적해가면 dp[0][0]이 최댓값이 된다.for(int i=n-1; i>=0; i--){ for(int j=0; j package BOJ.DP;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_1932_정수삼각형 { public static void main(S..

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/17825우선 윷놀이 판을 2차원 배열에 담아주었다.총 10번의 말 이동 순서를 순열로 뽑은뒤, 해당 순서로 게임을 진행하도록 하였다.게임을 진행할 때에는 각 말들의 저장해두고 싶은 현 상황을 Point 구조체를 만들어 담아두며 사용했다.이때 가장 중요한 것은 25, 30, 35, 40에서의 방문 처리 였는데, 이미 말이 놓여있는 자리로 이동하는 말의 경우 사용하면 안된다는 조건이 까다로웠다.결과 적으로 아래와 같이 제출하였지만 조금 더 다듬어야 할 것 같다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util..

https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제의 핵심은 기간을 비교하면 되는 것이다.우선 약관종류에 따른 유효기간은 Map에 넣어 사용했고, 모든 비교를 일(days)로 바꿔 계산했다.  import java.util.*;class Solution { public int[] solution(String today, String[] terms, String[] privacies) { PriorityQueue pq = new PriorityQueue(); ..

https://school.programmers.co.kr/learn/courses/30/lessons/72410 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문자열이 이렇게 어려웠던가.. 주어진 단계를 그대로 구현해내면 되는 문제였는데,풀고나서 다른 풀이를 보니 정규표현식을 사용하면 좀 더 깔끔하게 풀 수 있는 단계가 많았다.조만간 정규표현식을 따로 함 정리해야 할 듯.. class Solution { public String solution(String new_id) { String answer = ""; // 1. 대문자 -> 소문자 an..

https://www.acmicpc.net/problem/11054 결국은 가장 긴 오름차순 수열과 가장 긴 내림차순 수열.근데 이제 오름차순의 끝나는 수와 내림차순의 시작하는 수가 동일할 때의 최대 길이를 구하는 문제이다.1. 가장 긴 증가하는 부분 수열을 찾아 dpUp배열에 저장한다.2. 가장 긴 감소하는 부분 수열을 찾아 dpDown배열에 저장한다. (이때 배열의 끝부터 역으로 오름차순 탐색했다.)3. 각 위치에서 dpUp + dpDown - 1 (현재 위치 수 중복) 을 계산하며 최댓값을 갱신한다. package Study.Week05;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;i..

https://www.acmicpc.net/source/86922116 알고리즘의 난이도가 올라가면 더 이상 알고리즘 난이도의 문제가 아닌 아이디어의 문제임을 알려주는 대표적인 유형의 문제. 별의별 생각을 다 해보며 규칙을 찾아봤는데 결국은 하나였다. 오름차순으로 만들어야 한다는 것.오름차순으로 만들기 위해 옮겨지는 아이의 최소 수는? 이미 오름차순인 번호를 제외하고, 나머지 번호를 옮겨주면 된다.즉, (총 학생 수 - 가장 긴 증가하는 부분 수열) 인 것이다~!가장 긴 증가하는 부분 수열은 이전에 넘 많이 글을 올렸어서 링크로 첨부하겠당.https://dev-zsunny.tistory.com/65 99클럽 코테 스터디 30일차 TIL DP(상자넣기)https://www.acmicpc.net/proble..

https://www.acmicpc.net/problem/12852 우선 N의 범위가 최대 백만이기에, 각 3가지 경우를 모두 메모이제이션 하는 것은 불가능했다.그렇다면 최대 1차원 배열을 사용해야 한다는 것인데, 규칙이 뭘까? 하고 dp 배열을 그려봤다.예제 2를 대입해서 배열의 값으로는 연산 횟수를 저장하고자 할 때,이전 값에서 * 3, * 2, + 1 을 해서 현재 값이 되는 수의 배열 값 + 1(1회 연산) 을 한 것들 중 최솟값을 저장 하면 되겠다 싶었다.그래서 처음에 아래와 같이 작성하여 제출했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { ..

https://www.acmicpc.net/problem/1965문제 읽으면서 든 생각. 어라..? 이거 그냥 가장 긴 증가하는 부분수열 아닝가..?https://www.acmicpc.net/problem/11053 (백준 11053 가장 긴 증가하는 부분 수열) 크기가 더 큰 상자에 크기가 더 작은 상자를 넣을 수 있고, 이렇게 넣을 수 있는 최대 상자의 개수를 구하는 문제.결국은 오름차순을 가지는 수열의 개수를 구하면 되는 문제이다.예제를 살펴보면 1 6 2 5 7 3 5 6 -> 1, 2, 3, 5, 6 으로 총 5개가 답이 된다.순차적으로 배열을 탐색하며 현재 값보다 인덱스가 작은(이전에 위치한) 값들을 보며 현재 값보다 작으면 해당 인덱스 dp에 + 1 씩 하며 최댓값을 갱신해준다.  packa..

https://www.acmicpc.net/problem/9461 처음에 이해가 잘 안돼서 P(N)을 쭉 써보다가 규칙을 찾았다. P(1) = 1,P(2) = 1,P(3) = 2,P(4) = 2,P(5) = 2,P(6) = P(3) + P(5) = 3,P(7) = P(2) + P(6) = 4,P(8) = P(1) + P(7) = 5,P(9) = P(4) + P(8) = 7,P(10) = P(5) + P(9) = 9,P(11) = P(6) + P(10) = 12,P(12) = P(7) + P(11) = 16 작성하다보니 슬슬 규칙이 보이기 시작했다.혹시 몰라서 문제의 그림을 보며 머릿속으로 그려봤는데 한바퀴를 돌 때까지 규칙이 일정하다는 것을 확인했다.P(1) ~ P(8) 이후부터는 P(N) = P(N-5..