프레소님의 블로그

[백준 / BOJ] 1028 다이아몬드 광산 (Python)

문제 링크https://www.acmicpc.net/problem/1028사용 알고리즘DP누적 합풀이주어진 배열 안에서 나타나는 가장 큰 다이아몬드 모양의 크기를 구하는 문제이다. 첫 시도에는 주어진 행, 열의 크기에 따라 나타날 수 있는 모든 다이아몬드 모양의 좌표를 저장해두고 각 모양마다 해당 모양을 만족하는 경우가 있는지 확인하는 식으로 구현했지만 시간 초과가 발생해서 다른 사람의 풀이를 보고 해결했다.이 문제를 풀기 위해서는 다이아몬드의 성질을 파악해야 한다. 특정 좌표를 다이아몬드 모양의 가장 왼쪽 좌표가 `(y, x)`라고 가정했을 경우,`(y, x)`에서부터 우측 상단, 우측 하단으로 연속된 1의 개수와`(y, x + 2 * (size - 1))`좌표에서의 좌측 상단, 좌측 하단으로 연속된 ..

문제 링크https://www.acmicpc.net/problem/1700사용 알고리즘그리디풀이한정된 수량의 플러그에 각 전기용품을 순서대로 사용해야 할 경우에서플러그를 최소한으로 빼며 모든 전기용품을 사용하려면 몇 번 플러그를 빼야하는지 구하는 문제이다. 여기서 중요한 점은 각 전기용품을 순서대로 사용해야 하기 때문에 전기용품을 사용하는 순서에 따라 가중치를 주어야 한다는 점이다.플러그를 빼야 할 경우(현재 멀티탭에 꽂혀있는 전기용품의 개수가 k 이상일 경우),현재 멀티탭 안에 꽂혀있는 전기용품들의 가중치를 구한 뒤 가중치가 가장 낮은 전기용품을 빼면 된다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')std..

문제 링크https://www.acmicpc.net/problem/1029사용 알고리즘DP비트필드를 이용한 다이나믹 프로그래밍그래프 이론풀이이 문제를 해결하기 위해 DP 배열에 저장해야 할 정보는 3가지이다.현재 그림을 가지고 있는 사람: 다음 거래의 가격을 결정하기 위해 필요하다.직전에 거래된 가격: 다음 거래의 가격이 직전 거래의 가격보다 크거나 같은지 확인하기 위해 필요하다.지금까지 지나온 사람들: 이미 거래한 사람들에게 다시 거래하지 않기 위해 필요하다.이 3가지 조건에 따라 그림을 가지고 있던 사람의 최대값이 달라지게 된다. DP 배열 내의 각 정보들의 크기는 아래와 같이 잡는다.현재 그림을 가지고 있는 사람: n명직전에 거래된 가격: 10 (최대 가격이 10이기 때문에)지금까지 지나온 사람들:..

문제 링크https://www.acmicpc.net/problem/1339사용 알고리즘그리디풀이단어들에 등장하는 알파벳에 각각 숫자를 대입해서 반환된 값의 합의 최대를 구하는 문제이다. 이를 구하기 위해서는 등장하는 각 알파벳 별로 모든 단어에서 해당 알파벳이 위치한 자리가 큰 순서대로 숫자를 할당해주면 된다. 예제입력2GCFACDEB 위의 예제에서 등장하는 알파벳은 (A, B, C, D, E, F, G)이다. 알파벳이 등장하는 자리에 따라 가중치를 더 크게 주어야 하기 때문에 모든 단어들에 0을 패딩해 자리수를 맞춰주자.index01234S[0]00GCFS[1]ACDEB 이와 같은 상태에서 자리수별로 가중치를 주게 된다면 아래 표와 같이 되고, 가중치가 높은 순서대로 숫자를 할당해주면 된다.알파벳가중치..

문제 링크https://www.acmicpc.net/problem/2602사용 알고리즘DP풀이천사 or 악마, 현재 밟고 있는 위치, 현재 문자열이 두루마리의 몇 번째 문자열인지를 저장할 DP 배열을 만들어준다. 우선 DP 배열을 초기화하기 위해 두루마리의 맨 처음 문자열을 밟아준다.s, devil, angel = input(), input(), input()dp = [[[0] * len(s) for _ in range(len(devil))] for _ in range(2)]for now in range(len(devil)): if devil[now] == s[0]: dp[0][now][0] = 1 if angel[now] == s[0]: dp[1][now][0] = 1 그 후, 돌다리의 각 ..

