본문 바로가기

전체 글105

최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) LIS 길이는 꽤 단순하게 구할 수 있다. 10 20 10 30 20 50의 전체 수열이 있다면 먼저 10을 벡터에 넣는다 10 그 다음 수를 벡터의 마지막 수와 비교하여 1) 마지막 수보다 크다면 그대로 벡터에 삽입 10 20 2) 마지막 수보다 작거나 같다면 벡터에 있는 요소들 중 다음 수보다 크거나 같은 가장 작은 정수를 찾아 바꿔주면 된다. 10 20 (세번째 10과 첫번째 원래 들어있던 10을 바꾼것이다) 이 수를 찾을 때 lower_bound를 사용하면 편하지만 실력 향상을 위해 직접 이분탐색을 구현하여 써봐도 좋다. 끝까지 반복하면 10(2) 20(4) 30(3) 50(5) ()안에 수는 인덱스이다 의 결과를 얻을 수 있는데 이것은 부분 수열의 길이가 4라는 것이지 이 결과가 최장 증가 부분.. 2020. 6. 25.
[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.
이분 매칭 이분매칭은 x -> y로 가는 y를 모든 x에 대하여 선택할 때 두개 이상의 x가 y로 매칭되지 않으면서 최대로 선택할 수 있는 알고리즘입니다. dfs와 bfs로 접근 가능하며 BFS는 잘 알려진 네트워크 플로우가 속합니다. 본 글에서는 DFS를 사용하여 경우의 수를 찾아보겠습니다. 이분 매칭의 메인 아이디어는 모든 x에 대하여 선택 가능한 y를 찾아 가면서, 1. x가 탐색 중 만난 y가 이전에 다른 x에게 선택되어 지지 않았거나, 2. x가 y를 선택할 때, y를 선택했던 x가 다른 y를 선택할 수 있으면, (즉, {x,y} 상태에서, {x,y}, {x,y} 쌍이 구성될 수 있다면) 이 외의 경우는 x의 짝은 존재 하지 않는다. 현재 탐색하고자 하는 x 는 쌍을 구성할 수 있습니다. 두개의 배열을 선.. 2020. 6. 25.

티스토리툴바