CS46 [프로그래머스] 요격 시스템 python 문제 A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, .. 2023. 6. 9. [Python] 소수 판별(IsPrime) 알고리즘 / 에라토스테네스의 체, 나누기 소수(Prime Number)란? 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 나누기를 통해 정의에 의해 나누기를 사용하여 구현할 수 있다. n이라는 수가 소수인지 판별하는 코드를 구현해보자. 1은 소수가 아니다. 시간 복잡도를 위해 $\sqrt(n) + 1$까지만 탐색한다. def isPrime(n): if n == 1: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True print(isPrime(1)) # False print(isPrime(11)) # True print(isPrime(12)) # False print(isPrime(13)) # True 에라토스테네스의 .. 2023. 5. 12. [프로그래머스] N개의 최소공배수 python / 최대공약수, 최소공배수, 유클리드 호제법 나이가 드니,.. 최소 공배수가 뭐더라 최대공약수가 뭐더라,.... 암튼 해당 알고리즘이 바로바로 생각날 수 있도록 문제를 기록한다 ! 최대공약수(Greatest Common Divisor, GCD) 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. 두개의 자연수를 1~N까지 나누어 공통되는 것을 찾아 그 중 max 값을 구하면 구할 순 있겠지만 ! 높은 시간 복잡도를 가진다. 이에 최대공약수를 간단하게 풀 수 있는 유클리드 호제법을 사용한다. 유클리드 호제법: 2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 코드로 구현하면 아래와 같다. def gcd(a, b): while b: r = a % b a,.. 2023. 5. 10. [프로그래머스] 다음 큰 숫자 python 문제 문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. 제한 사항 n은 1,000,000 이하의 자연수 입니다. 풀이 $O(N)$으로 풀어야 한다. 처음엔 아래와 같이 직접 2진수 변환을 하고, list로 변환하여 1을 세는 등... 다양한 바보같은 짓을.. 2023. 5. 10. 이전 1 2 3 4 ··· 12 다음
