알고리즘문제해결전략 p159 문제 게임판 덮기 (문제ID:BOARDCOVER, 난이도 하) 알고스팟 링크 풀이 나는 2차원 입력값을 브루트포스로 뭔가 시뮬레이팅 하는 문제가 제-일 싫다. 그래서 원래 이 포스팅을 시작하면서 한번 풀었던 문제도 다시 풀려고 마음 먹었는데 이 문제는 그냥 옛날 코드를 조금 손보기만 했다. 아이디어는 좌상단에서 우하단으로 좌표를 이동시키면서 빈 칸이 있으면 재귀호출을 하는 방식으로 4가지의 블럭 모양의 기준을 좌상단 좌표로 맞추는게 핵심이다. (위나 왼쪽으로 삐져나가지 않는 방법으로) 이렇게 했을 경우에 항상 한번 지나온 좌표는 더 이상 신경 쓸 필요가 없기 때문에 한번의 DFS로 모든 경우의 수를 다 찾을 수 있다. 조금 깔끔하게 코드를 쓰기 위해서 '.' 과 '#'을 각각..
알고리즘문제해결전략 p155 문제 소풍 (문제ID:PICNIC, 난이도 하) 알고스팟 링크 풀이 입력 크기가 작고 메모리나 시간도 넉넉하기 때문에 큰 고민없이 DFS를 했다. 재귀 함수 안에서 중복을 검사하는 students리스트를 집합으로 하면 더 빠르게 동작할 거라고 생각되지만 집합이 정렬을 보장해 주지 않기 때문에 리스트를 사용했다. 따라서 시간복잡도가 좋지는 않은 것 같다. (매번 검사를 할때마다 리스트의 길이 만큼의 시간이 소모되므로) 하지만 정답을 받는데는 문제가 없었으므로 pass 만약 시간적으로 더 개선이 필요하다면 중복처리를 숫자 자체를 집어넣은 리스트가 아니라 포함 유/무를 bool형으로 관리해주면 훨씬 더 개선될 거라고 생각한다. (책에서도 그렇게 관리 한 것 같다.) 코드