[algorithm] 백준 단계별 문제 풀이 (약수, 배수와 소수 1탄)

[algorithm] 백준 단계별 문제 풀이 (약수, 배수와 소수 1탄)

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 약수, 배수, 소수에 대한 문제들로 구성해 보았습니다.

 

파이썬3 를 사용해 문제 풀이를 진행하겠습니다.

 

문제마다 링크를 걸어두었으니 문제를 살펴보시고 문제를 푼 다음에 저와

 

풀이를 비교해 보시는 걸 추천드립니다.

차근차근 풀어봅시다.

 

알고리즘

---

백준 BAEKJOON 5086

 

https://www.acmicpc.net/problem/5086

 

5086번: 배수와 약수

 

문제 해석

 

각 줄마다 두 개의 숫자가 주어지는 첫 번째 숫자가 두 번째 숫자의 약수, 배수, 둘 다 아닌지를 출력하는 문제

 

풀이

 

while True:
    a, b = map(int, input().split())
    
    if a == 0 and b == 0:
        break
    
    if b % a == 0:
        print('factor')
    elif a % b == 0:
        print('multiple')
    else:
        print('neither')

 

풀이 해석 및 팁

 

주어지는 두 숫자가 모두 0일 때 반복문이 멈추도록 설정해두고 무한루프를 돌립니다.

---

백준 BAEKJOON 2501

 

https://www.acmicpc.net/problem/2501

 

2501번: 약수 구하기

 

문제 해석

 

숫자 두 개가 주어질 때 첫 번째 숫자의 약수 중 두 번째 숫자 번으로 작은 약수를 출력하는 문제

존재하지 않을 경우 0을 출력

 

풀이 

 

a, b = map(int, input().split())

tmp = []

for i in range(1, a + 1):
    if a % i == 0:
        tmp.append(i)

try:
    print(tmp[b-1])
except:
    print(0)

 

풀이 해석 및 팁

 

tmp 리스트에 약수를 담은 후 익덱스로 접근해 약수를 출력합니다.

약수 리스트안에 원하는 번째의 약수가 존재하지 않을 경우를 대비해 try except 문을 활용합니다.

---

백준 BAEKJOON 9506

 

https://www.acmicpc.net/problem/9506

 

9506번: 약수들의 합

 

문제 해석

 

자신을 제외한 모든 약수의 합이 자신과 같다면 그 수를 완전수라고 부를 때

주어지는 수가 완전수인지 팔별하는 문제

 

풀이

 

while True:
    
    a = int(input())

    if a == -1:
        break
    
    tmp = []

    for i in range(1, a):
        if a % i == 0:
            tmp.append(i)

    if sum(tmp) == a:
        print(f'{a} = ', end = '')
        for i in range(len(tmp)):
            print(tmp[i], end = '')
            if i != len(tmp)-1:
                print(' + ', end='')
            else:
                print('')
    else:
        print(f'{a} is NOT perfect.')

 

풀이 해석 및 팁

 

tmp 리스트에 문제에서 주어진 수를 제외한 약수들을 담고 합이 주어진 수와 같을 때

약수들이 모두 보이도록 출력하고 그렇지 않을 때는 완전수가 아니라는 문구를 출력해 줍니다.

---

백준 BAEKJOON 1978

 

https://www.acmicpc.net/problem/1978

 

1978번: 소수 찾기

 

문제 해석

 

문제에서 주어지는 수들 중 소수가 몇 개인지를 출력하는 문제

 

풀이

 

n = int(input())
nlist = list(map(int, input().split(' ')))
prime = 0

for i in nlist:
    cnt = 0 
    if(i == 1):
        continue
    for j in range(2, i+1):
        if(i % j == 0):
            cnt += 1
    if(cnt == 1):
        prime += 1
print(prime)

 

풀이 해석 및 팁

 

주어진 수들을 리스트에 담고 각 요소마다 소수인지 검사를 실행합니다.

1은 소수가 아니므로 제외해야 하며, 나머지 수들에 대해 검사 후 소수의 개수를 카운팅 합니다.

---

여기까지 백준 단계별 문제풀이 약수, 배수와 소수 1탄의 풀이 내용이었습니다.

 

문제를 마주했을 때 어떤 식으로 풀어야겠다는 생각이 들지 않는다면 가장 기본적인 개념으로 접근해서

 

필요한 요소에 차근차근 풀어보시면 좋을 것 같습니다.

 

궁금하신 점이나 도움이 필요하신 분들은 댓글로 남겨주세요.

 

감사합니다.