본문 바로가기

Algorithm

 (30)
[Algorithm] Python : index 함수의 시간초과 해결법, Dictionary 이용 ! 백준의 좌표압축(18870)번 문제를 풀다가 시간초과로 한참 고민함 .. ㅠㅠ 문제는 생각보다 쉬웠다. 해결방법은 1. 입력받을 숫자개수(n)을 입력받고, 2. n개 만큼의 숫자를 list로 받은 후, 3. set으로 중복을 제거하고, 4. sort함수로 정렬한 후, 5. 기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력하면 된다고 생각했다. 근데, 여기서 시간초과가 발생한 것은 "기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력" 하는 부분이었다. 원하는 값의 index를 출력하는 index()함수의 시간 복잡도는 배열의 원소 하나하나를 따져야하기 때문에 O(n)의 시간복잡도를 갖는다. 따라서, 배열의 원소들을 각..
[Algorithm] NP-완전 문제 (2) 지난번 NP-완전 문제 (1) 포스팅에 이어서 계속한다. 저번 포스팅에서는 결정문제까지 다루었는데, 이번 포스팅에서 다룰 건 아래와 같다. NP-완전(NP-Complete, NP-완비) 문제를 이해하기 NP-완전 증명 방법을 이해하기 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합 NP-완전이라는 사실이 판명됨으로써 얻을 수 있는 이득을 이해하기 음 일단 그전에! P와 NP 문제를 이해해보자 1️⃣ 문제의 분류 ( P와 NP ) P : 다항식 시간복잡도를 가진 알고리즘으로 해결되는 (polynomial) 문제 집합 [결정문제 관점에서] 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합. 다항식 시간에 Yes 또는 No 대답을 할 수 있는 문제 전산학자들이 제안한 '풀기 쉬운' 문제의..
[Algorithm] NP-완전 문제 (1) NP-완전 이론 : 문제를 현실적인 시간에 풀 수 있는가에 관한 이론 복잡한 문제가 주어졌을 때, 고민할 것 답이 존재? 어떻게 답을 찾는가? 찾은 것이 올바른지 어떻게 검증? 쉬운문제 / 답은 구하는데 시간이 짧은 문제 어려운 문제 / 답을 구하는데 시간이 오래 걸리는 문제 풀 수 없는 문제 / 너무 어려워서 풀리지 않는 문제 아리송한 문제 / 어떤 집단 문제들은 어려워 보이기는 하지만, 그 답을 보면 옳다는 것을 검증하기가 쉬운 그러한 집단 문제 예) 퍼즐 맞추기 : 모나리자를 500조각 낸 퍼즐을 구입하여 짝을 맞추는 문제 : 문제를 푸는 것은 어렵지만, 답을 보고는 그것이 옳다는 것을 판정하는데 500 조각만 조사하면 됨으로 검증하기 쉽다. 이번 포스팅에서 다룰 것. 문제의 난이도 "다루기 힘든 ..
[Algorithm] Miller-Rabin Primality Test : 밀러-라빈 소수판별법 Miller-Rabin Primality Test : 밀러-라빈 소수판별법 임의의 수 a가 소수인지 아닌지를 확률적으로 판별해주는 알고리즘 이 알고리즘은 주어진 수 a이 소수임을 증명하지 않고, 소수가 아닐 확률(여사건)을 분석하여 소수를 판별함. 왜 확률적인가? a가 큰수이고, 소수 판별을 위해 먼저 2로 나누어 떨어지지 않는다고 가정한다면, 2, 4, 6, 8 등의 2의 배수인 수로도 나누어 떨어지지 않는다. 즉 이 수들에 대해서 검사할 필요가 없다. -> 전체 자연수에 대해서 50%의 숫자들을 검사한 효과! a가 3으로 나누어 떨어지지 않는다면 6, 9, 12 등의 수에 대해서도 검사할 필요가 없다. -> 전체 자연수에 대해서 33%의 숫자들을 검사한 효과 a가 5로 나누어 떨어지지 않는다면, 10..
[Algorithm] 기수 정렬 (Radix Sort) 기수정렬? 데이터끼리의 직접적인 비교 정렬이 아닌, 숫자를 부분적으로 비교하는 정렬방법 제한적인 범위 내에 있는 숫자에 대해서 낮은 자릿수부터 자릿수 별로 비교 정렬하는 알고리즘 어느 비교 정렬 알고리즘보다 빠른 큰 장점!! 기 (Radix)? 특정진수를 나타내는 숫자들 10진수의 기 : 0,1,2,3,4,5,6,7,8,9 2진수의 기: 0,1 🚫주의할 점 10의 자리가 같을 때 왜 035가 131 위에 위치하면 안되는 것인가? -> 1의 자리에 대해 정렬해 놓은 것이 아무 소용이 없게 되기 때문이다. ❗️정렬알고리즘은 안정성을 가진다. 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일하다. 💡RadixSort 알고리즘 (의사코드) 입력 : n개의 r진수의 k자리..

티스토리툴바