# memoization

4개의 포스트
post-thumbnail

Algorithm - BLOCKGAME2

문제 설명 H x W 크기의 게임판과 한 가지 모양의 블록이 여러 개 있다. 게임판에 가능한 한 많은 블록을 올려놓고 싶은데, 게임판은 검은 칸과 흰칸으로 구성된 격자 모양을 하고 있으며 이 중에서 흰 칸에만 블록을 올려놓을 수 있다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 격자에 어긋나게 덮거나, 검은 칸을 덮거나, 게임판 밖...

2019년 10월 27일
·
0개의 댓글

재귀 복습

Recursion Recursion은 Function이 스스로를 내부에서 부르게 하여 문제를 해결하는 기술이다. 이렇게 하면 소량의 처리만 완료하고 나머지 문제를 재귀 호출에 위임할 수 있다. 함수를 스스로 호출하는 것 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때 까지 실행하는 패턴으로 볼 수 있습니다. 재귀는 무한 반복을 방지하기 ...

2019년 10월 14일
·
0개의 댓글

동적 계획법(Dynamic Programming) - Memoization

동적 계획법을 사용하는 이유 > 동적 계획법은 부분 문제를 통해 큰 문제를 재귀적으로 해결하려고 할 때 중복되는 부분 문제들이 많이 발생하여 불필요하게 같은 계산이 반복될 때 사용된다. 이항 계수를 계산하는 공식은 아래와 같은 공식이 성립한다. bino(n, r) = bino(n-1, r-1) + bino(n, r-1) > 위 식에 대해 생각해보...

2019년 6월 27일
·
0개의 댓글