로보틱스 연구일지

안녕하세요 여러분:) 이번시간에는 에라토스테네스의 체 알고리즘에 대해 알아봅시다. 에라토스테네스의 체는 유클리드 호제법과 더불어 알고리즘을 공부하셨다면, 한 번쯤은 들어봤을 알고리즘이죠? ㅎㅎ. 1. 에라토스테네스의 체란? 에라토스테네스의 체란 간단하게 말해서 시작범위와 끝 범위의 수가 주어졌을 때 그 수 가운데 있는 수 중에서 소수 리스트를 구할 수 있는 알고리즘입니다! 기본적으로 1부터 100까지 수 중에서 소수를 구하여라.라는 문제가 주어졌을 때 우리는 한 수에 대해서 모두 이중 반복문을 돌려서 1과 자기 자신을 포함한 약수가 어떤 수가 있는지 구하는 방법이 있죠? 그런데 이 방법을 사용하면 모든 수에 대해서 이중 반복문을 돌려야 하므로 시간 복잡도가 O(n²)으로 매우 큽니다. 이때 에라토스테네스..

문제 문제는 입력받은 수보다 작은 한수를 출력하는 것이다. 한 수는 각각의 자릿수가 등차수열을 이루는 수로 3번째 자리부터 이에 해당한다. 왜냐하면 최소 세 개의 자리가 있어야 차가 동일(등차)한 지 확인할 수 있기 때문이다. 그래서 1~99까지는 무조건 한수이고 이후 100~999까지 한 수를 구하는게 목표다. 풀이 그래서 반복문 1개를 통해 우선 1000이하인 한수의 리스트를 구하고 다음 반복문에서 입력받은 수 보다 작은 한수를 출력했다. 근데 다른 코드를 보니까 미리 한수 리스트를 안 구하고 수를 입력받은 뒤 바로 그 수보다 작은 수에 대해 반복문을 돌리면서 한수를 구한 뒤 그 개수를 출력했다. 그래서 미리 리스트를 구하는 것은 지난 self number처럼 모수의 리스트가 많은 경우에만 사용하는게..

문제 문제는 1~10000까지의 정수 중에서 셀프 넘버를 출력하는 것이다. 셀프 넘버는 생성자가 없는 숫자이다. 생성자는 함수 d(n)에서 나오는데 d(n)은 각각 자리를 더해 다음 수를 만드는 것으로 아래 예시와 같이 다음 수를 만든다. 33 + 3 + 3 = 39 39 + 3 + 9 = 51 51 + 5 + 1 = 57 그래서 다음 수를 만드는 수 33, 39, 51과 같은 수를 생성자라고 한다. 그래서 셀프 넘버는 1~10000 중에서 생성자가 없는 수를 말한다. 입력: X 출력: 셀프 넘버 풀이 그래서 풀이는 전체 1~10000까지의 전체 집합과 지울 생성자 집합을 만들고 셀프 넘버를 생성하고 그 값을 생성자 집합에 넣어서 저장하고 이후에 전체 집합에서 생성자를 제외하고 정렬해서 출력하면 된다. ..