profile
안녕하세요

프로그래머스 - level 1 이상한 문자 만들기

문제 https://programmers.co.kr/learn/courses/30/lessons/12930 풀이 문장 전체의 인덱스가 아니라, 문장에 포함된 단어별로 인덱스가 짝수인지 홀수인지 확인 해야 한다. flag = true이면 대문자를 소문자로 flag = false이면 소문자를 대문자로 ' '이면 새로운 문자가 시작되므로, ...

2019년 12월 2일
·
0개의 댓글

프로그래머스 - level 1 수박수박수박수?

문제 https://programmers.co.kr/learn/courses/30/lessons/12922 풀이 입력받은 n 의 길이만큼 패턴에 맞는 문자열을 return하면 된다. 패턴은 "수"(0),"박"(1) 이므로, 문자열의 길이만큼 0101을 출력하면된다. 문자열 길이가 3이라면, 010을 출력하면 "수박수" 가 출력된다. 코드

2019년 11월 30일
·
0개의 댓글

프로그래머스 - Level 1 체육복

문제 https://programmers.co.kr/learn/courses/30/lessons/42862 풀이 전체 학생의 체육복 정보를 담을 별도의 공간을 생성한다. 체육복이 있는 학생은 0, 여벌의 체육복이 있는 학생은 1, 체육복을 잃어버린 학생은 -1으로 표시한다. 체육복 여벌이 있다가 도난당하는 학생도 있다. 예를들어, reserve = {...

2019년 11월 24일
·
0개의 댓글

프로그래머스 - 완주하지 못한 선수

문제 https://programmers.co.kr/learn/courses/30/lessons/42576?language=cpp c++ STL 정리 c++의 vector자료형이 함수의 파라미터로 주어지기 때문에, vector자료형을 먼저 정리해 보겠다. vector > vector는 array와 비슷하지만, 크기가 정해지지 않은 Linked-Lis...

2019년 11월 20일
·
2개의 댓글

BOJ 13398 연속합 2

문제 image.png image.png 풀이 배열 중 한개를 버리는 경우와, 그렇지 않은 경우로 나눠진다. 2차원 배열로 dp 표현 dpn = n까지의 연속합, 버린 경우는 없다 dpn = n까지의 연속합, 1개를 버린 경우 버리지 않는 경우에는, dpn-1 + a[n]과 a[n]을 비교해서 큰 값을 선택하면 된다. 버리는 경우에는, n-1번째...

2019년 11월 19일
·
0개의 댓글

boj 15988 - 1,2,3 더하기 3

