오늘은 여기까지

https://www.acmicpc.net/problem/9095 개념: dp 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.  풀이N = 4일때를 예시로 보면, `dp[N] = dp[N-1] + dp[N-2] + dp[N-3]`으로 나타낼 수 있음을 알 수 있다.3+1, 2+1+1, 1+2+1, 1+1+1+12+2, 1+1+2..

https://www.acmicpc.net/problem/1463 개념: dp, bfs 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.  1. dp로 푼 풀이주어진 예시로 생각해보면 `dp[10] = min(dp[3] + 1, dp[5] + 1, dp[9] + 1)`이다.d[n]을 구하고자 할때 n-1은 항상 가능하므로 dp[n] = dp[n-1] + 1을 구한다. 그리고 n이 3으로..

https://www.acmicpc.net/problem/1541 개념: 그리디 문제세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력첫째 줄에 정답을 출력한다. 예시55-50+40>> 55-..

https://www.acmicpc.net/problem/1931 개념: 그리디 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작..

https://www.acmicpc.net/problem/18230 개념: 그리디 접근N이 홀수라면 2x1 타일 하나를 우선 선택한다.N/2번 동안 for문을 돌면서2x2 타일 1개 vs 2x1 타일 2개 값을 비교한다. 값이 더 큰 경우를 선택한다. 전체코드import java.util.*;import java.io.*;public class Main{ static int N, A, B; static ArrayList twoByOne; static ArrayList twoByTwo; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade..

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  접근방법 1. 코스의 요리 개수를 기준으로 가능한 조합을 구한다.2. 주문내역을 돌면서 가능한 조합을 구한다.3. 각 조합의 주문 횟수를 센다.4. 가장 많이 주문된 조합을 정답에 추가한다. 2개의 요리로 만들 수 있는 조합을 구하기로 한다.    - 주문내역에서 2개를 선택한 조합을 구한다.    - 각 조합이 몇 번 주문됐는지 센다.    - 최대 주문 횟수만큼 주문된 조합을 정답에 추가한다. 3개의 요리로 만들 수 있는 조합을 구한다. ..

https://school.programmers.co.kr/learn/courses/30/lessons/92334 사용개념: 해시 import java.util.*;class Solution { public int[] solution(String[] id_list, String[] report, int k) { ArrayList answer = new ArrayList(); HashMap reported = new HashMap(); // 유저별 신고 당한 횟수 HashMap> reportByUser = new HashMap(); // 유저별 신고한 id 저장 for (String id : id_list) { rep..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사용개념: 해시  1. 노래 정보를 하나의 객체로 관리한다.class Song { int id; int plays; Song(int id, int plays) { this.id = id; this.plays = plays; }}  2. 데이터 정리장르별 총 재생횟수를 저장할 맵 하나, 장르별 노래 정보 (고유번호, 재생횟수) 저장할 맵 하나가 필요하다.전체를 순회하면서 데이터를 정리한다.Hash..

https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해시 연습문제~ 해시맵 하나에는 원래 구매 품목이랑 개수 정보를 담고, 다른 하나는 탐색하면서 개수 조절하는 용도이다.  전체코드import java.util.*;class Solution { public int solution(String[] want, int[] number, String[] discount) { int answer = 0; HashMap map = new HashMap(); fo..

https://www.acmicpc.net/problem/1238 사용개념: 다익스트라  문제 설명 1. N명의 학생이 각자의 마을에서 X번 마을로 가는 최단 시간2. 파티가 끝난 후 다시 자신의 마을로 돌아가는 최단 시간3. 이 왕복 시간이 가장 오래 걸리는 학생의 소요시간을 찾는 것 풀이 1. 다익스트라를 2번 사용한다X로 가는 최단 시간 (마을 → X)되돌아가는 최단 시간 (X → 마을)2. 정방향 그래프, 역방향 그래프 활용정방향 그래프로 각 정점에서 X까지 최단 시간을 구한다역방향 그래프로 X에서 각 정점까지 최단 시간 구한다3. 마지막으로 각 학생별로 두 거리의 합을 구한 뒤 최댓값을 찾는다 전체코드import java.io.*;import java.util.*;public class Main..