step 11 - 15

(step 15 = 1st Challenge for Me)

< ★Step 15후기 >

2023.11.24 -

문제 수준에 관하여: Step1 -14 까지 프로그래밍에서 고민이 적었거나, 부족한 이론적인 부분을 체득할 수 있었음.

Step 15에서 처음으로 몇분 안에 또는 하루만에 문제를 풀어내지 못하고 헤메다가, 3일에 걸쳐서 문제를 풀게 됨. Thanksgiving Day 연휴도 있어서 여유를 가지고 천천히 고민해볼 수 있었음. 모르는 부분을 체득할 수 있어서 좋은 시간이었음.

배운 점에 관하여: 공대생 관점에서는 문제를 푸는 방식보다는, 문제를 해결하는 것 자체가 중요하다.

4948 베르트랑 공준, 17103 골드바흐 파티션을 통해서 소수를 구하는 여러 알고리즘들을 다루면서 메모리와 시간, 컴파일러에 대해 자연스럽게 공부할 수 있었음. 13909 창문 닫기 문제에서, 시뮬레이션을 통해서 문제를 해결하다 보니 메모리/시간 부족을 모두 한번씩 겪음. 알고보니 완전제곱수 갯수를 구하는 문제여서 입력 한줄, 출력 한줄, 총 두줄로 끝냄. "방식이 중요하기보다는, 문제를 어떻게든 풀어만 내면된다" or "솔루션(최신 기술)에 집중하기 보다는 문제를 해결했는가(내 생각에 또는 쉽게 만들었는가, 발전을 보였는가) 중요하다는 것" 는 이야기를 최근에 EO의 한기용님의 강연을 통해서 들었는데, 이번 백준 Step 15를 통해서 체감할 수 있어서 좋았음.

2023.11.24 - Baekjoon 13909 창문닫기 = 완전제곱수 = 공약수가 홀수개 = 마지막에 창문이 열림 > 메모리 제한 64MB 해결

2023.11.22 - 2023.11.24 - Baekjoon 13909 창문닫기 (메모리 초과) : 배열을 선언하는 순간 메모리초과

2023.11.22 - 2023.11.24 - Baekjoon 13909 창문닫기 (시간 초과) : 각 창문 하나에 대하여 마지막에 열고 닫히는지를 나머지 연산으로 시뮬레이션해도 시간초과

2023.11.24 - 메모리 vs 시간 : 컴파일러 Python3 vs PyPy3 비교. - Baekjoon 17103 골드바흐 파티션을 푸는 중에,

Baekjoon 문제 풀이에 한정하여, 시간초과가 문제가 된다면 Python3 대신 PyPy3로 컴파일 해보는 것도 속도를 1/2~1/3 배로 단축 시킬 수 있다. PyPy3는 Python보다 메모리를 약 2배~3배 더 많이 쓴다. 컴파일러에 따른 memory vs time trade-off 를 보여준다고 생각된다. PyPy3는 그냥 Python이랑 이름이 비슷하길래 그냥 같은 코드로 실행했는데, 작동이 되고 시간도 빨라서! 잠깐 어떤 컴파일러인지 공부해보았다.

의외로 Eratosthenes sieve의 경우 list를 쓰는 것이 dictionary 자료형 보다 빨랐다. 이유는,

첫번째로, x in list 와 x in dictonary는 dictionary을 사용하게 되는 경우는 dictionary가 훨씬 빠르지만 e.g. O(nlogn) vsO(1)

Eratosthenes sieve는 이미 mapping을 시도하는 알고리즘이므로 list[idx] 와 dictionary[idx] 만을 사용한다.

두번째로, dictionary는 element를 (key, value) 두 개 저장하기 때문에 list보다 메모리를 약 2배 더 사용한다.

고등학교 때, C언어를 배우면서 정리된 좋은 문제들로 체감해보았던 이론들이,

Python을 통해서도 다시 부딪혀보며 재확인되는 부분이 있어 지금 시도해보는 Daily Baekjoon이 꽤 의미있다고 생각된다.

MATLAB을 보기 좋은 코드, 시간에 따라 잘 실행되는 코드를 구성하는 데에도 도움이 될 것 같다.

개인적으로 보편적인 Tip들은 Baekjoon main page에 기록 중이다.

2023.11.24 - 함수 선언 X = 2820 ms

2023.11.24 - 함수 선언 O = 1136 ms

2023.11.24 - 반복되는 기능을 함수로 만들면 실제로 빠르다! (지역 변수 vs 전역 변수) - Baekjoon 17103 골드바흐 파티션을 푸는 중에,

같은 코드더라도, 함수화 하느냐 하지 않느냐에 따라야 속도가 약 2배 정도 차이가난다. 이는 Python의 경우 전역 변수 (global variable)과 지역 변수 (local variable)의 접근 시간에 차이 때문이다. 전역 변수는 접근 속도가 늦으므로, 함수화 하여 지역 변수로 다룬다면, 코드 실행속도가 빠르다.

2023.11.23 - 소수 판정법에 관한 짧은 실험. - Step15. 약수, 배수와 소수 풀이를 위하여,

(1) 특정 범위 (e.g. 1~N) 를 구하는 소수 알고리즘의 경우 % 나머지 연산을 활용하기 보다는, Sieve of Eratosthenes 와 "+ 덧셈 연산"을 활용하여 후보를 지워나가는 것이 효율적이다.

