알고리즘 시작..
오늘은 어제 못한 알고리즘을 시작했다..
팀원들과 어제 CSAPP 책에 대해 서로의 생각과 의견을 나누고 오늘은 이번주에 주어진 알고리즘을 쭉 풀고 이야기 해보기로 했다.
풀어야하는 알고리즘 중 내가 잘 못 했거나 헷갈렸던 문제들을 정리해보려 한다.
백준 OX퀴즈 4344번
처음에는 바로 풀 수 있는 문제인줄 알고 아래와 같이 풀었다.
import sys
input = sys.stdin.readline
a = int(input())
for _ in range(a):
b = input()
b = b.replace('X', ' ')
b = list(b.split())
score = 0
for i in b:
score += len(i)*(len(i)+1)//2
print(score)- OX 문자열을 받아 X를 ' '빈칸으로 치환
- split으로 빈칸을 기준으로 나누기
- 리스트에 O으로된 문자열 삽입
- O가 붙어있을 때마다 1씩 늘어나는 등차수열로 계산
막상 풀어보니 더 좋은 방법이 있을 것 같다는 생각이 들었다.
import sys
input = sys.stdin.readline
a = int(input())
for _ in range(a):
t = list(input())
cnt, sum_score = 0, 0
for i in t:
if i == "O":
cnt += 1
sum_score += cnt
else:
cnt = 0
print(sum_score) 위와 같은 방법을 발견하고 머리를 탁 쳤다...
굳이 O만 있는 문자열을 나누지 않더라도
- i = O면 cnt를 1씩 증가
- cnt를 바로 sum_score에 더하기
- X가 나올 땐 cnt = 0으로 초기화
내 방법보다 훨씬 깔끔하고 이해하기 좋은 방법이라 느껴졌다.
백준 골드바흐의 추측 9020번
이 문제는 처음 볼 때 숨이 탁 막혔다.
4 이상의 소수는 실수들의 합으로 나타낼 수 있다하지만 이걸 파이썬으로 어떻게 구현해야할지 막막했다.
혼자 소수 판별을 짜보는 와중 두 가지의 방법이 있다는 정보를 보게됐다.
def is_prime_number(n):
# 1은 소수가 아님
if n == 1:
return False
# 2부터 n까지 나누어 떨어지는지 확인
for i in range(2, n + 1):
# 자기 자신은 건너뛰기
if i == n:
continue
# 나누어 떨어지면 소수가 아님
if n % i == 0:
return False
# 나누어 떨어지는 수가 없으면 소수
return True일반 소수 판별
- 시간복잡도 O(n)
- 2부터 n까지 모든 수를 검사
- 각 수마다 n번의 연산 필요
- 큰 수에 대해 매우 비효율적
- 나누어 떨어지는 수가 있으면 소수가 아님
# 중앙부터 시작하는 방식
import sys
input = sys.stdin.readline
# 0과 1은 소수가 아니므로 False, 나머지 9,999개를 True로 초기화 (소수 판별용)
is_prime = [False, False] + [True] * 9998
# 에라토스테네스의 체 알고리즘으로 소수 목록을 미리 구함
for i in range(2, int(10000 ** 0.5) + 1): # 2부터 √1,000,000까지 반복
if is_prime[i]: # i가 소수이면
for j in range(i*i, 10000, i): # i의 배수들은 소수가 아니므로
is_prime[j] = False # 해당 인덱스를 False로 마킹
t = int(input())
for _ in range(t):
n = int(input())
# 중앙값부터 시작
# 중앙값에서 가장 가까운 소수 찾기
left = mid
right = mid
# 중앙에서부터 양쪽으로 퍼져나가며 검사
while left > 0 and right < n:
# 두 수가 모두 소수인지 확인
if is_prime[left] and is_prime[right]:
print(left, right)
break
# 한쪽은 감소, 다른 쪽은 증가
left -= 1
right += 1에라토스테네스의 체
- O(n log(logn))
- 2부터 √n까지의 수만 검사
- 배수를 지우는 방식
- 메모리를 사용해 속도 향상
is_prime = [False, False] + [True] * 9998
for i in range(2, int(10000 ** 0.5) + 1):
if is_prime[i]: # i가 소수이면
for j in range(i*i, 10000, i):
is_prime[j] = False - 위와 같이 처음엔 0, 1 은 소수가 아니기 때문에 False
- 2 ~ N까지는 True로 초기화
제곱근까지만 검사하는 이유
100까지의 소수를 찾는다고 가정
√100 = 10
11 이상의 수의 배수는 이미 2~10의 배수를 처리할 때 모두 처리됨
Ex: 11의 배수인 22는 이미 2의 배수로 처리됨
13의 배수인 26은 이미 2의 배수로 처리됨
i*i부터 시작하는 이유
예를 들어 i = 5일 때
5×2 = 10 (이미 2의 배수로 처리됨)
5×3 = 15 (이미 3의 배수로 처리됨)
5×4 = 20 (이미 2의 배수로 처리됨)
5×5 = 25 (여기서부터 시작)
5×6 = 30 (이미 2의 배수로 처리됨)
2의 배수 처리: 4, 6, 8, 10, 12, 14, 16, 18, 20, ...
3의 배수 처리: 9, 12, 15, 18, 21, 24, ...
5의 배수 처리: 25, 30, 35, 40, ...
7의 배수 처리: 49, 56, 63, ...
100까지의 소수 찾기
- 제곱근 사용: 2~10까지만 검사 (9번)
- 제곱근 미사용: 2~100까지 검사 (99번)
1000까지의 소수 찾기:
- 제곱근 사용: 2~31까지만 검사 (30번)
- 제곱근 미사용: 2~1000까지 검사 (999번)
