본문 바로가기
SMALL

Coding Test/SWEA18

[Advanced] 12. NP-Complete - 이론편 P와 NP P : 다항식 시간 알고리즘이 존재하는 모든 결정 문제의 집합 NP : 다항식 시간 비결정적 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합 어떤 문제들이 어려운 문제일까요? 다항식 시간이 필요하면 현실적인 시간 지수시간 이상이 필요하면 비현실적인 시간으로 "어려운 문제"에 해당 → 다루기 힘든(Intractable) 문제 문제의 분류 다항식 시간 알고리즘을 찾은 문제 다루기 힘들다고 증명된 문제 다루기 힘들다고 증명되지 않았고, 다항식 시간 알고리즘도 찾지 못한 문제 1. 다항식 시간 알고리즘을 찾은 문제 다항식 시간이 아닌 알고리즘도 있으나, 다항식 시간 알고리즘을 찾은 경우 정렬문제 O(nlogn) P(Polynomial) 문제 집합 정렬된 배열 검색 O(logn) 행렬 곱셈 O(n^.. 2021. 8. 5.
[Advanced] SW 문제해결 응용 - 구현 - 완전검색 1. 완전 검색 - 최적해 문제 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것 완전 검색 알고리즘 → 중복 제거 → 개선된 알고리즘 완전 검색 알고리즘 → 분할정복, 동적 계획법 ex) 베이비진 문제 2. 조합적 문제 - 경우의 수 문제 순열 : 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 다수 문제들이 순서화된 요소들의 집합에서 최선의 경우를 찾는 것 순회 외판원 문제 (Traveling Salesperson Problem) 방문할 도시가 n개라면 가능한 모든 경로는 n! 만큼 존재 → 12이상부터 폭발적 증가! 존슨-트로터 알고리즘 : 교환을 통해 순열 생성 조합 : 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 재귀 호출을 이용한 조합 생성 알고리즘 부분집합.. 2021. 8. 5.
[Advanced] 11. 동적 계획법의 활용 - 이론편 최장 증가 수열 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 나열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제 부분 수열의 요소들은 연속적이거나 비연속적 3, 2, 6, 4, 5, 1 최장 증가 수열은 2, 4, 5 길이는 3 3, 4, 5도 길이가 3인 최장 증가 수열이 됨 완전 검색 적용 수열의 모든 부분 집합 구함 → 해당 부분 집합의 증가 수열 여부 판별 → 증가 수열 중 가장 길이가 긴 값을 구함 시간 복잡도 : O(2^n) 알고리즘 수도 코드 # S : 수열 for i in range(N, 0, -1): for ALL subsequence of S with length of i: if there is one increasing subsequence: .. 2021. 8. 4.
[Advanced] 10. 동적 계획법의 적용 - 이론편 0-1 배낭 문제에 동적 계획법 적용하기 배낭문제(Knapsack) ❔ 문제 : 도둑이 물건을 훔치기 위해 보관 창고에 침입 → 물건은 배낭에 담음(배낭은 담을 수 있는 물건의 무게가 고정) → 창고에는 여러개의 물건들이 있고 각각의 물건에는 무게와 값이 정해져 있음 → 경비원들에게 발각되기 전에 배낭의무게를 초과하지 않으면서 값의 총합이 최대가 되도록 물건을 선택해서 담기. 즉, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값의 총합이 최대가 되도록 하려면? S = {item1, item2, ... ,itemn} wi = itemi의 무게, Pi = itemi의 값 W = 배낭이 수용가능한 무게 완전 검색 방법 +완전 검색으로 집합 S에 대한 모든 부분집합을 구함 총 무게가 W보다 큰 부분집합 제.. 2021. 8. 2.
[Advanced] 9. 동적 계획법의 소개 - 이론편 피보나치 수열 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열 0, 1, 1, 2, 3, 5, 8, 13, ... → f(n+2) = f(n) + f(n+1) 함수 f의 정의로부터 피보나치 수열의 n번째 항을 반환하는 함수를 재귀함수로 구현 def fibo(n): if n=2 and memo[n]==0: memo[n] = fibo(n-1) + fibo(n-2) return memo[n] 메모이제이션 문제점 : 추가적인 메모리 공간 필요, 재귀함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우 발생 동적 계획법 탐욕 기법과 같이 최적화 문제(최대나 최소를 찾는)를 해결하는 알고리즘 완전검색을 좀 더 효율적으로 하는 방법 재귀 + 메모이제이션 점화식을 찾으면 됨.. 2021. 7. 31.
[Advanced] 8. 문자열 탐색 - 이론편(3) 트라이 (trie) 정보검색(Retrieval)에 사용된 자료구조로 문자열의 집합을 표현하는 트리 각 간선은 하나의 문자에 대응 같은 노드에 나오는 간선들은 같은 라벨을 갖지 않음 각 문자열은 단말 노드에 대응 접미어 트라이 문자열의 모든 접미어를 트라이로 표현 길이가 n인 문자열의 접미어는 n개 접미어 트라이의 장점 부분 문자열 검사 - "ba"가 "abac"의 부분 문자열인가? 두 접미어의 최장 공통 접두어 찾기 - "abac"와 "ac"의 최장 공통 접두어는 무엇인가? 두 접미어의 끝 글자에 해당하는 노드 선택 가장 가까운 공통 조상 찾음 사전적 순서로 정렬된 k번째 접미어 찾기 - "abac"에서 사전적 순서로 3번째 접미어는 무엇인가? 깊이 우선 탐색으로 문자열들을 생성하면 사전적 순서로 정렬 .. 2021. 7. 30.
LIST

티스토리툴바