분류 전체보기

[문제]https://www.acmicpc.net/problem/1516 [접근방식]해결 키워드는 '위상 정렬' 과 'DP' 이다. 위상 정렬은 우선순위가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 작업 순서를 정해주는 알고리즘이다. 현재 건물 건설시 선행 건물의 건설이 필수적인 현재 문제에서 효과적인 알고리즘이다. [위상 정렬 참고자료]https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting [알고리즘] 위상 정렬 (Topological Sorting)정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.조금 더 이론적인 설명은, 사이클이 ..

[문제]https://www.acmicpc.net/problem/11066 [접근방식]이 문제는 '다이나믹 프로그래밍' 으로 해결하고자 한다. 문제를 읽어보고 든 생각은 백준 11049번 '행렬 곱셈 순서' 문제랑 유사하다. 라는 것이었다. 문제 - https://www.acmicpc.net/problem/11049 풀이 - https://notorious.tistory.com/417  '행렬 곱셈 순서' 문제 풀이의 핵심은 "dp[i][j] 를 (i~k) 와 (k+1~j)로 구간을 나눠 해결" 하는 것이다. 따라서 이 문제 역시 i번째 파일부터 j번째 파일까지 병합하는 최소 비용을 (i~k) 와 (k+1~j)로 범위를 나눠 해결할 것이다. DP 문제 해결에서 가장 중요한 것은 DP배열의 정의를 확실하게..

[문제]https://www.acmicpc.net/problem/17626 [접근방식]문제를 보자마자 든 생각은'동전' - https://notorious.tistory.com/412'동전2' - https://notorious.tistory.com/414위 두문제와 유사한 방식으로 해결해야 겠다 였다. 위 두 문제는 동전 종류를 하나씩 대입하여 dp[i] = dp[i - coin] + 1 방식을 통해, i원을 구성하는 경우의 수 개수를 구하는 해결 방식을 채택했다. 이와 비슷하게 "동전의 종류" 대신에 제곱(1^2, 2^2, 3^3, ...)를 대입하여 해결하고자 하였다. dp배열의 정의는 "i 를 표현하는 제곱수들의 최소 개수" 로 설정하였다. [Java 코드]/** * BOJ_17626 Four S..

[백준 11049번 '행렬 곱셈 순서']https://www.acmicpc.net/problem/11049 [접근방식]다이나믹 프로그래밍을 이용하여 해결한다.DP 배열의 정의는 다음과 같다."dp[i][j] : i번째 행렬부터 j번째 행렬까지 최소 곱셈 연산수" 작은 집합부터 계산해 나가 궁극적으로 0 ~ n-1 까지의 행렬의 최소 곱셈 연산수를 구한다. '''곱셈 연산 단위 : 2개 - [(0, 1), (1, 2), (2, 3), (3, 4), ... , (8, 9)] 곱셈 연산 단위 : 3개 - [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), ... , (7, 8, 9)] ...  곱셈 연산 단위 : 10개 - [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)]..

[백준 9252번 'LCS 2']https://www.acmicpc.net/problem/9252 [접근 방식]LCS(Longest Common Subsequence), "최장 공통 부분 수열" 은 '대상 문자열들의  문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열'을 의미한다.위 문제의 예제1을 보면,"ACAYKP" , "CAPCAK" 이렇게 두개의 문자열의 LCS 를 구하고자 한다. "ACAYKP""CAPCAK" LCS = "ACAK" 이다.꼭 연속된 문자가 아니더라도, 순서대로 공통된 문자들의 집합의 가장 긴 사례를 구하는 것이 "최장 공통 부분 수열" 이다. LCS에 대한 자세한 설명은 https://buly.kr/7mAqbah 를 참고. 문제 해결 키워드는 "LCS"를 "DP"를 이용하여 ..

[백준 2565번 '전깃줄']https://www.acmicpc.net/problem/2565 [접근 방식]스스로 해결하지 못한 문제. 다이나믹 프로그래밍과 최장 증가 부분 수열을 사용하여 해결하는 문제이다.전기줄들을 A위치를 기준으로 오름차순 정렬한다.정렬된 전기줄들의 B위치 배열에서 최장 증가 부분 수열의 최대 길이를 구한다. 전체 전기줄 개수에서 최대 길이를 빼면, 제거해야 하는 전기줄의 개수가 도출된다. 여기서 중요 포인트는, 최장 증가 부분 수열을 다이나믹 프로그래밍을 통해 구현하는 것이다.length 배열의 정의 : length[i] 를 끝으로(포함) 하는 최장 증가 부분 수열의 길이따라서 인덱스 k의 원소를 포함하는 최장 증가 부분 수열의 길이를 DP를 이용하여 구한다.인덱스 k 원소가 가장..