약수의 개수 구하는 방법
숫자 N의 약수의 개수를 구하는 문제가 주어졌을 때, 1부터 N까지 모두 탐색을 하게 되면, N이 100,000같이 크기가 클 경우 시간이 많이 걸린다. 약수 개수를 구할 때, 시간을 줄이는 방법은 2가지가 있다. 1/ 소인수분해를 이용하는 방법 N을 소인수분해하여 각 소수의 지수를 구한 후, (각 지수+1) 값들을 곱하여 약수의 개수를 구한다. ex) N이 24일 경우 24 = 2³ * 3¹ → (3 + 1) * (1 + 1) = 4 * 2 = 8 즉, 24의 약수의 개수는 8이 된다. (1, 2, 3, 4, 6, 8, 12, 24) 2/ N의 제곱근으로 범위를 좁혀 탐색 만약 N이 24일 경우, 24의 제곱근(√24)은 4.xxxx이다. 따라서 1~24가 아닌, 1~4까지만 탐색해도 [ 1, 2, 3..
리스트(List)
** 자료구조 : 데이터를 저장하고 관리하는 방식 List 자료구조는 SET 자료구조와 비교가 많이 된다. 예를 들어, 1,2,3을 저장하려고 한다. # SET 자료구조 set에 저장할 때는 (1,2,3)으로 저장을 하든, (3,2,1)로 저장하든, (2,3,1)로 저장하든 다 똑같다. 원소가 무엇이 저장이 되어있느냐가 중요하다. 순서는 중요하지 않다. # List 자료구조 하지만, List는 순서가 중요한 자료구조. [1,2,3], [3,1,2]는 전혀 다른 리스트가 된다. 순서가 중요하기 때문에 순서가 바뀌면 전혀 다른 list가 된다. ## List 자료구조 구현방법 List 자료구조는 어떻게 구현이 될까? 크게 두 가지 방법이 있다. 1/ Array List - Array로 만들어진 list. 배..