문제 image.png image.png 풀이 다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 점화식을 정의하면 아래와 같다. 문제에 주어진 예시를 풀어서 보면 아래처럼 나타나지고, 끝자리에 1이오는경우,2가오는경우,3이오는경우로 나눠지는것을 볼 수 있다. 점화식을 식으로 나타내면 아래와 같다. > dp[n] = dp[n-1] + dp[n...

2019년 11월 16일
·
0개의 댓글

BOJ 2225 합분해

문제 image.png image.png 풀이 문제를 통해서 점화식을 정의하면 아래와 같다. > dpn = n까지의 정수 k개를 더한 합이 n이 되는 경우의 수 코드

2019년 11월 16일
·
0개의 댓글

BOJ 9465 - 스티커

문제 풀이 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다. 아래와 같은 형태로 점수가 정해진 상태로 스티커가 붙어 있다. 이때, (50,50,100,60)인 스티커를 떼면 총합이 260으로 변을 공유하지 않고 최대값을 가지는 부분집합이 된다. dpn = n번째 열에서 스티커를 m했을 때, 2 x...

2019년 11월 8일
·
0개의 댓글

BOJ 11057 - 오르막수

문제 image.png image.png 풀이 오르막 수는, 수의 자리가 오름차순을 이루는 수를 의미한다. 앞자리와 같은 수도 오름차순으로 생각한다. n = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 dp1 = 1 n = 2 dp2 = 9 dp2 = 1 dp2 = 1 ...

2019년 11월 7일
·
0개의 댓글

BOJ 1309 - 동물원

문제 image.png image.png 풀이 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수 없다. (대각선으로만 배치 가능하다) 1번째 줄에 1번째 칸에 사자가 들어가 있으면, 2번째 줄에는 2번째 칸에 사자가 들어가야 한다. n = 1 인 경우 n = 2 인 경우 dpi = dpi-1 * 3 dpi = dpi-1 * 2 ...

2019년 11월 7일
·
0개의 댓글

BOJ 1149 - RGB 거리

문제 image.png 풀이 첫번째 집에서 최소비용이 드는 색을 선택한다. 그러면 두번째 집에서는 첫번째 집이 사용한 색을 제외한 것 중 최소비용이 드는 색을 선택하는 방식으로, 전체 집을 칠하는 최소 비용을 구할 수 있다. K = 0(빨강),1(초록),2(파랑)이라고 가정하면 아래와 같은 형태로 표현된다. 전체 집을 칠할때 드는 최소 비용을 구해...

2019년 11월 6일
·
0개의 댓글

BOJ 15988 - 1,2,3 더하기 3

문제 image.png image.png 코드

2019년 11월 6일
·
0개의 댓글

BOJ 1699 - 제곱수의 합

문제 image.png 풀이 먼저, 점화식을 정의하면 아래와 같다. > dp[n] = n 제곱수의 최소항 개수 가장 마지막에 ,i^2 왔으면 그 앞부분 까지의 합은 n - i^2이 된다. n-i^2의 제곱수로 표현할때 그 합이 최소인 개수에 i^2항 한개가 추가된 것 이다. > dp[i] = min(dp[i-n^2]) + 1 dp[i] = i로...

2019년 11월 4일
·
0개의 댓글

BOJ 1912 - 연속합

문제 image.png 풀이 dp[i] = i번째 수로 끝나는 가장 큰 연속합 이라는 점화식을 도출 했다. i 번째 수에게 가능한 경우를 세야한다. i-1번째 수의 연속합에 포함되는 경우 dp[i-1] + num[i] 새로운 연속합을 시작하는 경우 num[i] 현재 값과 현재값 이전 값 + 현재값을 중 더 큰 값을 dp에 채워 넣으면 된다. num...

2019년 11월 3일
·
0개의 댓글

boj 14002 가장 긴 증가하는 부분 수열 4

문제 image.png image.png 풀이  해당 문제는 가장 긴 증가하는 부분 수열 문제를 응용해서 해결 할 수 있다. 다만, 가장 긴 증가하는 부분 수열의 길이 이외에도 부분 수열을 출력해야 한다는 점에서 차이가 있다. v라는 배열을 생성한 후, v 에는 증가하는 부분 수열의 index 값을 저장 시킨다. 예를들어, 아래와 같은 형태...

2019년 11월 3일
·
0개의 댓글

BOJ 2193 - 이친수

문제 image.png image.png 풀이 이차원 다이나믹 프로그래밍 풀이 점화식을 다음과 같이 정의할 수 있다. > dpn = n 자리 이친수, 마지막 수 l 이친수가 되려면, 이진수 이면서 첫번째 자리에 0이 오면 안되고, 11을 부분 문자열로 가지면 안된다. dpn = n자리 이친수, 마지막 수 0 마지막에 0 이 왔으면 그 앞에...

2019년 11월 3일
·
0개의 댓글

BOJ 10844 - 쉬운 계단 수

문제 image.png image.png 풀이 문제를 통해 점화식을 정의하면 아래와 같다. >DPN = 길이가 N인 계단 수의 개수, 마지막 사용한 수 L 만약, 아래 그림처럼 전체 길이가 N, 마지막 수가 L 이면 길이가 N-1 마지막 수가 L-1 인 계단 수에 L이 마지막에 붙으면 계단 수 길이가 N-1 마지막 수가 L+1 인 계단 수에 L...

2019년 10월 30일
·
0개의 댓글

BOJ 11052 - 카드 구매하기

문제 image.png image.png image.png 풀이 문제를 통해서 점화식을 정의하면 아래와 같다. > n개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값 예를들어, 민규는 총 4장의 카드를 구매한다고 하자. 1장이 들어있는 팩의 가격은 1원 2장이 들어있는 팩의 가격은 5원 3장이 들어있는 팩의 가격은 6원 4장이 들어있는...

2019년 10월 26일
·
0개의 댓글

BOJ 9095 - 1,2,3 더하기

문제 image.png image.png 풀이 문제를 통해 점화식을 정의하면 아래와 같다. > 정수 n 을 1,2,3의 합으로 나타내는 방법의 수 예시를 통해서 점화식을 구체적으로 정의 해보겠다. 1 = 1 2 = 1+1, 2 3 = 1+1+1, 2+1, 1+2, 3 4 = 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 3+1, 1+3, ...

2019년 10월 26일
·
0개의 댓글

BOJ 11727 - 2*N 타일링 2

문제 image.png image.png 풀이 점화식을 정의하면 다음과 같다. > 2N 타일을 12,21,22 타일로 채우는 경우의 수 > dp[i] = dp[i-1] + dp[i-2] + dp[i-2] 코드

2019년 10월 24일
·
0개의 댓글