본문 바로가기

알고리즘, 자료구조55

27. 그래프 그래프 사용의 예 철도망의 안정성 분석 - 28 절단점 찾기 알고리즘 소셜 네트워크 분석 - 29 BFS(너비 우선 탐색) 인터넷 전송 속도 계산 - 31 최소 스패닝 트리 한 붓 그리기 (오일러 경로) - 28.4 DFS(깊이 우선 탐색) 외환 거래 - 30 최단 거리 알고리즘 암시적 그래프 구조들 그래프 형태를 갖는 구조가 아니라도, 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제들이 있음. 이를 암시적 그래프(implicit graph)라 한다. 할일 목록 정리 - 위상 정렬(topological sort) - 28 DFS(깊이 우선 탐색) 15-퍼즐 - 29, 30 최단 경로 문제 게임판 덮기 - 32 이분 그래프, 이분 매칭 알고리즘 회의실 배정 - 28 강 결합성 문제 그래프의 표현: 인접.. 2019. 9. 8.
[DP] LIS (최장 공통 부분 수열) LIS (Longest Increasing Subsequence) 수열 안에 있는 증가 하는 부분 수열 중 가장 긴 것을 찾는 문제 Idea1 완전탐색입니다. 1) 수열을 처음부터 하나씩 증가하면서 (a[]의 모든 원소마다), 각 경우마다는 첫번째 수 a[i]를 정하고, 인덱스를 1씩 늘려가면서(a[i+1] ... ) 첫번째 수보다 큰 숫자들을 컨테이너(sub_a[])에 담습니다. 2) sub_a를 1)번 과정을 되풀이하는 재귀함수를 구현합니다. a[] = {3, 2, 1, 7, 5, 4, 2, 6} 첫번째 원소 3을 기준으로, 그 다음 가능한 7 5 4 6 중 다시 재귀적으로 LIS를 뽑습니다. #include #include using namespace std; /* LIS의 길이를 반환 */ int.. 2019. 9. 6.
[SW] 8382 방향전환 쉬운 문제, 규칙을 찾는 문제. #include inline int abs(const int& a){ return a >= 0 ? a : -a; } int main() { int T; scanf("%d", &T); int x1, y1, x2, y2; for (int i=1; i ady) ans = 2 * ady; else ans = 2 * adx; int line = abs(adx - ady); if (line % 2) ans += 2 * line - 1; else ans += 2 * line; } printf("%d\n", ans); } return 0; } 2019. 9. 6.
[SW] 7732 시간 개념 인풋을 잘 나누어 받고, 자리수를 조정하여 계산할 수 있다면 쉬운 문제에 속한다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; string current, appointment; int ctime[3]; int atime[3]; int ans[3]; for (int i=1; i> current >> appointment; for (int j = 0, k = 0; j < 7; j += 3, ++k) { ctime[k] = stoi(current.substr(j, 2)); atime[k] = stoi(appointment.substr(j, 2)); .. 2019. 9. 5.
[정렬] sort 버블정렬, 선택정렬, 삽입정렬, 쉘정렬, 병합정렬, 퀵정렬, 힙정렬, 계수정렬, 기수정렬까지... 많은 정렬들을 직접 구현해봤지만, 결국 실전에서는 이것들을 일일이 구현할 순 없다. 물론, 다 외워서 할 수 있으면 정말 좋긴 할 것이다. 실전에서 만약 정렬이 필요하다면, #include sort(v.begin(), v.end()); stable_sort(v.begin(), v.end()); STL함수를 써야할 것이다. sort 여기 있는 sort함수는 introsort라는 하이브리드 기법을 썼다고 한다. 불안정한 quick sort가 아니라서 다행이다. 시간복잡도 O(NlogN)을 보장한다. stable_sort 또한 중복되는 key에서 각 key가 가진 다른 값도 정렬하고 싶을 때는 stable_sor.. 2019. 9. 2.
[Sort] 대표적인 정렬의 모든 것 정렬(Sort) 비교정렬(Comparision Sort) 비교하여 정렬하는 방법은, 아무리 알고리즘을 잘 짜도 O(NlogN)보다 크다. 그렇지만, O(NlogN)도 충분히 빠른 정렬이고, 일반적인 경우에 대해 정렬할 수 있는 방법이기 때문에 이를 공부하는 것은 중요하다. O(N2) 정렬 1. 버블 정렬(Bubble sort) 장점 : "순서대로 대소 비교 후 큰 것을 뒤로 보낸다."를 그대로 구현하면 되기 때문에, 코드가 보기에 직관적이므로 구현이 쉽다. stable 정렬이다. 단점 : 최악이든 최선이든 O(N2)이기 때문에 굉장히 비효율적이다. 2. 선택 정렬(Selection sort) 장점 : "최댓값을 찾고, 맨 뒤의 원소와 바꾸어준다"를 그대로 구현하면 된다. 구현이 쉽다. 원소 교환 횟수가 .. 2019. 8. 31.
[KMP] 문자열 알고리즘 KMP algorithm KMP (Knuth-Morris-Pratt) 알고리즘 문자열 검색, 짚더미(Haystack, H 문자열)에서 바늘(Needle, N 문자열)을 찾아봅시다! 불일치가 일어났을 때 지금까지 일치한 글자 수를 이용해 다음으로 시도해야 할 시작 위치를 빠르게 찾아냅니다. 필요한 것: 부분 일치 테이블(partial match table) p[i] 를 만듭니다. pi[i]는 문자열 N[...i] (문자열 처음부터 i번째 까지 문자열)의 접두사도 되고 접미사도 되는 문자열의 최대 길이입니다. 예를들면 "aabaaba"에서 aaba는 접두사도 되고 접미사도 되는 최대 길이 문자열이므로, pi[6] = 4 입니다. KMP 알고리즘의 전체 반복문 수행 횟수는 O(|H|) 입니다. #include.. 2019. 8. 30.
[이진탐색] 1920 수 찾기, Binary search Binary search는 '정렬된 배열'에서 특정 원소를 찾을 때, O(logN)의 탐색시간을 보장합니다. 따라서, O(N)만큼 걸리는 Linear search 보다는 성능이 좋을 수 있습니다. 처음에는 재귀함수로 구현하였고, 이와 거의 비슷하게 반복문으로 구현할 수 있었습니다. #include #include int a[100001]; // array는 정렬되어 있어야 함. int binarySearch(int first, int last, int k){ int mid = (first + last) / 2; if (first > last) return -1; else { if (a[mid] == k) return mid; else { if (a[mid] < k){ binarySearch(mid + 1.. 2019. 8. 29.
[Deque] 5430 AC (백준) Deque의 성질을 잘 활용해야 하는 문제. 이것을 데크를 무시하고, 리버스를 처음에 그대로 구현했다가.. 시간초과가 났다. p의 길이의 합과 n의 합이 70만을 넘지 않다는 것이지... p x n 이 70만을 안 넘는 것은 당연히 아니었다. 리버스 있는 그대로 해서 하는 순간 reverse가 O(N)이라고 가정하면, 전체 수행시간이 O(PN)이 되어 10억, 즉 10초 정도로 시간초과가 난다. 그래서, 아이디어는 리버스했을 때 front인지 rear인지 설정을하고 각각 pop_front, pop_back을 해주면된다. 개념적으로는 참 쉬운데, 문자열 다루는데 익숙하지 않았던지 푸는데 너무 오래걸렸다. string 객체의 substr을 잘 이용해보았다. string s; s = "2019.08.28" i.. 2019. 8. 28.
[Deque] 1021 회전하는 큐 문제에 나온 그대로 하면 풀리는 문제이다. M 2019. 8. 27.
728x90