solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac
- Class 1에 해당하는 문제들을 모두 살펴보았습니다. 전반적으로 난이도 면에서는 그리 어렵지 않으셨을거라 생각합니다.
- Class 2부터는 본격적으로 브루트포스, 이분 탐색, 에라토스테네스의 체를 이용한 소수 판정, 그리고 다양한 자료 구조 등을 익힐 수 있게 됩니다.
- solved ac에서 제공되는 난이도에 따르면 Class 2에는 브론즈 3 문제부터 실버 2까지의 문제가 수록되어 있습니다.
- 이번 포스팅부터는 Github Gist를 활용하여 코드 스니펫을 삽입할 예정입니다. 또한 비교적 쉬운 난이도의 문제들을 다뤄보도록 하겠습니다.
4153번 : 직각삼각형
4153번: 직각삼각형
입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.
www.acmicpc.net
- 특정 삼각형에서 세 변의 길이가 주어지면 이 삼각형이 직각삼각형인지를 판단하는 문제입니다.
- 우선 세 변의 길이가 입력으로 주어졌을 때 이를 정렬한 뒤, 피타고라스의 정리를 활용하여 직각삼각형 여부를 판단하면 되겠습니다.
def check_right_triangle(a, b, c):
sides = sorted([a, b, c])
return 'right' if sides[0] ** 2 + sides[1] ** 2 == sides[2] ** 2 else 'wrong'
if __name__ == '__main__':
while True:
a, b, c = map(int, input().split())
if a == b == c == 0:
break
else:
print(check_right_triangle(a, b, c))
1978번 : 소수 찾기
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
- 주어진 수 중에서 소수의 개수를 찾는 문제입니다.
- 심화 과정이지만 시간 복잡도 측면에서 뛰어난 효율을 보이는 '에라토스테네스의 체' 알고리즘을 사용하였습니다.
- '에라토스테네스의 체' 알고리즘의 기본적인 로직은 다음과 같습니다.
1. 모든 숫자의 소수 여부를 저장하는 리스트와 소수들을 저장할 리스트 생성 (처음에는 0과 1을 제외한 모든 수를 소수라고 가정)
2. 범위를 순회하며 i 가 소수라면 i 를 소수 리스트에 저장
3. 나머지 i 의 배수들은 소수가 아니라고 표시 (True → False)
- 위 로직을 바탕으로 코드를 구현하고 최종적으로 소수인 것들의 숫자들을 카운트해주는 형식으로 풀었습니다.
def sieve_of_eratosthenes(max_num):
number = [False, False] + [True] * (max_num - 1)
primes = []
for i in range(2, max_num + 1):
if number[i]:
primes.append(i)
for j in range(i*2, max_num + 1, i):
number[j] = False
return primes
if __name__ == '__main__':
N = int(input())
num_list = list(map(int, input().split()))
max_num = max(num_list)
primes = sieve_of_eratosthenes(max_num)
print(sum(1 for num in num_list if num in primes))
알면 도움되는 코딩 테스트 유형: 12) #Primality_Test
이번 글에서는 소수 판정에 대한 개념과 코딩 테스트에서 소수 판정 문제를 해결하는 방법에 대해 알아보겠습니다. 소수는 많은 알고리즘 문제에서 자주 등장하는 중요한 주제 중 하나이므로,
injoycode.tistory.com
- 위 글을 통해서도 '에라토스테네스의 체' 알고리즘에 대하여 더 자세히 알 수 있습니다. 위 작동 방식과는 다를 수 있으나 로직은 같으니 참고하시면 도움이 될 것 같습니다. :)
- 아래는 간단한 시각화입니다. 특정 숫자 목록을 입력하면 그 중에서 소수를 판정해주는 방식으로 진행됩니다. ,(comma)로 구분하여 입력해주셔야 동작합니다!
2231번 : 분해합
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
www.acmicpc.net
- 위 문제는 분해합을 구하는 문제는 아니고, 입력되는 수의 분해합을 만드는 생성자를 찾는 문제입니다.
- 생성자를 찾는 로직은 다음과 같습니다.
1. 자연수를 입력
2. 해당 자연수까지의 모든 숫자를 확인 (이 때 각 숫자는 i)
3. 각 i 에 대하여 i 의 자릿수를 모두 sum
4. 그 후 i 와 sum 을 더하여 이 수가 입력된 자연수와 같다면 i 를 반환 (i 에 해당하는 수가 생성자)
- 위 로직은 완전 탐색이라고도 불리는 '브루트포스' 알고리즘을 적용시킨 것으로, 모든 경우를 탐색해야할 때 유용하게 사용됩니다.
def find_constructor(target):
for i in range(target):
temp = sum(map(int, str(i)))
if i + temp == target:
return i
return 0
if __name__ == '__main__':
N = int(input())
print(find_constructor(N))
2292번 : 벌집
2292번: 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌
www.acmicpc.net
- 주어진 방 번호에 도달하기 위한 최소 개수의 방을 출력하는 문제입니다.
- 벌집을 한 겹 한 겹씩 해쳐나가야 합니다. 현재 겹에서의 방 번호의 최댓값을 코드에서 'step'으로 표기하였습니다.
- 이 'step'은 이전 단계 최대 번호에 '지금까지 지나온 겹 수 * 6'을 더한 값입니다.
- 따라서 이 식을 코드로 나타내면 다음과 같습니다.
def find_minimum_steps_to_room(N):
step = 1 # 현재 겹에서 방 번호 최댓값
count = 1 # 지금까지 지나온 겹 수
while N > step:
step += count * 6
count += 1
return count
if __name__ == '__main__':
N = int(input())
print(find_minimum_steps_to_room(N))
2798번 : 블랙잭
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
- 여러 수가 주어질 때, 이 중 3개를 합하여 M과 가장 가깝게 되는 수를 출력하는 문제입니다.
- 이와 같은 문제도 '브루트포스' 알고리즘을 활용하여 풀 수 있습니다.
- 저는 3중 반복문으로 모든 경우의 합을 찾아내면서 M보다는 작거나 같은 최댓값을 찾는 방식으로 진행하였습니다.
def find_max_sum_under_limit(n, m, cards):
max_sum = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
current_sum = cards[i] + cards[j] + cards[k]
if current_sum <= m:
max_sum = max(max_sum, current_sum)
return max_sum
n, m = map(int, input().split())
cards = list(map(int, input().split()))
print(find_max_sum_under_limit(n, m, cards))
'알고리즘 문제 풀이 > Class (solved.ac)' 카테고리의 다른 글
Class 2 (달팽이는 올라가고 싶다 ~ 영화감독 숌) (0) | 2023.12.18 |
---|---|
Class 2 (Hashing ~ 부녀회장이 될테야) (3) | 2023.12.15 |
Class 1 (최소, 최대 ~ 단어 공부) (4) | 2023.12.01 |
Class 1 (A x B ~ ACM 호텔) (1) | 2023.11.28 |
Class 1 (윤년 ~ A+B - 5) (2) | 2023.11.26 |