매일 조금씩

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 S지점에서 X라는 지점에 도착해서 X->A, X->B 로 갈라진다. 즉,..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 기준 숫자에서 왼쪽과 오른쪽을 나눈다. left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수 right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수 left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문) 차례대로 index를 증가 또는 감소 시키면서 채워나..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제가 제일 어렵다. DP문제는 사고의 전환이 필요하다. 나한테 너무 어려운 부분... 어쨌든 해당 문제는 구글링을 통해 힌트를 조금 얻어서 풀었다. dp[i][j] = i자리수에서 j로 끝나는 계단수의 개수 N(자리수)가 1일 때 1, 2, 3, 4, 5, 6, 7, 8, 9 dp[1][0] = 0 dp[1][1] = 1, dp[1][2] = 1 ... dp[1][8] =1 dp[1][9] = 1 N이 2일 때 10 / dp[2][0] = 1 21 / dp[2][1] = 1 12, 32, / d..

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 DP를 이용하여 풀었다. 작은 문제들의 답을 구한다. dp[2] = 1, N이 2일 때는 최소 횟수가 1이다. (2으로 나눔) dp[3] = 1, N이 3일 때는 최소 횟수가 1이다 (3으로 나눔) ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12914# 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이 완전 탐색으로 풀면 시간 초과가 발생한다. 가만 보니 2 x n 타일링 문제와 동일하다. 아래 문제에서 세로 타일 한개를 1칸, 가로타일 두 개를 2칸으로 해당 문제에 대입할 수 있다. DP문제로 점화식을 이용해서 풀 수 있다. 2021.10.29 - [Alogirthm/Programmers]..

문제 https://programmers.co.kr/learn/courses/30/lessons/43238# 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이 이분탐색을 이용해서 풀어야 하는 문제이다. 결과 값이 크기 때문에 타입에 유의해야 한다. 아래와 같이 초기화 한다. 심사의 최대 시간 = 최소 심사시간 * n 심사의 최소 시간 = 최소 심사시간 그리고 이분탐색을 진행한다. mid값을 총 걸리는 시간이라고 가정한다면, mid값/심사시간 = 해당 심사관이 심사하는 사람의 수가 된다. 그리고 모든 심사관의..

문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 풀이 DP 방식으로 풀 수 있다. 코드는 정말 간단한데 점화식을 세우는 게 쉽지 않다. 타일이 가로로 끝나는 것과 세로로 끝나는 것을 분류해보면 아래와 같다. 가로길이가 i일 때, 타일링의 경우의 수는 = i-1의 경우의 수와 i-2의 경우의 수를 합한 것이다. i-1의 경우의 수에서 세로 타일을 붙임 i-2의 경우의 수에서 가로 타일을 붙임 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 Level3 이지만 체감 난이도는 Level1 느낌이다. 1. 모든 work를 최대힙에 담는다. 2. 야근 시간만큼 순회하면서 최대값을 가지는 원소를 poll하여 -1 한후 다시 offer하였다. 3. 이후 queue에 남은 원소를 제곱하여 합계를 내었다. 소스코드 import java.util.*; import java.lang.*; ..

문제 https://programmers.co.kr/learn/courses/30/lessons/17676# = time-1000+1 && req 0) return 1; else if(o1 - o2 < 0) return -1; else return 0; } }); SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS"); for(int i = 0; i < lines.length; i++){ // Time으로 변환해서 첫시간, 끝시간을 PriorityQueue에 담아준다. // 그리고 두 시간을 가지는 Process를 생성해준다. String s = lines[i]; String date = s.substring(0, 23); long m..