Lv4

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 단어 퍼즐(2017 팁스타운)

🤔문제 해결 Lv4 | 다이나믹 프로그래밍 풀이 방법은 앞에서 부터 문자 하나하나 선택한다. 'b', 'a', 'n', ... 그 문자로 끝나는 단어가 strs에 들어있는지 확인한다. 있으면 현재까지 썼던 단어 개수(dp[i])와 그 문자를 사용했을 때의 단어 개수를 비교해서 최솟값으로 갱신 (말이 너무 어렵다...) ["ba", "na", "n", "a"] 와 "banana"로 테스트 해보면 맨처음 "b"로 끝나는 단어는 없으므로 pass 다음 "a"로 끝나는 단어는 "a"와 "ba"가 있다. - "na"는 조건에 맞지 않음 "a"를 선택했을 때는 아무일도 없다. why? 처음에 b로 끝나는 단어가 없어서 값이 무한대인 상태 "ba"를 선택하면 1로 갱신해준다. - (단어 하나만으로 "ba"를 만들었다..