문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 단 차이점은, 증가하는 부분 수열중 합이 가장 큰 값을 반환해야하는 것이다. 이 문제 또한 특정 인덱스에서 앞을 순회하면서, 1) 나보다 값이 작다면 2) 갱신되는 값이 더 크다면 갱신해준다. 라는 플로우를 따르면 된다. 식으로 나타내면 D[i] = max(D[i], D[j] +..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이 문제에서 n의 제한은 1000이다. 따라서 O(n^2) 풀이가 가능한것을 인지하고 있자. 증가하는 수열이므로, 특정 인덱스 앞의 요소들을 하나씩 다 살펴본다. 1) 이후 만약 값이 나보다 작고 2) 해당 값에 저장된 수열 + 1 (현재 인덱스까지 포함하면 + 1 이니까 ) , 현재 수열의 길이를 비교해서 ..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 2 x n 타일링 문제와 거의 유사하다. (풀이 링크 : https://whiporithm.tistory.com/6 ) 차이점이라고는 2 * 2 타일이 하나 더 들어온 것. 따라서 = 타일이 ㅁ 타일이 될 수 있다. 그렇기에 경우의 수를 2배로 설정해주면 답이 나온다. 코드 n = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3, 1001): d[i] ..

문제 (S3) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 DP의 정수, 타일링 문제이다. 예전에도 풀었지만 100프로 이해한다는 느낌이 아니었는데, 이 참에 다시 풀어봤다. 우리는 1*2 의 타일과 ( ㅡ ) 2 * 1 타일을 사용할 수 있다. ( | ) 해당 타일들을 이용하여 2 * n 의 타일을 채워야한다. 여기서 우선 생각해야할것중 하나는 1 * 2 타일을 사용하기 위해서는 항상 2개를 세트로 사용해야한다. ( = ) 경우의 수를 생각해보면 Case..

문제 (S3) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 D[n]은 n을 1로 만드는 최소한의 연산 개수가 들어가있다. 가능한 연산은 3개로, 1을 빼거나 2로 나누거나 3으로 나누거나이다. 최소한의 연산을 수행하기 위해서 우리가 우선순위로 두어야할 연산은 1. 3으로 나누기 2. 2로 나누기 3. 1로 빼기 일 것이다. 왜냐면 큰 숫자로 나누어야 연산이 최소화가 될테니까 말이다. 그래서 문제를 풀 때 모든 숫자에 적용 가능한 1로 빼기를 먼저 수행해보고, 이후에 2로 나뉘어지는지 체크해보고, 3으로 나뉘어지는지 체크하는 순으로 검사 및 갱신하면 ..

문제 (S4) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 DP 연습이 필요할 거 같아서, 실버문제들을 쭈욱 풀면서 감을 잡으려 한다. 설탕배달은 단순하다. D[n]은 n Kg 을 배달하는 최소 설탕봉지의 개수가 저장되어 있다. 초기값으로 D[3] = 1 , D[5] = 1 로 설정해준다. 그리고 6부터 loop를 돌려준다. 이 때 n kg 일때, d[n-3] 또는 d[n-5] 값이 있다면 해당값으로 갱신해준다. 만약 d[n-3], d[n-5] ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 완전탐색으로 풀었다. 문제 풀 때 주의해야하는거는 1. 라이언이 어피치를 이겨야 한다. 2. 이길 때, 가장 큰 점수차로 이겨야한다. 3. 가능하면 작은 점수의 화살을 많이 맞춰 이겨야한다. 이 세가지 요소이다. 따라서 나는 가장 작은 점수부터 맞추는 방식으로 접근했다. 0점부터 -> 10점까지 접근하면서 모든 경우의 수를 체크해본다. (해당 인덱스의 점수를 얻거나, 포기하거나) 이 때..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 완전탐색을 곁들인 단순 구현문제이다. 최대 7개의 이모지가 들어오는데, 해당 이모지가 할인할 수 있는 모든 경우의 수를 적용시키고 유저와 비교해본다. 그 중에 우리의 목표와 가장 알맞는 값을 가져오면 된다. 어려운 문제는 아니지만, 유의미한 아이디어라고 하면 import itertools 순열이나 조합등을 다루는 itertools 라이브러리의 product를 사용했다면 좀 편하게 풀 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 생각했던 풀이 같은 경우에는, 거리를 줄일려면 가장 먼 택배부터 배달해야한다고 생각했고, 가장 먼곳의 택배 배달을 끝내고, 여분이 남으면 그 앞에 배달위치까지 커버하는 방식으로 진행했다. (실질적으로 배달은 앞에서부터 되나, 뒤에서부터 내가 배달할 수 있는 양을 계산했다.) 수거또한 멀리서부터 할려고 했고, 가장 멀리있는 경우부터 수거하고, 공간이 남으면 앞의 수거목록까지 커버하는 방..