2025.01.09TIL - 프로그래머스 문제풀이

문제사이트: https://school.programmers.co.kr/learn/courses/30/lessons/120846

• TIL (Today I Learned) - 합성수 구하기 문제 풀이

  ---

  문제 개요
  • n = 10 → 합성수: 4, 6, 8, 9, 10 → 결과: 5
  • n = 15 → 합성수: 4, 6, 8, 9, 10, 12, 14, 15 → 결과: 8.

  ---

  오늘 배운 내용문제 풀이 접근 방식
  1. 합성수 판별
     • 합성수는 약수의 개수가 3개 이상인 수입니다. 숫자별 약수를 탐색하고, 약수의 개수가 3개 이상이면 합성수로 판단했습니다.
  2. 효율적인 약수 탐색의 필요성
     • 처음에는 모든 숫자에 대해 약수를 구하는 방식으로 접근했으나, 효율적인 탐색 방식의 필요성을 느꼈습니다. 약수는 대칭적이므로 sqrt(i)까지만 탐색하면 된다는 점을 알게 되었습니다.

  ---

  처음 작성한 코드

  def solution(n):
      answer_list = []
      for i in range(1, n+1):  # 1부터 n까지 확인
          num_list = []  
          for j in range(1, i+1):  # 1부터 i까지 약수 찾기
              if i % j == 0:  # 약수 조건  
                  num_list.append(j)  # 약수를 리스트에 추가
                  
          if len(num_list) >= 3:   # 약수가 3개 이상이면
              answer_list.append(i)  # 결과 리스트에 추가
                  
      return len(answer_list)  # 약수가 3개 이상인 수의 개수 반환
  

  코드 분석
  1. 약수 찾기: 각 숫자 i에 대해 1부터 i까지 나누어떨어지는 값을 찾아 약수를 구했습니다.
  2. 합성수 판별: 약수의 개수가 3개 이상이면 합성수로 판단하여 리스트에 추가했습니다.
  3. 비효율성: 숫자 i에 대해 1부터 i까지 반복문을 사용하여 모든 약수를 탐색했기 때문에, 숫자가 커질수록 계산량이 많아져 비효율적이었습니다.
  개선점
  • 모든 숫자에 대해 약수를 구하는 반복문이 비효율적이므로, 약수를 구하는 과정을 최적화해야 했습니다.
  • 약수의 대칭성을 활용하면 1부터 sqrt(i)까지만 반복하여도 모든 약수를 구할 수 있습니다.

  ---

  개선된 코드

  import math
  
  def solution(n):
      answer_list = []
      for i in range(1, n + 1):
          divisor_count = 0
          for j in range(1, int(math.sqrt(i)) + 1):  # 1부터 sqrt(i)까지 탐색
              if i % j == 0:  # j가 i의 약수라면
                  divisor_count += 1  # 약수 j 추가
                  if j != i // j:  # 대칭 약수 중복 방지
                      divisor_count += 1
          if divisor_count >= 3:  # 약수가 3개 이상이면 합성수
              answer_list.append(i)
      
      return len(answer_list)
  

  ---

  개선된 부분
  1. math.sqrt() 활용
     • 숫자 i의 약수를 구할 때, 1부터 sqrt(i)까지만 탐색하고 나머지 약수는 대칭적으로 추가해 효율성을 높였습니다.
     • 예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12인데, 1, 2, 3까지만 탐색하고 나머지 대칭 약수(4, 6, 12)를 추가했습니다.
  2. 중복 약수 처리
     • 대칭 약수 중복을 방지하기 위해 조건문 if j != i // j를 추가했습니다. 이를 통해 불필요한 연산을 줄였습니다.

  ---

  깨달은 점
  1. 효율적인 알고리즘 설계
     • 약수의 대칭성을 활용하면 불필요한 반복을 줄이고 효율적인 알고리즘을 설계할 수 있음을 배웠습니다.
  2. 조건문 활용
     • 중복 계산을 방지하기 위해 조건문을 적절히 활용하는 것이 중요하다는 것을 느꼈습니다.
  3. 문제 해결의 다양성
     • 처음엔 직관적으로 모든 약수를 구했지만, 최적화를 통해 더 나은 코드를 작성할 수 있다는 점을 알게 되었습니다.

  ---

  복습 계획
  1. 수학적 알고리즘 연습
     • 약수 구하기, 소수 판별 등 수학적 문제를 효율적으로 해결할 수 있는 알고리즘을 더 연습할 계획입니다.
  2. 다양한 접근법 실험
     • 같은 문제를 다른 방법(예: 에라토스테네스의 체)으로도 풀어보고, 성능을 비교하며 최적의 방법을 고민해 보겠습니다.
  3. 리팩토링 연습
     • 처음 작성한 코드를 지속적으로 리팩토링하며, 더 간결하고 효율적인 코드를 작성하는 연습을 하겠습니다.

  ---

  배운 점 요약
  • 효율성: sqrt(i)를 활용한 약수 구하기로 연산량을 크게 줄일 수 있었습니다.
  • 수학적 사고: 약수의 대칭성을 활용해 중복 계산을 제거하는 방법을 알게 되었습니다.
  • 코드의 가독성과 성능: 효율성을 유지하면서도 읽기 쉬운 코드를 작성하는 것이 중요하다는 것을 깨달았습니다.

  ---

  오늘의 느낀 점
• 초기 코드에서 비효율적인 부분을 개선하며, 수학적 사고를 통해 더 나은 알고리즘을 설계하는 방법을 배울 수 있었습니다. 같은 문제라도 다양한 접근 방식이 있다는 점이 흥미로웠고, 앞으로는 최적화와 가독성 사이의 균형을 고민하며 문제를 풀어나가고 싶습니다.
• 문제 설명: 자연수 n 이하의 숫자 중 약수의 개수가 3개 이상인 합성수의 개수를 구하는 문제입니다.
  합성수: 약수가 3개 이상인 자연수.
  제한 사항: 1 ≤ n ≤ 100
  입출력 예시:

---

복습 계획

1. 수학적 문제 풀이 연습
   • 약수 구하기, 소수 판별 등 수학적 알고리즘 문제를 풀며 최적화 기법을 연습할 예정입니다.
2. 코드 리팩토링 연습
   • 기존 코드를 더 깔끔하게 리팩토링하거나, 메모리 사용을 줄이는 방식으로 개선할 방법을 고민할 계획입니다.

---

배운 점 요약

1. 효율적인 약수 구하기: sqrt(i)까지만 탐색하고 대칭 약수를 활용하는 방법.
2. 조건문 활용: 대칭 약수 중복 방지로 불필요한 연산 제거.
3. 코드의 가독성과 성능: 효율성을 유지하면서도 읽기 쉬운 코드를 작성하는 연습이 중요함.

---

오늘의 느낀 점

처음에는 약수를 모두 구해 개수를 확인하는 비효율적인 방식을 사용했지만, 대칭 약수를 활용해 sqrt(i)까지만 탐색하는 방법으로 성능을 크게 개선할 수 있었습니다. 문제를 해결하는 다양한 방법을 고민하며, 같은 결과를 더 효율적으로 얻는 과정이 흥미로웠습니다. 앞으로도 최적화된 알고리즘 설계와 가독성 높은 코드 작성에 더 신경 써야겠다고 느꼈습니다.