Algorithm
-
백준 1305 광고Algorithm/BOJ(백준) 2018. 9. 6. 21:23
문제 링크 : https://www.acmicpc.net/problem/1305※선행해야 할 알고리즘 : KMP Algorithm Algorithm : 문자열의 pattern table을 구한 후 그 해당하는 pattern table값을 문자열 길이에서 빼준다. 1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음. 2. 예를 들어aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉, baaa가 원래 광고..
-
백준 1701 CubeditorAlgorithm/BOJ(백준) 2018. 9. 6. 16:28
문제 링크 : https://www.acmicpc.net/problem/1701※선행해야 할 알고리즘 : KMP Algorithm Algorithm부분 문자열마다의 pattern_table을 생성하여 그 중 값이 가장 큰 것을 return 한다.(해당 내용 : KMP Algorithm 참고) 1. 여기서 말하는 "부분 문자열" 마다의 의미는 예제 입력 "abcdabcabb"을 기준으로 다음과 같다. (1) abcdabcabb (부분 문자열 1) (2) bcdabcabb (부분 문자열 2) (3) cdabcabb (부분 문자열 3) . . . (10) b (부분 문자열 10) 2. "pattern_table"의 의미는 다음과 같다.문자열의 모든 부분 문자열의 접미사와 접두사가 같은 문자열의 문자 개수들을 ..
-
알고리즘 학습 방법Algorithm/이론 2018. 9. 6. 14:58
※ 알고리즘 학습 방법 순서도(커리큘럼) 1. 알고리즘과 입/출력2. 자료구조 1- 큐/스택/데크- 문자열3. 다이나믹 프로그래밍 14. 알고리즘 수학 1- GCD/LCM- 소수5. 정렬6. 그래프 1- 정의와 표현방법- 탐색 (DFS/BFS)- 모델링7. 트리 1- 순회- 저장- 트리와 관련한 알고리즘8. 그리디9~10. 분할 정복- 이분 탐색- 머지 소트/퀵 소트- 가장 가까운 두 점11~12. 완전 탐색- 비트마스크- 순열- 부르트 포스- 백트래킹13. 자료구조 2- 스택 2- 서로소 집합(Disjoint-Set)- 힙과 힙 소트- 이진 탐색 트리 (BST)14. 다이나믹 프로그래밍 2 15. 수학 2- 분할 정복- 이항 계수- 카탈란 수- 오일러 피 함수- 확장 유클리드 알고리즘16. 그래프 2-..