💻 컴퓨터

다항시간 알고리즘의 뜻 최악의 경우 시간복잡도의 상한을 다항함수의 꼴로 표현할 수 있는 모든 종류의 알고리즘 해를 얻었다는 것은 그 해에 대한 검증이 이미 끝났다는 것을 의미 모든 P-문제는 자명히 NP-문제 P-문제(Polynomial) - 문제에 대한 해를 도출하는 다항시간 알고리즘이 하나 이상 존재하는 경우 NP-문제(Non-deterministic Polynomial) - 문제에 대한 해를 검증하는 다항시간 알고리즘이 하나 이상 존재하는 경우 NP-문제가 P-문제를 포함함 P-NP 문제의 이해 P-문제와 NP-문제의 포함관계? 정의로부터 NP가 상위인 것은 분명, 가능한 경우는 서로 같은 것이거나 같지 않은 경우 NP-난해 문제 다음의 조건을 만족하는 X NP 클래스에 속하는 모든 문제를 다항시간..

확률적 관점에서의 소수 판별 Q. 자연수 n을 입력받아서, n이 소수인지 아닌지 판단하는 프로그램에서, 결정론적 알고리즘에 대응되는, 무작위 알고리즘의 개념 Deterministric Algorithm 동일한 입력에 대하여, 매번 동일한 결과를 출력하는 형태의 알고리즘으로, 확률과 무작위성이 개입하지 않음 ex. 자연수 N이 소수인지 판별하기 위해, 2,3,4, - - - 루트N까지의 수로 나눠봄 Randomized Algorithm 확률과 무작위성이 개입함으로써 동일한 입력에 대해서도 다른 결과가 나타날 수도 있는 형태의 알고리즘 ex. Miller-Rabin 소수 판별법, Pollard-Rho 알고리즘을 이용한 소인수분해 오일로 정리로 얻을 수 있는 소수의 특성 → Miller-Rabin 소수 판별법..

연관분석 알고리즘과 그 개선 지지도 Support : 전체 사례 대비, 해당 항목이 등장하는 사례의 비율 Apriori Algorithm에서 수행하는 기능은? 빈번히 발생하는 세트 확인 가지치기 연관된 규칙 생성에 용이 신뢰도 confidence : A를 포함하는 사례 중, B까지 포함하는 사례의 비율 높은 신뢰도를 보이는 연관규칙은 반드시 유의미할까? 향상도 lift : 연관규칙 A⇒B에 대한 신뢰도를 B의 지지도로 나눈 값 정방향, 역방향 모두 같은 향상도를 가짐 Apriori Algorithm 사전에 지정한 최소 지지도보다 높은 지지도를 갖는 모든 조합을 알아내기 위한 방법 중 하나 확장과 가지 치기를 반복함으로써 완전 탐색보다 효율적으로 조합들을 탐색 확장 - 크기 1의 후보군들을 모아 크기 2의..

집합의 분할과 스털링 수 그룹의 순서와 그룹 내 원소의 순서는 중요하지 않은 상황 서로 다른 열 개의 팀을 네 그룹으로 빈 그룹 없이 나누는 방법은? 제2종 스털링 수를 구하는 프로그램 S = list() n = 10 k = 4 for i in range(0, 100): new_list = list() for j in range(0, 100): new_list.append(-1) S.append(new_list) for i in range(1, n+1): for j in range(1, i+1): if (j == 1 or j == i): S[i][j] = 1 else: S[i][j] = S[i-1][j-1] + (j*S[i-1][j]) print(S[n][k]) 카탈란 수의 뜻과 그 응용 Catalan ..

직선에 대한 점의 좌우 판별 Q. 세 점이 있을 때, 두 점을 연결한 반직선을 기준으로 좌우를 판별할 수 있는가? → 벡터의 외적을 이용한 직선에 대한 점의 좌우 판별 가능 def LP(A,B,C): result1 = (A[0]*B[1]) + (B[0]*C[1]) + (C[0]*A[1]) result2 = (B[0]*A[1]) + (C[0]*B[1]) + (A[0]*C[1]) result = result1 - result2 if (result > 0): return 'LEFT' elif (result < 0): return 'RIGHT' else: return 'S' 볼록 껍질 문제에 대한 해법 그레이엄 스캔 - 볼록 다각형, 오목 다각형 구분 주어진 모든 점들 중, 가장 왼쪽의 점을 기준점으로 설정 (..

백트래킹을 이용한 해의 탐색과 그 실제 조합 및 순열 문제: 서로 다른 요소들의 모든 조합이나 순열을 생성할 때 사용됩니다. N-Queens 문제: N×N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제를 해결할 때 사용됩니다. 수도쿠: 주어진 조건을 만족하는 수도쿠 보드를 완성하는 데 사용됩니다. 그래프 색칠 문제: 그래프의 정점을 최소한의 색상으로 색칠하는 방법을 찾는 문제 해결에 사용됩니다. 백트래킹과 효율적 해 탐색 Q - 여섯 명을 중복 없이 한 명씩 나열하는 경우를 모두 출력하는 프로그램? → 6^6 중, 중복되지 않는 경우만 추출해 나열 vs 중복된 수를 제외하면서 나열 Backtracking 가능한 모든 해를 탐색, 조건에 어긋나는 경우 이전으로 돌아가는 기법 어떤 지점이 해의..