jun-wiki

오늘도 코테다

기숙사 정리해야해서 많이는 못한다

첫 문제는 모든 순열 백준이다

어떻게 풀어야할지 모르겠다만…

알고리즘 분류 재귀라서 재귀 함수 사용했다

재귀 함수 간만에 쓰려니 어렵다;;

주요하게 짚어야할 부분은

1. 탈출조건

2. 백트레킹

3. 데이터 관리

4. sys.setrecursionlimit 써서 재귀 제한 늘리기 (파이썬 개꿀팁)

등이 있다

그 다음으로 푼건 로또 문제다

몇가지 정해진 숫자 집합 가지고 6개 조합 만드는 문제다

이것도 재귀 함수다

하나 헷갈렸던건 순서만 바꾼 중복이면 허용안하는 거였고 재귀 함수 호출시에 인자 두개주는 식으로 처리해 체크포인트? 비슷한거 찍게 해서 해결했다

마지막은 1062 가르침이다

지민센세가 남극의 학교 무너지기직전까지 가르침을 주려는 문제다

새 학교 부지는 마다가스카르가 되리라 예상한다

주어진 단어랑 사용가능한 글자 수 가지고 몇개까지 만들수 있냐는 문제다

처음에 글자 빈도수로 하려다가 안돼서

글자 집합 만들고 이를 통해 만들 수 있는 경우의 수 해서 가장 많이 단어 만들때 찾도로 수정했다

확실히 브루트포스다

CPython으로는 TLE 나서 PyPy3로 통과했다

그치만 그렇게 끝내면 아쉬우니 비트마스킹도 적용해보았다

시간단축 해보려 말이다

…

난이도 2배는 뛴 거 같다

비트 마스킹 생각보다 어렵다

비트 마스킹 하면서 인자로 비트 마스킹한 값까지 넘겨주려 하니까 머리 아픔;;

아무튼 덕분에 PyPy말고 CPython으로도 통과 가능해졌다

관련 코드는 다른 깃헙 프로젝트 폴더에 들어있다

오늘 푼 것들