[백준] 1562번 - 계단 수 (한줄평) 간단하다고 생각했지만 0부터 9까지 숫자가 모두 등장했는지 확인하기 위한 아이디어를 떠올리기 어려웠던 문제였다. 비트 마스킹을 이용한 DP 문제 유사 문제: 10844 https://hseungyeon.tistory.com/302 [다이나믹 프로그래밍] 10844번 - 쉬운 계단 수 [백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 hseungyeon.tistory.com 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 0으로 시작하는 수는 계단수가 아니다. 수의 길이 n이 주어질 때 0~9까지 숫자가 모..
[백준] 2293번 - 동전 1 (한줄평) 오랜만에 풀었더니 dp 문제 감을 잃었다고 느꼈다. 한 끝차이로 계속 틀린 이유을 찾지 못했던 문제.. 다음에 다시 풀어봐야할 것 같다 풀이 시간: 60분 이내 n가지 종류의 동전을 사용해서 가치의 합이 k원이 되는 경우의 수를 구하는 문제다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. (풀이1) 틀린 풀이 1) 문제 해결 아이디어 점화식을 세우기까지는 오랜시간이 걸리지 않았으나 그걸 코드로 구현하는 과정에서 잘못 생각한 부분이 있어서 어려움을 겪었다. 2) 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) # 동전 종류, 가치의합 graph = [int(..
[백준] 2629번 - 양팔 저울 (한줄평) 생각보다 머리가 복잡했던 문제.. 점화식을 만들기가 어려웠다.. 무조건 복습필수다 풀이 시간: 90분 이내 1) 문제 해결 아이디어 추의 개수 n(30 이하), n개의 추의 무게(500이하의 자연수)가 오름차순으로 주어지고 구슬의 개수 m(7이하), m개의 구슬의 무게(40000 이하의 자연수)가 주어진다. 양팔 저울에 추를 사용하여(올리거나 올리지 않을 수 있음) 주어진 m개의 각 구슬의 무게를 확인할 수 있는지 여부를 구하는 문제다. 각 추를 사용할 때 3가지 경우의 수가 있다. 즉, 추의 개수가 n이면 추를 이용하여 구할 수 있는 모든 경우의 수는 3**n이 된다. n의 값이 최대 30이므로 단순하게 완전 탐색을 한다면 이 문제는 시간초과로 풀 수 없게된..
[백준] 11049번 - 행렬 곱셈 순서 (한줄평) 이전에 풀었던 문제와 풀이 방식이 비슷해서 풀 수 있었지만 다음에 다시 풀면 못 풀 것 같기도 한 문제.. 복습이 꼭 필요하다! 유사 문제: 11066 https://hseungyeon.tistory.com/313 [다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기 [백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3 hseungyeon.tistory.com 풀이 시간: 60분 이내 1) 문제 해결 아이디어 n개의 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 구하는 문제다. 이 문제의 핵심은 대각선방향으..
[백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3시간 이내 1) 문제 해결 아이디어 소설을 구성하는 장의 수(k)와 k개의 파일의 크기(f)가 주어졌을 때 모든 장을 합치는데 필요한 최소 비용을 구하는 문제다. 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산해야한다...
[백준] 9252번 - LCS 2 (한줄평) 이전에 풀었던 LCS를 잘 이해하고 있다면 쉽게 풀 수 있었던 문제! 메모리, 시간 복잡도를 개선할 수 있는 방향으로 코드를 짜기 위해 고민해야하므로 나중에 한 번 쯤 다시 풀어보는 것이 좋을 것 같다 유사 문제: 9251 https://hseungyeon.tistory.com/311 [다이나믹 프로그래밍] ★★ 9251번 - LCS [백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하 hseungyeon.tistory.com 이 문제는 LCS 길이와 LCS를 구하는 문제로 DP테이블에 LCS를 바로 기록하는 방식과..
[백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하다 두 문자열의 LCS 길이를 구하는 문제다. 이 문제는 각 문자열의 길이를 하나씩 늘려가며 두 문자열의 LCS를 반복적으로 구하는 것이 핵심이다!! dp 테이블을 2차원 혹은 1차원 리스트로 풀이하는 방식 2가지가 있는데 1차원 리스트를 이용하여 구현항 방식이 조금 더 효율적인 방식이다. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴것을 찾는 문제 (풀이1) 2차원 리스트 이용 풀이 시간: 50분 이내 1) 문제 해결 아이디어 dp 테이블을 2차원 리스트로 생성하여 푼 방식이다. 1. ..
[백준] 12865번 - 평범한 배낭 (한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!! 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다. 1. 분할가능 배낭 문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 때(설탕 몇 g) - 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능! - 배낭이 감당할 ..
