본문 바로가기

💻 알고리즘

 (215)
[ 2022 KAKAO 블라인드 ] k진수에서 소수 개수 구하기 (Python, 파이썬) https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 💕풀이 방법 이번 문제는 아래 두 가지 함수를 만들어 문제를 풀어냈다. 1️⃣ convert(n, k) - 10진수인 n을 k진수로 변경하는 함수 - divmod() 함수를 사용해서 n을 k로 나눈 몫과 나머지를 구한다. 그리고 num에 나머지를 저장해준다. (이 과정을 n이 0이 될 때까지 반복함) * 10진..
[ 백준 ] 1747 소수&팰린드롬 (python) https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 🔥 문제 풀이 문제를 처음 읽고 n의 범위가 너무 크지만, 소수이면서 가장 작은 팰린드롬 숫자를 찾는 것이기 때문에 while 문을 통해서 n을 1씩 증가하면서 소수인지 && 팰린드롬 숫자인지 확인해주면 된다고 생각했다. 그래서 isPrime 함수를 만들어 소수인지 확인하고, 소수라면 팰린드롬 숫자인지 확인할 수 있도록 구현해줬다. 👀 위에서 설명한 대로 구현..
[ 백준 ] 21919 소수 최소 공배수 (python) https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 🔥 문제 풀이 처음 문제를 보고 주어진 a 리스트 중에서 소수인 값들을 찾아서 list에 담은 후, 숫자를 두 개씩 뽑아서 최소 공배수를 구하도록 구현을 해줬다. 이렇게 구현해줬더니시간 초과가 발생함..😥 그래서 시간을 줄일 수 있는 방법을 생각하다가 소수인 숫자들끼리의 최소 공배수면 겹치는 숫자 없이 서로 곱하기만 하면 최소 공배수가 완성된다는 것을 깨달았다!! 즉, 굳이 소수인 숫자를 두 개씩 골라서 최소공배수 구하고, 다시 다른 숫자와의 최소공배수를 구하고.. 이런 과정들이 필요가 없이 모든 수를 곱해주면 된다는 뜻이다! ex) [..
[ 백준 ] 21275 폰 호석만 (python) https://www.acmicpc.net/problem/21275 21275번: 폰 호석만 만약 문제의 조건에 맞는 X, A, B가 유일하게 존재한다면, X를 십진법으로 표현한 수와 A와 B를 공백으로 나누어 출력하라. 만약 만족하는 경우가 2가지 이상이라면 "Multiple"을, 없다면 "Impossible"을 www.acmicpc.net 🔥 문제 풀이 이 문제는 10진수인 X를 i진수로 변경한 a, j진수로 변경한 b를 입력받아서 i와 j를 구하는 문제다. 이번 문제는 [ 백준 ] 2745 진법 변환 (python) 이 문제와 비슷하다고 생각한다. index() 함수를 이용하는 것과 n진법을 10진법으로 풀어내는 과정 등 비슷한 부분이 많기 때문에 만약 2745번 문제를 풀어보지 않았다면, 먼저 풀..
[ 백준 ] 21920 서로소 평균 (python) https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 🔥 문제 풀이 * 서로소 : 최대 공약수가 1인 두 자연수 주어진 x와 수열 a의 원소들이 각각 서로소인지부터 구해야 하기 때문에 gcd 함수를 만들어 최대공약수가 1인지 아닌지 판단하도록 했다. 그리고 서로소인 값들의 평균을 구하기 위해서 간단하게 print(sum(res)//len(res)) 입력해 줬는데 실행 결..
[ 백준 ] 4134 다음 소수 (python) https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 🔥 문제 풀이 처음 문제를 보고 주어진 수(n) 보다 같거나 큰 소수를 찾는 문제여서 주어진 최대 숫자까지 범위를 잡고 소수를 구하는 중에 주어진 n보다 같거나 큰 첫 번째 수를 출력하려고 했다. ( 작은 수부터 확인을 하기 때문에 같거나 처음 커진수에서 소수 값을 출력하고 break 하면 된다고 생각함 😥) 그래서 생각한대로 구현을 했더니 주어진 범위가 너무 커서 OverFlowError가 발생함 따라서 정답을 맞추기 위해서 다른 방법으로 접근했다. 주어진 숫자 n이 소수인지 ..
[ 백준 ] 2960 에라토스테네스의 체 (python) https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 🔥 문제 풀이 문제를 읽고 에라토스테네스 체를 사용해서 최대 범위인 1000까지 소수를 구해놓고, 그 소수들의 순서가 k - 1번째 일 때 값을 출력하면 되겠다고 생각했다.( 리스트는 0부터 시작하므로 k -1번째 값을 출력해야 우리가 원하는 답을 찾을 수 있음 ) 그래서 늘 풀어왔던 방법대로 소수인지 확인하는 범위를 int(math.sqrt(n)) + 1 로 잡아서 소수를 모두 리스트에 담아서 문제를 풀었더니 틀림..😱 두 번째 예제에서 원하는 값이 나오지 않았다😥 ( 👀 에라토스테..
[ 백준 ] 2745 진법 변환 (python) https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 🔥 문제 풀이 이문제는 2진법을 10진법으로 바꿔주는 방법을 생각하면 쉽게 문제를 풀어낼 수 있다. ex) 이진법 수인 1010을 10진법으로 바꾼다고 생각해보자. 그러면 0의 자리부터~ n의 자리까지 (자리 숫자 * 2**n)을 해줘서 합치면 10진법 숫자인 10이 된다. 위와 같은 방법으로 이번 문제도 풀어내면 된다. 문제에서 주어진 예시로 확인해보면. 36진법으로 만들어진 'ZZZZZ' 를 1..

티스토리툴바