일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 27 |
28 | 29 | 30 |
- 막내의막무가내 플러터
- 주택가 잠실새내
- 막내의막무가내 rxjava
- 막내의막무가내
- 2022년 6월 일상
- 부스트코스
- 주엽역 생활맥주
- flutter network call
- 막내의 막무가내 알고리즘
- 안드로이드 sunflower
- 안드로이드 Sunflower 스터디
- 막내의막무가내 안드로이드
- 안드로이드
- 막내의 막무가내
- 막내의막무가내 프로그래밍
- 막내의막무가내 안드로이드 에러 해결
- Fragment
- 막내의막무가내 일상
- 막무가내
- 막내의막무가내 SQL
- 막내의막무가내 코틀린
- 프래그먼트
- 프로그래머스 알고리즘
- 막내의막무가내 코틀린 안드로이드
- 막내의막무가내 플러터 flutter
- 막내의막무가내 코볼 COBOL
- 막내의막무가내 알고리즘
- 막내의막무가내 안드로이드 코틀린
- 막내의막무가내 목표 및 회고
- 부스트코스에이스
- Today
- Total
목록알고리즘/DP (20)
막내의 막무가내 프로그래밍 & 일상
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 1463 1로 만들기 문제에 이어 동적계획법 다음단계인 쉬운계단수를 풀어봤습니다. 이전 문제보다 바로 2차원 배열로 접근해서 쉽게 풀수 있었습니다. 그리고 주의해야할점이 문제에 나와있는것처럼 %1000000000 을 해줘야합니다. 위와 같이 먼저 dp 정의를 세우고 dp[자릿수][오는숫자] = 경우의수; dp 문제의 경우 대부분 초기 값을 몇개 세팅해주고 풉니다. 위 그림은 두자리(N=2) 의 예시인데 앞자리는 0이 못오고 1~9가 올 수 있음을 알 수 있습니다. 그러므로 초깃값을 0빼고 다음과 같이 해줍..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 처음 2차원 배열로 접근 했다가 삽질했습니다. import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[N + 1]; // 인덱스 : 숫자, 값 : 최솟값 dp[0] = 0; dp[1] = 0; for (int i = 2; i
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 백준 계단 오르기 dp 문제를 풀어봤습니다. ㅎㅎ DP 가 아주 조금은 감이 오는 것 같습니다. 문제의 포인트는 한칸 이동과 두칸 이동이 있는데 연속으로 ..
RGB 문제에 이어서 dp 다음 단계 문제를 풀어봤습니다. 둘 다 dp 문제이므로 성향은 비슷합니다. 과거의 값을 이용해 최대가 되는 값을 알아내가는 문제입니다. 삼각형 특성 상 왼쪽 구석과 오른쪽 구석은 이전 N-1 줄을 더할 때 한가지 경우의 수밖에 없다는 점과 그 외 가운데 값들은 두가지 경우중 큰 값을 더해줘야 한다는 로직이 필요합니다. 주석에 설명을 적어놓았습니다. ㅎㅎ 풀이는 다음과 같습니다. import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 삼각형 높이 int[][] num = new int..
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 첫 dp(다이나믹 프로그래밍 또는 동적계획법) 문제를 풀어봤습니다. 단계별 풀기에서 풀었는데 이전단계들을 생략하고 이 문제부터 풀었네요 ㅎㅎ 먼저 DP의 개념은 다음과 같습니다. Dynamic Programming; DP 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 조금 장난스럽게 ..