본문 바로가기

CS/Coding Test42

[프로그래머스] 요격 시스템 python 문제 A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, .. 2023. 6. 9.
[프로그래머스] 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.
[백준] 19637: IF문 좀 대신 써줘 python 구현 / 이분 탐색(bisect) 문제 게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다. 예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다. 혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자. 입력 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ $10^5$)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ $10^5$)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ $10^5.. 2023. 5. 8.

티스토리툴바