꾸준하게 거북이처럼

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n이 100 이하라 완전탐색을 해도(O(n^2)) 괜찮다. 하지만 입력 크기가 커지게 되면 어떻게 풀어야할까 어딘가에 개수를 저장해서, 전체 개수인 n개에서 빼면 다른 트리 개수가 나올 것 같다. dp구나! 생각이 들었고, 프로그래머스에서 풀이를 찾아봤다. 자식에서 부모로 올라가면서 개수를 증가시켜나가는 방식이다. 그러면 O(n) 방식으로 풀 수 있다. function solution(n, wires) { const g = Array(n + 1) .fill() .map((e) => Array()); for (..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 n이 홀수일 때는 1x2, 2x1로 3xn 모양의 타일을 만들 수 없다. 짝수 일 때의 경우를 그려보면 위와 같은데, n이 4부터는 이전의 타일( d[2]와 d[2]를 가지고 만듦)을 이용해서 만드는 것뿐만 아니라 좀 새로운 모양의 타일이 2개씩 생긴다. n이 6일 때는 dp[4] * dp[2] + dp[2] * dp[4]의 새로운 모양타일 2개 + dp[6]에서 만들어진 새로운 모양 타일 2개 .... dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + ..... + dp[0] * 2 와 같은 점화식을 구할 수 있다. 코드 dp = [0] * 3..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 관련된 문제로 연속합 문제가 있는데, 이번에는 연속합2 이다. dp는 역시, 이전의 값을 참조해서 답을 찾아나가는 과정! 경우의 수를 잘 나누는 것이 진짜 중요하다. => 점화식 빠르게 찾는 지름길* 10만이 입력이라서, 2차원 배열은 포기해야겠네 생각했었다. 하지만 그렇다고 해서 2차원 배열을 바로 포기해서는 안된다. 내가 어떻게 써먹는지에 따라 시간적 효율성은 달라지기 때문. 풀이 이 문제는 두 가지의 경우의 수로 나눌 수 있다. 이 힌트만으로도 문제 풀이가 금방..

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 부분 수열 문제를 풀어봤다면, 이 두 가지 힌트로 문제풀이를 쉽게 떠올릴 수 있을 것이다. 1. 주어진 수열 arr[i] 까지의 가장 긴 증가 수열의 길이를 담은 increase[i] 사용 2. i 부터 n까지 가장 긴 감소 수열의 길이를 담은 decrease[i] 사용 => **reverse를 이용한다. 주어진 수열: 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 increase[i] - 증가하는 수열 길이: 1, 2, 2, 1, 3, 3, 4, 5, 2, 1 dec..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 현재의 값보다 작은 수들 중 가장 dp 값이 큰 것을 더하여 dp값을 업데이트 하고 max(dp)를 구한다. 코드 n = int(input()) arr = list(map(int, input().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, n): big = 0 for j in range(i): if arr[j] < arr[i] and big < ..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 아직 백준에서만 dp문제를 접했지만, dp 문제는 항상 이전의 값을 참고하여 문제에서 주어진 조건을 차례대로 충족해나가는 문제인 것 같다. 예를 들어, 1 ~ n 까지의 어떤 배열이 있고 + 문제에서 구하고자 하는 것과 주어진 조건 + 최댓값 구하기 문제라면, 1, 2, 3, 4,,, 까지 일 때의 최댓값을 축적해나가는 것이다. 그래서 마지막 n번째 배열에는 최종 최댓값을 구할 수 있는 것. 축적해 나가는 i 까지의 최댓값 후보는 여러개인 경우가 많고 max를 구..

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net n = 1 : 3가지 n = 2 : 7가지 n = 3: 17가지 .,, 어떤 규칙이 있을까 아무리 생각해도 떠오르지 않았다. 기준을 무엇으로 두어야할까? 가 문제였다. dp는 전의 결과를 참고하는 과정에서 차곡차곡 답이 쌓인다. 이걸 꼭 명심하자. 2x1 타일을 새로 추가할 때 그 때 2x1 타일을 기준으로 총 3가지의 경우로 분류할 수 있다. 1. 아무것도 선택 안할 때 2. 왼쪽 타일 선택 3. 오른쪽 타일 선택 - 아무것도 선택 안하는 경우 (dp[i][0]이라 하자) dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] - 왼쪽 타일을 선택하는 경우 (dp..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번달까지는 dp만 풀 것 같다. 오늘은 가야할 곳이 있어서 바쁜 나머지,, 잠도 요즘 덜자고? 맘도 급했고 문제가 잘 풀리지 않았다.ㅠ dp인것은 대충 감이 오지만, dp는 지금까지 백준에서는 1 또는 2차원 배열을 이용해서 차곡차곡 이전의 요구사항에 맞게 정답을 만들어 나갔다. 예를들어 최솟값을 찾는 거라면, n이 될 때까지, 점화식을 이용해서 1 ~ n 까지 차례대로 차곡차곡 이전의 값을 이용해서 n일때의 최솟값을 만들어 나가는 느낌이..

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 풀었긴했지만 시간적 효율이 안좋아서 다시 한번 생각해 보았다. 처음에 이 문제에서 점화식을 dp[n][k] = dp[n - 1][i]( i = 1 ~ k까지) 라고 두었다. 그렇게 되면 => 3중 중첩문 + 여러번 같은 수를 반복해서 더하게됨. dp[2][1] 이나 dp[2][5] 를 더할 때도 반복해서 dp[1][1 ~ k] 까지 똑같이 같은 반복으로 더해야한다. 이는 불필요하다. 아래는 위의 점화식으로 코드를 짠것이다. dp = [[0] * 201 for _ in range(201)] n, k = map(int,input().split()) for i in range(1, 20..

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 최소 제곱수의 합을 쭉 나열해 보면, 0 - 0개 1 - 1^2 (1개) 2 - 1^2 + 1^2 (2개) 3 - 1^2 + 1^2 + 1^2 (3개) 4 - 2^2 (1개) 5 - 2^2 + 1^2 (2개) 6 - 2^2 + 1^2 + 1^2 (3개) 7 - 2^2 + 1^2 + 1^2 + 1^2 (4개) 8 - 2^2 + 2^2 (2개) 9 - 3^2 (1개) 10 - 3^2 + 1^2 (2개) 11 - 3^2 + 1^..