막내의 막무가내 프로그래밍 & 일상

https://programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 오랜만에 프로그래머스 알고리즘 LV2 간단한 문제를 풀어봤습니다. ㅎㅎ 처음에 재귀로 풀었으나 시간초과가 나서 DP식으로 풀었습니다. 학창시절 프로그래밍언어개론 과목 첫 과제중 하나가 이거..

www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 백준 dp 유형의 2×n 타일링 2 문제를 풀어봤습니다. ㅎㅎ 이전에 풀었던 문제의 연장선 같은 문제였습니다. youngest-programming.tistory.com/446 [알고리즘] 백준 11726 2xn 타일링 -dp- 자바 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직..

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 백준 DP 유형의 문제를 풀어봤습니다. DP 유형은 이번년도에는 처음 푼 것 같네요.. 역시 생각하는거나 규칙성을 찾는게 어려운 것 같습니다. ㅠ_ㅠ 1,2,3 으로 해당 숫자를 만들 수 있는 경우의 수를 찾는 문제 입니다. 1,2,3 의 덧셈으로 이루어진 경우의 수 이므로 1 일때 경우의 수 (1) - 1가지 2 일때 경우의 수 (1+1, 2) - 2가지 3 일때 경우의 수 (1+1+1, 1+2, 3) - 4가지 4 일때 경우의 수 (1+1의 총케이스, 2+2의 총케이스, 3+3의 총케이스) - 7가지 로 ..

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 프로그래머스 LV3 동적계획법(DP) 문제 등굣길을 풀어봤습니다. 집에서 학교까지 웅덩이를 피해 갈 수 있는 모든 최단 경로의 수를 구하면 되는 문제였습니다. 집은 1,1 학교는 n,m 에 있고 최단 거리만 계산하면 되므로 상하좌우가 아닌 우측과 하단으로 이동만 하면 됩니다. row와 col 인덱스로 이루어진 이중 배열을 만들고 값으로는 해당 지점까지 오는데까지의 ..

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 백준 11726 2xn 타일링 문제입니다. dp 문제인데 그려보니까 간단한 점화식이였습니다. ㅎㅎ dp[n] = dp[n-1] + dp[n-2] 그려보면 바로 풀리는 문제였습니다. n=1 일 때 처리만 조심..! 여기서 인덱스아웃에러 떴었습니다. 풀이는 다음과 같습니다 [Java] import java.util.Scanner; class Main { public static void main(String[] args) { Scann..

www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 처음 완전탐색으로 접근했다가 삽질만 했습니다. 제출 시 60초가 걸리는 테스트케이스와 100,000개의 n 때문에 완전탐색으로 푼다고 해도 시간초과가 날 것 같당.. 이후 서칭 후 DP 문제인 것을 알고 dp로 풀었습니다. 다음 그림으로 점화식을 세우면 됩니다. [Java] import java.util.Scanner; class Main { public static void main(String[]..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net import java.util.Scanner; class Main { static int[][] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { int num = sc.nextInt(); if (num == 0) { System.out.println("1 0"); continue; } if (num == 1) { Sy..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 백준 단계별풀기 동적계획법2 의 동전1 문제입니다. 동전 1원, 2원, 5원의 모든 경우의 수를 dp에 축적해줍니다. 바텀업방식 주석에 풀이를 써놨습니다. [Java] import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.ne..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 백준 동적계획법1 단계별 풀기 마지막 문제인 평범한 배낭 문제를 풀어보았습니다 ㅎㅎ 풀다가 도저히 모르겠어서 아래 사이트를 참고해서 풀이했습니다. (설명도 매우 잘되어있었습니다.!) https://fbtmdwhd33.tistory.com/60 [백준,BOJ 12865] 평범한 배낭(JAVA 구현) -내 생각 이 문제의 경우 혼자 풀..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 동적계획법1 (dp) 단계별 풀기에 있는 연속합 문제를 풀어봤습니다. ㅎㅎ [입력 단계] dp[] 에는 해당 인덱스까지의 최댓값을 담도록 합니다. arr[] 에는 입력 숫자를 받습니다. [반복문 단계] 현재 인덱스까지의 연속된 합과(dp[i-1] + arr[i]) 현재 값을(arr[i]) 비교합니다. 현재 인덱스보다 지금까지의 연속합이 더 작으면 최대값dp를 바꿔주도록 하고 아니면 현재인덱스까지의 연속..

https://programmers.co.kr/learn/courses/30/lessons/12913?language=java 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 프로그래멋 LEVEL2의 땅따먹기 문제를 풀어봤습니다 ㅎㅎ dp 로 바로 접근하고 복잡한 문제가 아니라 빠르게 풀 수 있었습니다. 풀이는 다음과 같습니다. [Java] class Solution { int solution(int[][] land) { int answer = 0; for (int i = 1; i < ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS란 Longest Common Subsequence 로 최장 부분 수열을 말합니다. 이전 dp 문제들에서도 부분 수열문제들을 풀었었는데 이번 문제는 하나의 문자열 또는 집합이 아닌 두개의 문자열 비교까지 했어야 했습니다. 풀다가 모르겠어서 다음 사이트를 참고하였습니다. https://jaesungbong.tistory.com/21 백준 온라인 저지..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 백준의 가장 긴 바이토닉 부분 수열 문제를 풀어봤습니다. 동적계획법1 의 단계별문제이며 이전에 풀었던 문제에서 조금씩 응용을 하며 풀고 있습니다. 이 문제도 한가지의 케이스를 더 생각하고 응용하면 풀리는 문제였습니다. 이전문제는 다음 포스팅에서 참고합니다. https://youngest-programming.tistory.com/265 [알고리즘] 백준 2156 포도주 시식 -dp- https://www.acmicp..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net https://youngest-programming.tistory.com/265 [알고리즘] 백준 2156 포도주 시식 -dp- https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 백준 동적계획법1 단계별 풀기 포도주 시식 문제를 풀어봤습니다. dp[] 에 n개의 포도주 최대양을 저장, wine[] 에 n 번 째..