백준

문제 https://www.acmicpc.net/status?user_id=whipbaek&problem_id=1197&from_mine=1 채점 현황 www.acmicpc.net 풀이 제목 그대로 최소스패닝트리(MST)를 만드는 문제다. MST를 만드는 방법으로는 크루스칼과 프림 알고리즘 두개가 있는데 나는 크루스칼을 활용하여 풀었다. 크루스칼은 edge들의 비용순으로 오름차순 한 후에, 하나씩 연결해보는 알고리즘이다. 연결하다가 사이클이 발견되면 그 edge는 뛰어넘고 다음 edge를 확인해보는 식으로 반복된다. 이 때 사이클을 감지하기 위하여 union find 알고리즘을 활용한다. 연결하려는 두 노드의 루트노드가 같다면 사이클이 존재한다는 것이다. 사이클이 발생하지 않을경우에만 비용값을 더해주고 ..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 dp 방식으로 생각해보면 '내가 위치한 계단을 어떻게 오느냐' 에 초점을 맞춰보면 된다. 내가 i번째 계단에 있다면 나는 1. i-1 번째 계단에서 왔거나 2. i-2 번째 계단에서 왔을것이다. 단 i-1번째 계단에서 왔다면, i-2번째계단을 밞고오진 않았을 것이다. (그렇게 되면 3개 연속 계단을 밞으니) 따라서 i-3 번째에서 왔을것이고 이를 활용하여 점화식을 세울 수 있다. D[i] = max..

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

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