https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 : dp를 베이스로 하는 완전 탐색 문제 풀이 : 숫자 n개를 이용해 만들기 위해선, 숫자 n-1개로 만든 수들을 이용해야 한다. 유의점 : N=4, number = 17 인 경우 -> 17 = (4*4) + (4/4) 이 경우는, 4를 4개를 이용해 17을 만들었는데, 4를 3개 이용한 조합에서 사칙연산한 것이 아니라, 4를 2개 이용한 숫자(= 4*4)와 4를 2개 이용한 숫자(= ..
https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스에서 dp 문제 풀었다. 그런데 왠걸,, 백준에서 이미 비슷한 문제를 풀어본 적이 있었기에 금방 풀었다 ㅎㅎ level 3의 다른 카테고리 문제들보면 좀 까다로운 경우가 많은데, 아무래도 dp인지라 기본적으로 level이 좀 높게 잡히는 것 같다. 그래도 이 문제는 크게 어려운 점화식도 아니니 찬찬히 코드 보면서 손으로 따라가면 금방 이해하실 수 있을 것 같다. def solution(..
처음으로 릿코드 문제를 풀어보았다. 어떤 정수 배열이 주어졌을 때, 이 배열을 '합이 동일한 2개의 부분 집합으로 나눌 수 있는지' 를 판단하는 문제였다. dp를 이용해 풀었다. 아래 알고리즘은 직접 손으로 따라가며 풀면 금방 이해할 수 있을만한 코드이다. TIP! 배열의 합이 22일 때, 배열에 속한 몇가지의 수를 선택해 배열의 합의 절반인 11을 만들 수 있으면 자연스레 선택받지 못한 나머지 수들의 합도 11이 된다. (배열의 합이 짝수인 경우만 2개의 부분 집합으로 나눌 수 있기 때문!) 혹시 이런 문제가 백준에도 있다면 댓글 남겨주세요,, class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if tot..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net dp문제는 왜인지 항상 블로그에 글을 쓰고 싶게 만든다. 처음 이 문제를 보면, 점화식을 만드는 규칙이 한 눈에 보이지 않아 무척 당황스러울 것이다. 하지만 연습장 하나 꺼내서 차근차근 손으로 계산하다보면 어떤 규칙이 눈에 띌 것이다 ! 그 규칙은 바로 삼각형이 정삼각형, 역삼각형 꼴을 반복하는 것이고, n번째 삼각형의 변의 길이 = 바로 직전의 삼각형의 변의 길이 + 직전 삼각형을 만드는데 쓰였던 삼..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각보다 까다로웠던 dp 문제이다. (사실 dp문제는 다 까다롭지만,,) dp[1], dp[2], dp[3]까지는 손쉽게 생각할 수 있다. dp[i]가 의미하는 바는 i번째 와인까지 마셨을 때 최대로 마실 수 있는 와인의 양이다. 1. 전전 와인 먹지 않고 전 와인과, 현재 와인 마시기 + 전전전 와인까지의 최댓값 2. 전 와인 먹지 않고 현재 와인 마시기 + 전전 와인까지의 최댓값 3. 전 와인까..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 중복조합 또는 dp로 해결가능한 문제인데, dp로 풀어보았다. 우선, k가 1일 경우엔 n으로 어떤 수가 와도 경우의 수는 1이다. 그러나 n이 1일 경우, 경우의 수는 k값을 따라간다. dp 테이블 k = 1 k = 2 k = 3 n = 1 1 2 3 n = 2 1 3 n = 3 1 n = 4 1 n = 5 1 이제 위 dp 테이블을 채워나가면 된다. n=2이고 k=2일 때 가능한 경우는 0+2, 2+0, 1+1 총 3가지 이다. 이는 (2,1)의 경우인 2와 (1,2)의 경우인 0+1, 1+0를 합한 것이라고 볼 수 있..
