본문 바로가기

분류 전체보기74

[프로그래머스] 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.
10진수 n진수 변환, n진수 10진수 변환 진수 문제가 나오면 항상 내장 함수를 찾느라 시간이 좀 걸렸다..! 해당 내용을 정리해보기로 한다 ! 10진수에서 n진수 변환 10진수 > 2진수, 8진수 16진수 python에서는 2진수, 8진수, 16진수 변환을 위한 bin, oct, hex 메서드를 지원한다. 주의할점은 앞 두 글자는 진법 표시를 위해 있다는 점 ! bin(11)[2:] 와 같이 얻을 수 있다. print(bin(11)) print(oct(11)) print(hex(11)) # 0b1011 # 0o13 # 0xb 10진수 > n진수 혹은 함수작성을 통해 원하는 진법으로 변환이 가능하다. def convert(n, base=2): T = '0123456789ABCDEF' q, r = divmod(n, base) if q == 0: r.. 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.

티스토리툴바