다이나믹프로그래밍 알고리즘,PS/백준 2023. 10. 6. [BOJ] 백준 [15486] 퇴사 2 JAVA https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 📝문제 📝풀이 하루씩 순차적으로 진행하면서 특정 일의 상담을 진행하고 나서 받는 총 합 이익을 갱신 시켜주면 된다. 특정일을 i 상담 걸리는 시간을 A(i) 페이를 P(i) 페이 총합을 S(i) 라고 했을 때 점화식은 S(i + A(i)) = max( S(i + A(i)), S(i)+P(i) ) 가 된다. 추가로) i 의 범위는 i 번째 상담을 끝 났을 때 i+1 일.. 알고리즘,PS/백준 2022. 5. 11. [BOJ] 백준 [10844] 쉬운계단수JAVA https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝문제 📝풀이 DP 를 활용한 문제이다. 우선 1~9 까지는 한자리 수 니깐 1 이다. 여기서 2번째 자리수는 다음과 같은 상황이 나온다. 0 + ? 1 + ? 2 + ? 3 + ? 4 + ? ... 9 + ? 여기서 ? 에 올 숫자는 이전 숫자보다 +1 또는 -1 이다. 그런데, 예외가 있다. 만약 9 가 나왔다면 다음은 무조건 8만 나와야 한다. ( 98 ) 그리고 0 이라면 이전은 다음건 1만 나와야 한다. 예를들어 10 ? 이 경우엔 다음수는 1만 가능 => 101 그럼 끝자리 경우 자체가 결정자가 될수.. 알고리즘,PS/프로그래머스 2021. 11. 27. [프로그래머스] [Level3] 등굣길 JAVA https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 (1,1) 집에서 (m,n)학교 까지 가는데 최단거리로 가는 경우의 수를 구하는 문제이다. 우선 , 문제의 조건으로 오른쪽or아래 만 진행한다고 하였으니 어디로 가든 최단거리는 기본으로 잡고 들어간다. 만약 현지위치를 (x,y) 라고 하면 이 위치에 오기 까지의 경우의수는 (x-1,y) 또는 (x,y-1)의 합이다. 즉 , 현재위치의 경우의.. 알고리즘,PS/백준 2021. 9. 29. [BOJ] 백준 [9252] LCS 2 JAVA https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 두 문자열(arr1,arr2) 을 문자 하나하나 비교하는것에서 시작을 해야한다. ( arr1 를 i 로 순차탐색 ) ( arr2 를 j 로 순차탐색) 차례대로 (i, j)비교하다가 만약 문자 하나가 같은경우 => arr1[i] == arr2[j] 일 경우 카운트를 증가시킨다. 이것을 끝날때 까지 진행하면 된다. 하지만 이대로하면 중복되는부.. 알고리즘,PS/백준 2021. 9. 28. [BOJ] 백준 [1005] ACM Craft JAVA https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [문제] [풀이] 위와 같이 task 를 수행하는 순서가 있는 경우엔 위상정렬로 접근해야 한다. 이 문제에선 건물을 짓는데 있어서 선행조건이 존재하므로 위상정렬을 이용하여 inDegree 를 하나씩 낮춰가면서 진행. A,B 라는 건물을 지어야만 C를 지을수 있을 때 A와 B 건물중에서 더 오래걸리는 건물 기준으로 C까지 짓는데 걸리는 시간이 정해진다. 건물 n을 짓는데 걸리는 시간을 time.. 알고리즘,PS/백준 2021. 9. 14. [BOJ] 백준 [1463,12852] 1로 만들기 1,2 JAVA https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 만약 구하고 싶은 수를 i 라고 하면 , min( dp[i/2]+1 , dp[i/3]+1 , dp[i-1]+1 ) 이라는 최적해를 구해서 하면된다. 연산 순서에 따라 완전 다른 횟수가 나올 수 있기 때문에 그리디로 접근하면 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.*; import java.io.*; public class Main{ public static void main(Strin.. 이전 1 다음 LIST
![[BOJ] 백준 [15486] 퇴사 2 JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bN0MV0/btsyerRVJhp/kPvls814wUCJPdN6uHFWKk/img.png)
![[BOJ] 백준 [10844] 쉬운계단수JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/GDmFk/btrBMEG8wY5/IX1zDZ7DKqoJvzRmN95VtK/img.png)
![[프로그래머스] [Level3] 등굣길 JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/A6nhK/btrmiFt3Wq9/pwg1ibIQwUeIwCETvYctdK/img.png)
![[BOJ] 백준 [9252] LCS 2 JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/le0zE/btrgobrHeL8/3NzGbN9WHULFNHNCAnQjK0/img.png)
![[BOJ] 백준 [1005] ACM Craft JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bKKTYO/btrgbKJdWMK/MmZKTvpKLKFh9d9kDDkZcK/img.png)
![[BOJ] 백준 [1463,12852] 1로 만들기 1,2 JAVA](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/mqDJq/btreZ1Y17fA/bKq9ESuqq4yp2hV2OKku1K/img.png)