파이썬

문제 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 가장 긴 감소하는 부분 수열이랑 문제가 완전히 똑같다. (가장 긴 증가하는 부분 수열의 반대로 https://whiporithm.tistory.com/11 ) n에서 가장 긴 감소하는 부분 수열의 길이를 빼주면 정답이다. 코드 n = int(input()) d = [1] * n wars = list(map(int, input().split())) for i in range(n..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 해당 문제는 뒤에서부터 접근하여 최댓값을 갱신하는 방식으로 풀 수 있다. D[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이라고 정한다. 이후 뒤에서부터 (지금 날짜 + 오늘 일하면 걸리는 날짜)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보고서 Dictionary를 사용해야할 거 같았다. 1. 우선 주어진 프로그래밍 언어, 직군 등을 조합하고 모든 부분집합을 Key로 만들어주고 초기화해준다. 2. 이후에 info 리스트를 순회하면서 모든 부분집합을 만들고, 해당하는 Key에 점수를 넣어준다. 3. 마지막에는 query 리스트를 순회하면서 해당 조건에 맞는 Key를 찾고, value (점수들이 들어가있는 list)..

문제 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] ..