본문 바로가기

알고리즘37

[알고리즘] 14. P-NP 문제와 알고리즘의 내일 1. 다항시간 알고리즘의 뜻1) Polynomial-Time Algorithm최악의 경우 시간복잡도의 상한을 다항함수 꼴로 표현할 수 있는 알고리즘  2) P-문제  Polynomial문제에 대한 해를 도출하는 다항시간 알고리즘이 하나 이상 존재하는 경우예) 정렬 문제  3) NP-문제 Non-deterministic Polynomial문제에 대한 해를 검증하는 다항시간 알고리즘이 하나 이상 존재하는 경우예시) 정수 N개 집합에서 부분집합의 합이 k인 부분집합 찾기모든 부분 집합의 개수 2^N 다 확인해야함 -> O(2^N) 검증한다 : 정수 N개 집합에서 부분집함의 합이 0이 되는 부분집합이 있는가? 의 질문에 {5, -5}로 다항 시간 내 OX 판정 가능한가? -> 가능. O(1){5, 2} 로 판정.. 2024. 12. 13.
[알고리즘] 10. 기하 알고리즘 KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.10주차. Python을 이용한 기하 알고리즘 입문 10주차. Python을 이용한 기하 알고리즘 입문 1.  직선에 대한 점의 좌우 판별1) 벡터의 외적을 이용한 직선에 대한 점의 좌우 판별점 A(x1, y1), B(x2, y2), C(x3, y3) 이 좌표평면 위에 주어져 있을 때, 반직선 AB-> 에 대한 점 C의 상대적 위치는 아래와 같이 판단할 수 있다.(x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3) 이 양수면 왼쪽, 음수면 오른쪽, 0이면 나란하게 있다. # Week 10# LRdef LR(A, B, C): result1 = (A[0]*B[1]) + (B[0]*C[1]) .. 2024. 12. 13.
[알고리즘] 9. 백트래킹 KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.9주차. 백트래킹을 이용한 해의 탐색과 실제 9주차. 백트래킹을 이용한 해의 탐색과 실제 1.  백트래킹과 효율적 해 탐색1) 백트래킹(1) 백트래킹 이란?가능한 모든 해를 탐색하되, 조건에 어긋나는 경우 이전으로 돌아가는 방법 (-> 이부분이 Brute-Force와 차이)어떤 지점이 해의 조건에 위배되었을 경우, 해당 지점보다 깊은 해는문제 해결에 있어, 일반적인 완전 탐색 알고리즘보다 높은 성능을 기대할 수 있다. Tree에서 DFS와  관련있다. (2) 문제 예시(순열) 한 줄로 서기 -> 앞에 선 사람은 뒤에 설 수 없으므로 이전으로 돌아감. # Week 9# Line-up (Back-Tracking)member .. 2024. 12. 13.
[BOJ | Python] 3344 N-Queen 백준 3344 N-Queenhttps://www.acmicpc.net/problem/3344 시도 1 : 백트래킹 (실패)백트래킹 예제 풀다가 변형해서 제출했는데 N 최대가 99999라서  시간 초과가나온다. N = int(input())ans = []for i in range(0, N): ans.append(-1)def queen(num): if check(num) == True: if num == N: for a in ans: print(a+1) exit(0) else: for j in range(0, N): ans[num] = j .. 2024. 12. 12.
[알고리즘] 7. 암호화 알고리즘 KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.7주차 기초 정수론과 암호화 알고리즘7주차. 기초 정수론과 암호화 알고리즘 1. 고전적 암호화 방법과 한계1) 고전적 암호화 방법(1) 시저 암호 Caesar Cipher암호화 방식① 알파벳 A를 00으로, B를 01로, ... , Z를 25로 대응시킴② 평문에 모든 알파벳을 동일한 칸수만큼 미는 방식으로 암호화③ 알파벳이 26개이므로 26으로 나눈 나머지를 사용예시평문KOREA101417040013칸 미룬 암호문XBERN2301041713 (2) 아핀 암호 Affine Cipher암호화 방식평문 P와 암호문 C에 대응하여 다음 방식으로 암호화C ☰ K1P+K2 (mod 26)K1 = 3, K2 = 2 2) 시저, 아핀.. 2024. 12. 4.

티스토리툴바