본문 바로가기
728x90
[알고리즘 개념정리] 6. 완전탐색/백트래킹 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 완전 탐색(Brute Force) : 모든 경우를 탐색해 가면서 무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법 ★ 완전 탐색 문제 판별법 하나의 경우마다 따져야 할 게 명확한 경우 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 적은 경우 (N제한이 작을 때!!) ★ 완전 탐색 문제 접근법 모든 경우(상태)를 생성할 수 있는 방법을 생각한다. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크한다. * 문제에 따라 모든 경우를 따질 필요가 없거나 각 경우에 대해 체크할 조건이 없는 등의 상황도 있다.. 2022. 1. 29.
[알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱) **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** Stack 후입 선출(LIFO) 선입 후출(FILO) push, pop, top, isEmpty * isEmpty가 True일 때 pop하면 Underflow * 배열 vs 스택 배열: 임의의 위치에 random access O(1) 동적배열이 아닌 이상 static한 환경에서 append 불가능 스택: top에만 접근 O(1) 한쪽 끝에서만 추가/삭제 일어나는 구조가 필요한 케이스에 유용 ex) infix -> postfix로 바꾸기, 최근 행위 undo하기 Queue 선입 선출(FIFO) Enqueue, Dequeue, Front, Rear, isEmpty * isEmpty가 True일 때.. 2022. 1. 27.
[알고리즘 개념정리] 4. 그리디 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 그리디 알고리즘 : 부분적인 최적 전략을 반복적으로 취하는 알고리즘 당장 보이는 이득을 좇아가는 것도 이 알고리즘의 일부! ★ 그리디 문제 판별법 부분적인 최적 전략을 반복적으로 취해서 답을 구할 수 있는 문제 부분 문제에 대해 구한 최적해들이 모두 전체 문제의 최적해의 일부인 문제 ★ 그리디 문제 접근법 문제의 상황이 그리디 알고리즘에 적합한지 살펴본다. 어떤 기준으로 순서를 세워, 그 순서대로 처리하면 이득이 되는지 생각해본다. 직관 혹은 증명을 통해 어떤 기준이 확실하다면 구현한다. -> 만약, 그 기준이 보이지 않는다면 DP 등 다른 풀이를 생각해보자. 그리디 문제 유형은 크게 다음과 같이 나누어.. 2022. 1. 22.
[알고리즘 개념정리] 3. 동적계획법(DP) **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** Dynamic Programming : 전체 문제를 작은 부분 문제(subproblem)로 나누어 푸는 방법 -> DP, 분할 정복,... 중복되는 부분 문제는 한 번만 계산 메모이제이션 : memoization 배열 -1로 초기화, 배열 값 음수이면 계산 후 저장, 양수이면 저장해둔 값 재활용 기저 조건(Base Case) 설정 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해로부터 구해짐. ★ DP 문제 판별법 문제를 읽는다. 입력 조건 & 시간제한 & 메모리 제한을 확인한다. ex) 입력 조건 : 상태 개수를 정의. k=100, n=100000 -> kn=10000000 정의할.. 2022. 1. 19.
[알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)+기초지식 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 긴 문자열 S[1...n]내에 패턴 P[1...m]이 부분 문자열로 등장 하는지 알아보자. S의 부분 문자열 중 길이가 m인 것의 개수는 n-m+1이다. 이를 각각 m글자씩 하나하나 확인하는 방법은 O(nm)에 가깝다. Polynomial Rolling hash 방법을 사용하면 O(n)에 해결할 수 있다. Polynomial Rolling hash 시간복잡도 : O(n) 방법 : 문자열을 정수로 치환하여 정수끼리 비교한다. p(X) = { p[0]*(X^m-1) + p[1]*(X^m-2) + ... + p[m-1]*(X^0) } mod M // p(x) 는 P[1...m]을 정수화 시킨 값 S.. 2022. 1. 16.
[알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** sort 함수 시간복잡도 : O(nlogn)을 보장함. 정렬방식 : 퀵정렬 원소 개수가 특정 이하이면 삽입정렬, 중간이면 퀵정렬, 이상이면 힙정렬 사용 오름차순 정렬 sort([배열의 시작 주소], [배열의 마지막 주소+1]); sort(arr,arr+N); 내림차순 정렬 방법 1. sort([배열의 시작 주소], [배열의 마지막 주소+1], greater ()); sort(arr, arr+N, greater()); 방법 2. sort() 후 reverse(); sort(arr, arr+N); reverse(arr, arr+N); 방법 3. compare함수 구현 bool compare (int a, i.. 2022. 1. 11.
728x90

티스토리툴바