Day 13: 백준 [8단계] 기본 수학 2 - 소수

[결과]

무슨 시간이 148ms나 나왔지...... 하긴 코드를 구현목적으로만 짰으니 그럴 수 밖에 ㅠㅠ

 

[코드]

부끄러운 코드라서 올리기가 싫을 정도당

 

[과정]

1. 어제 풀었던 소수 방식으로 풀어도 괜찮을까? 주어지는 수가 10,000 이하의 자연수인데, 1초 안에 1부터 10,000까지 정수가 나온다면 다 돌고도 시간을 맞출 수 있을까? 한번 해보자!

>> 2~N까지 모든 소수를 모은 prime_list 안에 넣어둔 뒤

>> real_list안에 N과 M사이의 소수들을 모아서

>> sum과 min을 넣는다!

>> 어서 선배 개발자들의 코드를 보고 싶다....

 

[공부]

1. list.remove(element)

>> 사용하진 않았지만 원소를 지우는 함수!

>> 그나저나 반복문을 돌 때 원소 삭제해서 적용하는 방법이 기억이 안 나네..

 

[문제]

www.acmicpc.net/problem/2581

2581번: 소수

 

[선배 개발자들의 코드 분석]

1. 왜 모두들 리스트의 원소들을 미리 선언해놓았을까? append를 해도 되지 않을까? append가 느린가?

>> "append라는 함수 자체가 기존에 할당된 공간을 확장해야 하기 때문에, 만약에 연속된 메모리의 자리가 없을 경우 새롭게 큰 공간을 만들어 모든 값들을 이사시켜야 하는 단점이 있습니다. 여기서 바로 꽤나 큰 overhead가 발생하게 돼서 상대적으로 느립니다."

>> "이번 방법은 최종 보스몹.. 이번 방법은 조금 더 smart 합니다. 이미 우리는 얼마나 큰 공간을 만들어야 하는지 알기 때문에, 미리 N개의 공간을 만들어 놓고, 값만 바꿔줍니다. 실제로 메모리 할당에 드는 overhead가 가장 무지막지하기 때문에 이 방법은 1.5배 정도까지 시간을 줄여주네요."

>> "바로 Built-in(내장된) 함수를 사용하는 방법입니다. 바로 range()란 함수인데요, Built-in함수들은 C언어로 최적화되어있기 때문에, 굉장히 빠른 속도를 자랑하죠. 물론 기능은 제한적이지만, 꽤나 쏠쏠하게 사용되곤 합니다."

>> 미리 할당을 해놓고 원소를 바꾸는 게, append보다 빠르다... 와 이것도 몰랐네..

(모를만하기도 했다. 일할 땐 이런 관심이나 있었을까..)

 

2. 소수를 찾는 공식이 있나 보다.

>> 짝수를 +2~100만큼 건너뛰었을 때(10,000이라는 가정하에) 소수가 아닌가 보다.

>> 이건 소수를 나열해보지 않는 이상 어떻게 알 수 있는 거지...????

>> 괜히 고등학생 때 수학 문제 풀던 생각이 난다 ㅎㅎㅎ

>> False, True로 깔끔하게 문제 풀이가 된 것 같다! 

>> 코드도 짧고, 속도도 빠르고!

 

[느낀 점]

내가 모르는 영역에 대한 궁금증을 '쉽게' 가질 수는 없다.

내가 아는 지식의 한계에서 다른 영역이 있다는 걸 미리 알고 검색할 수가 없기 때문이다.

그런 의미에서 나 본인에게 피드백을 주기 위해서는, 멘토가 필요한 것 같다.

현재, 멘토가 없는 시점에서 나는 다른 개발자들의 풀이를 보고 분석할 수밖에 없는 것 같다.

너무 귀찮고 하기 싫지만, 그럴 때 이겨내면 성장하는 거라고 했다.

나중에 같이 일하는 개발자들에게 좋은 귀감을 주고 같이 성장할 수 있는 멘토가 되었으면 좋겠다!

이상 일기 끝!

 

[출처]

smlee729.github.io/python/data%20structure/2015/03/02/1-list-allocation.html