매일 조금씩

문제 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..

콘솔에 문자가 깨져서 출력된다. 1. Console Encoding 변경 File > Settings (Ctrl + Alt + S) Editor > General > Console에서 Default Encoding을 UTF-8로 변경해준다. 그래도 문제가 해결 되지 않았다. 2. idea64.exe.vmoptions 파일 수정 shift를 두번 눌러서 'Edit Custom VM Options...'을 Open한다. -Dfile.encoding=UTF-8 추가 후 저장한다. IntelliJ를 재시작 한 후 테스트 해보았다. 문자 깨짐 현상이 해결되었다.

문제 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..

문제 https://www.acmicpc.net/problem/21771 21771번: 가희야 거기서 자는 거 아니야 베게 중 8칸이 가희에 의해 가려졌으므로, 가희는 베게 위에서 자고 있습니다. www.acmicpc.net 풀이 베개의 넓이와 베개의 원소 개수를 비교해서 베개가 가려졌는지 여부를 판단한다. 소스코드 package dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ11057 { public static int R, C, GR, GC, PR, PC; public static void input() throws Exception{ ..

문제 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 그냥 이중 반복으로 구현해서 풀었다. 바깥쪽 반복문의 인덱스는 unit(자르는 단위의 개수)이다. 내부는 while문을 추가해서 인덱스를 unit만큼 증가시키면서 현재와 이전 문자열을 비교해서 count를 계산하였다. 소스코드(JAVA) import java.util.*; class Solution { public int solution(Str..