실제로 N이 소수인지 아닌지 판별하기 위하여 N^0.5 까지 테스트하는 알고리즘을 1~N까지 각각 적용했을 때보다 에라토스테네스의 체가 빠른 것을 확인할 수 있다. N= 1,000,000 기준 에라토스테네스의 체는 square root method 의 약 6%의 시간이 걸린다! (0.34 sec vs 5.30 sec)

(2) 1~N까지의 범위 중에서 홀수만 판단하는 알고리즘은 크게 효과가 없었다. 이유는 N %2 ==0 이 소수들 중에서 첫번째 시도이기 때문이다. 홀수만 판단하여 시간이 1/2로 줄어들 것이라고 짧게 생각한 것이 잘못된 예상이었다.

(3) 1~N까지의 범위 중에서 이미 소수를 알고 있고, 해당 소수만을 활용하여, 나머지를 구하는 알고리즘도 크게 효과가 없었다. 특히 N이 커지면 % 나머지 연산이 잘 동작하지 않는다.

결론:

특정 범위 숫자들의 소수 판별에는 덧셈을 활용한 에라토스테네스의 체
하나의 숫자 소수 판별에는 N^0.5 까지 비교하는 square root method

2023.11.23 - 약수와 배수를 다루는 문제 마지막 3개 7,8,9 에서 메모리 초과 또는 시간 초과로 헤매는 중. 소수 판결을 위해 홀수만 확인하여 체크하는 수를 절반으로 줄이거나, 이전의 소수를 저장하여 사용하는 등의 접근 방법으로 시간을 줄이기 위해서 다각도로 접근하는 중. 실제로 정답률이 30% 대인 것을 보면, 생각보다는 어려운 문제인 것 같음.

2023.11.22 - Step15: Baekjoon1929 소수구하기, import math 보다 n**0.5이 약간 느린 것이 신기했음.

< Step 14: 집합과 맵 후기 >

[Kor]

(1) Python의 Dictionary 와 Set을 List 대신 활용하면 꽤 쉽게 풀렸다.

(2) 다른 C++ 의 문제풀이 설명을 보면 Python과 접근 방법이 꽤 차이가 났는데, 나는 C언어로 시작해서 다시 Python 언어에 대한 고민이 들었다.

짧은 조사 후에 든 생각은 "개발이 먼저? Python vs 상업화와 최적화가 먼저? C 언어" 인 것 같다.

또 ML 쪽에는 Python Library가 현재 많으므로 내 연구 필드에는 현재로써는 Python이 적합한 것 같다.

물론 Python 외에 좀 더 어려운 언어를 배울 필요성도 현재 느껴진다.

백준 문제풀이로는 시간과 메모리를 다투는 대회에 참가할 생각은 아직 없기 때문에, 스트레스 덜받는 =) Python으로 계속 진행해보려 계획한다.

[Eng]

(1) I can solve easily with the data structur such as Dictionary and Set, instead of List of Python.

(2) When I saw a solution based on the C++ language, they have a quite difference between Python's perspective.

I was wonder about Python again, since I started with C language.

What came to mind after a short googling is "Development first? Python. Commercialization and Optimization First? C++".

In addition, there are many Python libraries on the ML side, so Python seems to be suitable for my research field for now.

Of course, I also feel the need to learn a more difficult or basic languages other than Python in the future.

As for baekjoon problem solving, I am not intend to particpate in a competition for time and memory yet, so I plan to continue with less stressful =) Python.

2023.11.21 - I always try to use "Dictionary" (HASH MAP) for the listing and sorting problem of baekjoon.

2023.11.21 - My experiments about Dictionary, List, and import sys! =)

2023.11.21 - Dictionary, Key-Value 탐색이 상수시간 O(1) 이 가능한 이유 = Hash Function !

https://oi.readthedocs.io/en/latest/ds&algo/programmers_study/week2/hash.html

2023.11.21 - List를 활용한 풀이 -> 시간초과

2023.11.21 - Dictionary를 활용한 풀이 -> 900ms 로 통과

Dictionary 는 해쉬로 값을 찾아 상수 O(1) 시간을 가지므로, 많은 원소들에서 꽤 유용함.

> Tip1. Use Dictionary and Set!

2023.11.21 - Dictionary를 활용한 풀이 + import sys -> 144ms 로 통과 < 약 1/6 of input() >

Dictionary 는 해쉬로 값을 찾아 상수 O(1) 시간을 가지므로, 많은 원소들에서 꽤 유용함.

> Tip1. Use Dictionary and Set!

> Tip2. Too large number of Inputs, use sys.stdin.readline().split()

2023.11.21 - Step 14 시작.

Step 13 정렬: Counting Sort가 시간은 걸려도 (원소 갯수가 작을 때) 메모리를 적게 활용할 수 있다는 점에 좋은 것 등이 다양한 관점에서 코드를 볼 수 있다는 사실을 알게되어 좋았음.

2023.11.20 - Baekjoon 18870, 시간초과와 메모리초과를 한번씩 겪음. 중복되는 숫자를 없애고 더 짧은 길이의 배열을 sort 하여 mapping 하는 문제 전략은 유효했음. 마지막으로 set 과 dictionary 자료형을 활용하여, 각각 중복되는 숫자를 제거하고, mapping을 구성함.