동적 계획법13 [알고스팟] 와일드카드 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. [BOJ] 백준 2098번: 외판원 순회 TSP (traveling salesman problem) 로 잘 알려진 외판원 순회문제는 NP-Hard 문제로, 마을의 수 n에 대해 다항식의 형태로 복잡도가 계산될 수 없다. 그래서 N의 개수가 매우 적고, 비트마스크를 사용하여 방문한 마을을 1로 표기하여 001011 처럼 1,2,4 번째 마을을 방문했다를 표현할 수 있다. TSP는 시작점을 어느 마을로 하든 동일한 값이 나오기 때문에 시작 마을을 인덱스 0으로 편의상 둔다. if (state == (1 2020. 6. 25. [BOJ] 백준 1509번: 팰린드롬 분할 Class 5에는 대부분 DP로 구성된 것 같네요 recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면 i = e) { return pal[s][e] = 1; } int& ret = pal[s][e]; if (~ret) return ret; ret = 0; if (str[s] == str[e]) { return ret = ispal(s + 1, e - 1); } return ret; } int recv(int node) { if (node == n) { return 0; } int& ret = dp[node]; if (~ret) return ret; ret = 2e9; for (int i = node; i < n; i++) { if (ispal(node, i.. 2020. 6. 25. 이전 1 2 3 다음
