[PS] 230801 유형별 코테 준비

[PS]는 문제해결 및 알고리즘을 공부한 내용을 담고 있습니다.
문제는 백준 Online Judge, Leetcode에서 참고했으며, 본문에서는 문제 접근 방식과 새로 배운 내용을 담고 있습니다.

6588. 골드바흐의 추측

• 지속적인 IndexError로 일단 Keep.

17425. 약수의 합

• TC는 맞는데 시간 초과가 떠서 틀렸던 문제.

• import sys
  t = int(sys.stdin.readline())
  
  for _ in range(t):
      n = int(sys.stdin.readline())
      print(sum(k*(n//k)for k in range(1,n+1)))
  

• 위와 같은 코드를 작성했는데 시간 초과가 나왔다.
• k*(n//k)for k in range(1,n+1)로 푸는 로직은 이해가 되는데, 이게 시간초과가 걸린다니..?
• O(nlgn)으로 풀 수 있었다.
  • i, j로 이루어진 반복문에 대해 i*j가 MAX보다 작으면 i를 array에 넣는다