문제 링크https://www.acmicpc.net/problem/17845사용 알고리즘DP풀이자주 접할 수 있는 DP 문제이다. 공부 시간에 따른 최대 중요도를 저장하는 DP 배열을 만든 뒤,각 과목별로 `max(현재 최대 중요도, 현재 공부 시간 - 해당 과목의 필요한 공부 시간 + 해당 과목을 공부했을 때 얻을 수 있는 중요도)`를 구하면 된다. 이 때 과목별로 현재 시간에 따른 중요도를 갱신하는 과정에서 `t ~ n + 1`로 반복하면 동일한 중요도가 더해질 수 있기 때문에 뒤에서부터(`n ~ t - 1`) 반복하는 것으로 해결할 수 있다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = i..

문제 링크https://www.acmicpc.net/problem/1563사용 알고리즘DP풀이여러 방법으로 시도하다 도저히 풀리지 않아 다른 사람의 풀이를 보고 푼 문제이다.나는 출석, 지각, 결석에 따른 경우의 수를 저장하는 배열을 사용하려 했지만 구현 시 현재 출석했을 때 결석의 수를 초기화할 수 없기 때문에 잘못된 방식으로 접근했다. 이 문제를 해결하기 위해 만들어야 할 DP 배열은 i번째 날에 지각, 결석한 횟수에 따른 경우의 수를 저장하는 배열이다.▶︎ `dp[학기의 날짜 수(= n + 1)][가능한 지각 횟수(= 2)][가능한 결석 횟수(= 3)]` 위와 같은 DP 배열을 만들면 현재 날짜의 지각, 결석 횟수에 따른 경우의 수를 저장할 수 있다.현재 날짜의 지각, 결석 횟수에 따라 아래와 같은..

문제 링크https://www.acmicpc.net/problem/2229사용 알고리즘DP풀이문제를 풀어서 설명하면 연속된 학생들끼리 묶어서 조를 구성할 경우, 각 조들의 잘 짜여진 정도의 합의 최댓값을 구하는 문제이다. 따라서, 각 학생별로 해당 학생까지 각 조들의 잘 짜여진 정도의 합의 최댓값을 저장하는 dp 배열이 필요하다.▶︎ `dp[i] = dp[i]까지 각 조들의 잘 짜여진 정도의 합의 최댓값` 그리고 i번 학생까지 조가 잘 짜여진 정도의 합을 알기 위해선,기존에 구했던 0 ~ i번 학생(j라고 가정)에서의 조가 잘 짜여진 정도의 합에`max(i번 학생의 점수, j번 학생의 점수) - min(i번 학생의 점수, j번 학생의 점수)`를 더했을 때 최대가 되는 값을 구하면 된다.코드import s..

문제 링크https://www.acmicpc.net/problem/11058사용 알고리즘DP풀이dp 배열의 각 인덱스를 현재 버튼을 i개 눌렀을 때 화면에 출력된 A의 최대 개수로 가정한다.▶︎ `dp[i] = i번 버튼을 눌렀을 때 화면에 출력된 A의 최대 개수` dp 배열의 초기값으로는 단순이 A만 눌렀을 때 화면에 출력된 A의 개수로 설정해두고,각 위치에서 Ctrl-A, Ctrl-C, Ctrl-V를 했을 경우(= `i + 2`) 나올 수 있는 A의 개수로 dp 배열을 갱신해주면 된다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = io.BytesIO()sys.stdout.write = lam..

문제 링크https://www.acmicpc.net/problem/14267사용 알고리즘DPDFS트리트리에서의 다이나믹 프로그래밍풀이이 문제를 풀기 전에 15681 트리와 쿼리를 먼저 풀어보는 것을 추천한다.이 문제와 유사하면서 트리에서의 다이나믹 프로그래밍에 대해 이해하기 좋은 문제다. 우선, 가장 먼저 할 일은 직속 상사와 부하의 관계를 표현할 tree 구조를 만드는 것이다.관계, 트리에서의 각 노드의 부모, 트리에서의 각 노드의 자손들을 저장할 배열을 만들어준 뒤 입력값을 통해 관계를 설정해주자.n, m = map(int, input().split())connect, node_parent, node_children = [[] for _ in range(n)], [-1] * n, [[] for _ ..