알고리즘(23)
-
[백준] 11054 - 가장 긴 바이토닉 부분 수열
백준 바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net DP 알고리즘 내 LIS(Longest Increasing Subsequence) 최장 증가 수열 문제입니다. 이해하는데 하루 꼬박걸렸으며 이해까지 도달하는데 효과적인 매체는 아래 유튜브 강의였습니다. 설명이 영어라도 그림만 봐도 이해되는 강의라 보심을 추천드립니다. 링크 출처: https://www.youtube.com/watch?v=CE2b_-XfVDk&list=LL&index=8&t=311s 풀이의 골자는 주어진 수열을 중첩 반복문으로 돌면서 각 index 값을 ..
2020.10.20 -
[백준] 12865 - 평범한 배낭
백준 바로가기 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 평범한 배낭 문제는 DP 알고리즘으로 분류되며 대표적인 '냅색'(Knapsack) 알고리즘 문제라고 합니다. 위키백과 배낭 문제 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 ko.wik..
2020.10.16 -
[백준] 9251 - LCS(Longest Common Subsequence)
백준 바로가기 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 알고리즘 이어서 푸는 중입니다. 문제 난이도는 solved.ac 기준 풀었던 것중 최상이었고 Gold5 였습니다. 난이도 체감은 알고리즘 개념보다 수학적 사고능력에 따라 높낮이가 결정되는 것 같습니다. DP를 알고있지만 위 문제는 어떻게 적용해야 할지 감이 오지 않았습니다. DP 알고리즘 문제의 특징인듯 합니다. 따라서 많이 풀어보고 다양한 형태의 문제를 접할수록 유리합니다. 제가 참고한 블로그 입..
2020.10.15 -
[백준] 1463 - 1로 만들기
백준 바로가기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 알고리즘 문제를 풀고 있는데요, DP로 안풀고 저만의 방식으로 풀다가 계속 틀리는 바람에 다른 분들 블로그 보고 DP 방식으로 풀었더니 됩니다. 두 가지 방법으로 풀 수 있는데 반복문 사용은 Bottom-up, 재귀 메서드를 이용한 방법은 Top-down으로 불립니다. 재귀의 경우 DP 배열을 써도 느리니 반복문 사용한 Bottom-up 방법을 추천합니다. 일단 두 가지 방법 모두 다루겠습니다. 문제 들어가기에 앞서 사고의 전환이 필요했습니다. 저는 주어진 N으로부터 3을 최대한 많이 사용해 1로 만드는 로직을 만든 다..
2020.10.14 -
[백준] 1904 - 01 타일
백준 바로가기 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 타일 문제는 가지고 있는 타일의 종류에 유의해서 풀어야 되나 봅니다. 그런 다음 어떤 원리가 있는지 규칙을 찾아야 합니다. 일일이 경우의 수를 손으로 구해가며 규칙을 찾으려 하다 경우의 수를 하나라도 빠뜨리면 틀린 규칙이 되버리기 때문입니다. 제가 그랬듯이... 원리에 입각한 풀이방법으로 설명하자면 우리가 가진 타일은 '00' 또는 '1' 두 가지 입니다. 그리고 n번째 경우의 수는 n-2와 n-1 번째 경우의 수에 각각 '00'과 '1' 타일을 추..
2020.10.14 -
[백준] 1436 - 영화감독 숌
백준 사이트 바로가기 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net #Java API 메서드를 사용해도 되지만, 저도 그렇게 풀었습니다. 시간과 메모리 부하를 줄 수 있기 때문에 다른 분들의 코드를 참고했습니다. 그 중에 제 눈높이에 맞고 시간도 오래 걸리지 않는 코드를 가져와 보았습니다. 우선 제가 푼 방식입니다. String.valueOf(int)를 활용해도 됩니다. 1) String.valueOf 사용한 풀이 - 간단하지만 (시간 복잡도가)복잡하다. 1 2 3 4 5 6 7 8 9 10 11 12 1..
2020.10.06