나의개발일지

https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  사용 알고리즘트라이 아이디어1. 단어 길이별 정방향/역방향 트라이 생성2. pro??? 형식으로 들어오면 해당 길이의 정방향 트라이 탐색해서 와일드카드 '?' 전 노드가 가지는 단어 수 ㅈ장3. ???pro 형식으로 들어오면 해당 길이의 opr??? 로 변경한 후 역방향 트라이 탐색해서 와일드카드 '?' 전 노드가 가지는 단어 수 저장 유의점- 쿼리가 모두 ? 로 이루어져 있을 때(ex.[?????]) 해당 길이를 가지는 트라이의 루트 노드가..

https://www.acmicpc.net/problem/11657 사용 알고리즘벨만-포드 아이디어1. 노드가 n개 일때 간선은 n-1개2. n-1번 돌면서 최단거리 계산3. n번째에서 최단거리가 변경되면 음의 싸이클 -> return true; 유의점거리를 계산하는 dist[] 배열 : int 값 범위 넘음 (언더플로우) -> long 형 제출코드package BOJ.Graph.BellmanFord;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ_11657_타임머신 { static class Point{ int..

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/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..

https://www.acmicpc.net/problem/11055 어제와 비슷한 유형의 문제이다.문제에서 구해야 하는 값을 dp배열에 저장하는 값으로 설정하고, 그 규칙을 하나씩 찾아봤다.dp[0] 은 무조건 배열의 값일것이고, 그 뒤는 현재 값의 앞에 있는 값들을 탐색하면서 현재 값보다 작은 값이 있으면 그 값에 현재 값을 더한다.그리고 이런 값들을 Math.max를 통해 최댓값으로 갱신하며 구하면 끝!(자세한 건 아래 주석 참고)** 참 저 ans 때문에 98%에서 또 틀렸는데, ans를 자꾸 습관적으로 0으로 초기화해서 1 1을 넣었을 때 0이 나왔다(반목문 안돌아서)ans 초기화도 생각을 잘 해서 초기화하자.. 여기선 dp[0]으로.. package Study.Week04;/*1 : dp[0] ..