시드니랩

어제 복습한 Permutation 직접 재귀로 구현한다는 생각에 열심히 했는데, 구현과정에서 리스트 복사 안해서 실수도 하고, 아무쪼록 아직도 갈길이 멀다ㅎㅎ [내 풀이] [모범답안] [반성할 점] 우선 파이썬에서 리스트 가지고 놀때는 (append 등) 반드시 [:] 로 복사해서 써야한다. => 소수 판별은 /2 가아니라 /sqrt(2) 까지 확인해야 하고, 제곱근으로 나누어떨어지는지 까지도 확인해야한다. 리스트에서 스트링으로 바꿀때 " ".join을 반드시 떠올리자.

애초에 시간복잡도를 줄이려는 생각을 하고 이중 for문을 풀이 후보에서 지워버렸기때문에 재빨리 풀 수 있지 않았나 싶다. [내 풀이] [모범답안] [반성할 점] string 의 startswith 라는 매소드가 있다. 잘만써먹으면 이런 문자열 접두어 문제에서 유용하게 써먹을 수 있을것 같다. 또한 배열 두개를 비교할때, 한번의 for loop으로 처리하기 위해서 arr[:], arr[1:] 을 사용하여 각각을 비교하는 스킬을 배워간다.

참 갈길이 멀다. 굉장히 간단한 문제였는데, 계속 O(N^2) 으로 생각하다가 효율성에서 실패했다. 딕셔너리를 제대로 사용하면 참 풀기 쉬운 기초중의 기초 문제다. [내 풀이] O(N)만에 빨리 해보려니 코드가 더럽게 되버렸다.. [모범답안] 반성해야할 점: Counter 객체를 전혀 생각하지 못하고 있었다. Counter 객체는 리스트를 딕셔너리 형태로 만들어주며 (결과물은 딕셔너리가 아니라 Counter 객체다) 이렇게 개수활용 측면에서 굉장히 유용한 도구이다. Counter 객체에서 key 매소드를 사용해서 dict_key 타입으로 만들어 줄 수 있다.

Q. n개의 계단이 있다. 계단은 한번에 1칸 혹은 2칸 오를 수 있다. 만약 계단을 1칸 올랐다면, 그 다음 시도에는 1칸 혹은 2칸을 오를수 있지만, 계단을 2칸 올랐다면, 그 다음 시도에는 반드시 1칸만 오를 수 있다. 반드시 마지막 계단은 밟아야 하며, 계단의 수가 주어졌을때, 계단을 오르는 방법의 수를 리턴해봐라.