# dynamic programming

7개의 포스트

스티커 모으기(2)

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12971 문제 N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. image.png 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 ...

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

단어퍼즐 (DP / BFS)

문제 단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 ba, na, n, a 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”,...

2019년 11월 29일
·
0개의 댓글

서울에서 경산까지

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42899 문제 서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는...

2019년 11월 28일
·
0개의 댓글

최적의 행렬 곱셈

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12942 문제설명 크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x...

2019년 11월 26일
·
0개의 댓글

카드게임 (Dynamic Programming 정리)

문제출처: 코딩테스트 문제를 풀다가 꽤 재밌는 문제를 발견해서 이 문제를 통해 Dynamic Programming을 정리하려고 합니다. 문제설명 카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는...

2019년 11월 20일
·
0개의 댓글

3xN 타일링

문제출처: 문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 8인 직사각형은 다음과 같이...

2019년 11월 20일
·
0개의 댓글
post-thumbnail

Algorithm - BLOCKGAME2

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

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