본문 바로가기

2021/1113

[백준] 2xN 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net def solution(n): dp = [0] * (n + 1) for i in range(n+1): dp[i] = i if i 2021. 11. 17.
[백준] 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 탑다운, 바텀업 두가지 방식으로 풀긴 했는데, 탑다운 방식으로 하니까 시간초과가 났다. max_num = 10**20 def solution(n,count): global max_num if n == 1: max_num = min(max_num,count) if n % 3 == 0: solution(n//3,count+1) if n % 2 == 0: solution(n // 2, count +1) if n > 1: solution(n-1,count+1) return max_num def solution2(n):.. 2021. 11. 16.
[알고리즘] 퀵 소트 공부해보기 분할정복 알고리즘인 퀵 소트에 대해 공부해보았다. https://www.daleseo.com/sort-quick/ [알고리즘] 퀵 정렬 - Quick Sort (Python, Java) Engineering Blog by Dale Seo www.daleseo.com 여기에서 상상 이상으로 정리가 잘 되어있다. 기본이 있고, 최적화하는 방법이 있는데 나는 일단 기본부터 외워보기로 했다. 의외로 구현이 간단해서 놀라웠다. 금방 외울 수 있었다. def qsort(arr): if len(arr) arr[i]: l.append(arr[i]) elif mid < arr[i]: r.append(arr[i]) else: e.append(arr[i]) return qsort(l) + e + qsort(r) print(.. 2021. 11. 13.
[알고리즘] DP 공부해보기 동적 계획법이라는 것에 대해 공부해보는 시간을 가졌습니다. '완전탐색 < DP' 라고 합니다. 문제를 쪼개고, 작은 단위의 답을 구하고, 그걸 바탕으로 더 큰 문제의 답을 구하는 과정을 반복하는 방법입니다. 오늘은 맛보기로 DP의 대표작인 피보나치 수열에 대해 간단하게 알아보았습니다. # recursive def f(n): if n < 2: return n return f(n-1) + f(n-2) # top - down cache = [-1] * 37 def f2(n): if cache[n] != -1: return cache[n] cache[n] = n if n < 2 else f2(n-1) + f2(n-2) return cache[n] # bottom - up fibo = [-1] * 37 def f.. 2021. 11. 10.