본문 바로가기

자료구조

 (36)
[1차] 뉴스 클러스터링 문제이해 입력으로 들어온 str1, str2를 두글자씩 끊어 다중집합의 원소로 만든다. 예제 1 FRANCE , french 가 있으면 FRANCE = {fr, ra, an, nc, ce} french = {fr, re, en, nc, ch} A U B = {fr, ra, an, nc, ce, re, en,ch} A X B = {fr, nc} n( A U B) = 8 n( A X B) = 2 유사도 = 0.25 65536 * 0.25 = 16384 예제 2 aa1+aa2 AAAA12 aa1+aa2 = { aa, aa } AAAA12 = {aa, aa, aa} n( A U B) = {aa, aa, aa} n( A X B) = {aa, aa} 유사도 = 0.6666 65536 * 2/3 = 43690.666..
지그재그 순열 Euler Zigzag Number (Entringer Number)을 사용했다. www.acmicpc.net/problem/1146 - 풀이 www.acmicpc.net/problem/3948 - 풀이 #include using namespace std; int main() { freopen("Text.txt", "r", stdin); int tCount; scanf("%d", &tCount); for (int t = 0; t < tCount; t++) { int nCount; scanf("%d", &nCount); //해당 길이의 커작커, 작커작 int d[301][301]{ 0, }; //base case d[2][1] = 1; for (int i = 3; i
[LIS DP]JUNGOL 1257 : 전깃줄(중), 1408:전깃줄(하) LIS DP문제이다. LIS DP를 처음 작성해 보아서 작성하는데 시간도 오래 걸렸고, 코드도 굉장히 복잡하다. 전깃줄(중)에서 유의할 점은 문제에 오류가 있는 것으로 보인다. 여러가지 답이 나올 수 있는데 그런 여러가지 답을 채점에 고려하지못해서 채점이 잘 안된다. 따라서 제출할 때 정답여부에 너무 집착하지 않아도 될 것 같다. O(n^2)의 경우는 시간초과가 나기 때문에 O(nlogn)의 이진탐색 알고리즘을 이용해야한다. O(n^2)의 경우 주의해야 할 점은 DP를 정확히 이해하는게 중요하다. i번째 값을 결정할때는 1~i-1번째까지의 모든 값 중에 가장 큰값을 선택해야하기 때문에 O(n^2)이다. O(nlogn)의 이진탐색을 이용할 때 주의할 점은 추적이 굉장히 어렵고 인덱싱 기법(몇번째 증가수열에..
260. [S/W 문제해결 응용] 7일차 - 화학물질2 Matrix속에서 sub Matrix를 빠르게 찾는 것도 중요하다 방법1. 0행, 0열에는 데이터가 들어가지 않게 하고 해당 공간의 열, 행의 합을 유지하면 불필요한 확인을 줄일 수 있다. 만약 문제에서 행렬들 간의 수행가능한 행렬 곱셈의 순서가 하나만 존재하는게 아니면 어떻게 풀어야할까? 깊이 우선 탐색+ 백트래킹을 활용하여 최장 길이로 연결 될 수 있는 행렬 곱셈 순서를 모두 찾아야한다. #include #define MAX_NUM 300 using namespace std; //화학 물질 용기 n^2개 //2차원 배열에 그 정보 저장 //빈용기 0, 화학물질 종류에 따라 1~9 //화학물질이 담긴용기들은 사각형 이룸 //사각형 내부에는 빈용기가 있다. //대각선상으로 빈용기 없을 수도 있다. //행..
JUNGOL 1871 : 줄세우기 LIS 알고리즘을 사용했다 O(n^2) -> O(NlonN)의 알고리즘도 사용해서 풀었으면 좋겠다. #include using namespace std; //적지까지 번호순서대로 일렬로 서서 걸어가도록 //아이들의 번호순서가 바뀌었다. //다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. -> 최소로 순서대로만들자 //N은 2 이상 200 이하의 정수이다. int main() { //freopen("sample_input.txt", "r", stdin); //입력 파일의 첫째 줄에는 아이들의 수 N이 주어진다. int nCount; scanf("%d", &nCount); //둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. int l_arr[201]{ 0, }; for..
1263. 사람 네트워크2 All-pair shortest path에 대한 문제이다. 풀이방법에는 1. Dijkstra 알고리즘을 모든 시작 정점 n-1에 대해서 시현하는 것 2. Floyd Warshall Algorithm을 적용하는 것 둘의 시간복잡도는 O(n^3)으로 같지만 실행시간은 차이가 있다 Dijkstra가 압도적으로 빠르다 => 기존에 가지고 있던 Data를 가지고 start->해당 정점까지의 거리로 갱신된다, Dijkstra는 update가 필요한 노드의 최단거리만 확인하거나 Heap을 이용해서 앞쪽에서 갱신된 최단거리가 더 작으면 cutting이 되는 case가 많다. 더 빠르게 할 수 있는 방법: BFS 극한의 빠르게 할 수 있는 방법: Best First Search!!! => 나중에 풀어보고 성능을 비교해보..
편집거리 알고리즘 점화식 1. 문자열의 해당 위치 값이 같을때 => D_ij = D_(i-1)(j-1) 대부분의 DP테이블은 2차원이 기본이다. str1을 몇번 수정하면 str2로 만들 수 있을까? str1[1] == str2[1] 이면 edit이 필요없다. 그래서 i-1, j-1의 위치의 값을 그대로 넣는다. 2. 해당 위치 값이 다를때 =>추가가 됐거나, Delete됐거나, Edit됐거나 편집거리 최소인 거리 추적하기 왼쪽, 왼쪽 위, 위쪽 으로부터 왔는지 저장해야한다. => 값을 누가 바꿨는가를 보고 봄ㄴ서 찾는 것이다. 왼쪽인 경우 삭제 왼쪽 위 edit 위쪽인 경우 단어 추가 --> 헷갈리니까 책에 있는 표 보지말자 그냥 아래 블로그 표 보자 hsp1116.tistory.com/41 편집 거리 알고리즘(Leven..
최장 증가 부분 수열 LIS 찾기 Brute-froce 접근 부분집합중에 오름차순인 것중에 가장 길이가 긴 것을 찾는다 2^n의 시간복잡도라서 풀수 없을 수 있다. DP접근방법 n-1 에서 n의 상태가 되는 것을 찾아보자(주의할점은 꼭 n-1만 생각할 필요는 절대 없다. n-2, n-3 까지 더 멀리 있을 수도 있다) LIS table의 성격은 LIS(i)는 i번째 원소를 가장 끝 값으로 하는 연속된 숫자 최대 개수!!! 제발 DP에서 i번째 테이블의 값을 정의를 분명히해야한다 앞에서 부분집합을 가지고 1. i번째 숫자가 LIS(i)에 포함되는 경우 LIS(i)란? LIS(i)_ = 1+ maxLIS(j) j가 i보다 작으면서 aj 한번 구현해보는 것 중요할것같다.

티스토리툴바