분류 전체보기105 [BOJ] 백준 1005번: ACM Craft 문제 링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 예제 그림은 4번 건물을 짓기 위하여 2번과 3번 건물이 모두 지어져야 하고, 2번과 3번을 짓기 위하여 1번 건물이 지어져야 하는 경우를 보여준다. 이때 4번 건물을 짓기위해 걸리는 최소 시간은 1->3->4 를 짓는 시간인 120초가 걸리게 된다. 즉, i번 건물까지 짓는 시간은 자신의 상위 건물(j..) 들 중 가장 오래 걸리는 시간에 영향을 받는다. 동적 계획법을 사용하여 dp[i]를 i번째 것물을 짓는 최소 시간이라고 한다면 아래 식으.. 2020. 6. 29. [알고스팟] 합친 LIS ID: JLIS 2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) LIS 길이는 꽤 단순하게 구할 수 있다. 10 20 10 30 20 50의 전체 수열이 있다면 먼저 10을 벡터에 넣는다 10 그 다음 수를 벡터의 마지막 수와 비교하여 1) 마지막 수보다 크다면 그대로 벡터에 삽입 10 2 seongjuk.tistory.com 이전 포스팅에서 LIS 알고리즘을 다뤘는데요, 이번에는 확장된 LIS인 두 배열에서 최장 증가 부분 수열을 뽑는 문제에 대해 다루려고 합니다. 문제 링크 algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열.. 2020. 6. 28. [알고스팟] 와일드카드 ID: WILDCARD 문제 링크 algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 와일드카드란 어떤 문자도 가능한 만능 문자로 *는 0글자 이상의 문자로 대체 가능하고, ?는 어떠한 문자 (1글자)로 대체될 수 있습니다. 예를 들어 b*a 는 bba, banana, ba와 같은 문자들로 대응될 수 있으며 b?a는 bba, baa, bca 로 대응 될 수 있지만 bbaa, ba와 같은 문자로 대응될 수 없습니다. 특정 와일드카드를 0개 이상 포함된 문자열이 주어지고, 대응 후보 문자열이 여러개 주어졌을 때, 대응될.. 2020. 6. 27. 최장 증가 부분 수열 찾기 | 역추적 (Longest Increasing Subsequence Tracking) 2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) 지난 포스팅에서 LIS로 찾은 결과는 부분 수열의 최장 길이에 대한 정보만을 가지고 있을 뿐, 그 자체가 부분 수열이 될 수 없다는 점을 강조했다. LIS 역추적을 위해 pair 자료형 배열을 만들고 다음과 같이 정의하였다. pair LIS[MAX_SIZE] // first = 값, second = 인덱스 그리고 매번 arr배열을 탐색하면서 2가지 규칙으로 i번째 인덱스 앞에 올 인덱스 j (j LIS[_size-1].first) { lastidx = i; pre[i] = LIS[_size - 1].second; LIS[_size++] = { arr[i],i }; continu.. 2020. 6. 26. 이전 1 ··· 19 20 21 22 23 24 25 ··· 27 다음
