[백준] 9252번 - LCS 2 (한줄평) 이전에 풀었던 LCS를 잘 이해하고 있다면 쉽게 풀 수 있었던 문제! 메모리, 시간 복잡도를 개선할 수 있는 방향으로 코드를 짜기 위해 고민해야하므로 나중에 한 번 쯤 다시 풀어보는 것이 좋을 것 같다 유사 문제: 9251 https://hseungyeon.tistory.com/311 [다이나믹 프로그래밍] ★★ 9251번 - LCS [백준] 9251번 - LCS (한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하 hseungyeon.tistory.com 이 문제는 LCS 길이와 LCS를 구하는 문제로 DP테이블에 LCS를 바로 기록하는 방식과..
[백준] 11726번 - 2xn 타일링 (한줄평) 쉽게 해결할 수 있었던 문제! 유사 문제: https://hseungyeon.tistory.com/287 [다이나믹 프로그래밍] ▲ 문제3 - 바닥 공사(223p) [이코테] 문제3 - 바닥 공사(223p) (한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직 hseungyeon.tistory.com 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1 2가지 타일로 채울 수 있는 경우의 수를 10007로 나눈 나머지를 구하는 문제다. 이 문제는 다이나믹 프로그래밍의 기..
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (한줄평) LIS 응용 문제로 LIS(최장증가부분수열)알고리즘을 안다면 쉽게 풀 수 있었던 문제! 풀이 시간: 15분 이내 1) 문제 해결 아이디어 n이 1이상 1000이하인 길이가 n인 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 구하는 문제다. 수열 S가 어떤 수 Sk를 기준으로 (S1 Sk+1 > ... SN-1 > SN)을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. Sk를 기준으로 왼쪽은 가장 긴 부분 증가 수열, 오른쪽은 가장 긴 부분 감소 수열을 구하면 풀 수 있는 문제다. 가장 긴 부분 감소 수열을 구하기 위해서 입력받은 수열을 reverse해야한다는 것을 잊지말자! 2) 소스코드 n = int(input()) # ..
[백준] 1463번 - 1로 만들기 (한줄평) 전에 풀었던 문제와 유사하지만 생각보다 시간이 좀 걸렸던 문제! 유사 문제: https://hseungyeon.tistory.com/285 [다이나믹 프로그래밍] ▲ 문제1 - 1로 만들기(217p) [이코테] 문제1 - 1로 만들기(217p) (한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제 풀이 시간: 40분 이내 1) hseungyeon.tistory.com 풀이 시간: 20분 이내 1) 문제 해결 아이디어 정수 X(1
[백준] 2579번 - 계단 오르기 (한줄평) 조건때문에 계속 헷갈려서 생각보다 어려웠던 문제! 코드는 단순하지만 복습이 필요하다!! 풀이 시간: 40분 이내 1) 문제 해결 아이디어 다음 조건을 만족하면서 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. i는 무조건 O이므로 (i - 1)은 O 혹은 X가 될 수 있다. 1. ~ OXOO일 때 - (i -1)이 O이면 (i -2)는 무조건 X여야한다. 조건2에서 연..
[백준] 1932번 - 정수 삼각형https://www.acmicpc.net/problem/1932 (한줄평) 익숙한 dp 문제라 쉽게 풀 수 있었던 문제! 풀이 시간: 10분 이내 유사 문제: 1149 https://hseungyeon.tistory.com/298 [다이나믹 프로그래밍] 1149번 - RGB거리 [백준] 1149번 - RGB거리 (한줄평) 아이디어를 쉽게 떠올릴 수 있었던 문제! 효율적인 코드를 짤 수 있게 고민해볼 수 있는 문제였다 이 문제는 집의 수 n(2
[이코테] 문제6 - 병사 배치하기(59:50) (한줄평) 아이디어를 떠올리기 어려웠던 문제로 답을 봤음에도 이해하는데 어려움이 있어서 꼭 복습이 필요!! 풀이 시간: 1) 문제 해결 아이디어 예를 들어 수열 array = {4, 2, 5, 8, 4, 11, 15} 라면 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15} 이다. 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 LIS 알고리즘을 조금 수정하여 정답을 도출할 수 있다! 가장 먼저 입력받은 병사 정보의 순서를 뒤집고 최장 증가 부분 수열(LIS) 알고리즘을 수행하여 정답을 도출한다! 병사 정보의 순서를 뒤집는 이유는 LIS는 가장 긴 오름차순 수열을 찾는 것이지만 실제로 우리는 가장 긴 내림차순 수열을 찾아야 한다. 그러므로 ..
[이코테] 문제5 - 금광(52:30) (한줄평) 혼자서 푸는데는 성공했지만 책 코드와 약간 다른 부분이 있어 복습이 필요한 문제!! (풀이1) 내 풀이 틀린 코드(1차원 리스트) 풀이 시간: 50분 이내 1) 문제 해결 아이디어 문제 자체는 2차원 리스트이지만 입력을 1차원 리스트로 받았기 때문에 금의 최대 크기를 담은 dp테이블도 1차원 리스트로 생성하여 풀었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for _ in range(t): n, m = map(int, input().split()) # 세로, 가로 graph = list(map(int, input().split())) # n * m 개의 금 개수 d = [0] * (n * m) # 금의 최대 크기 for i in..
