프로그래머스 검색 결과

해당 글 37건

[프로그래머스] (동적계획법) 도둑질 (C++)

도둑질 (Level 4) 문제 전체 문제 보기 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 접근법 이 문제에서 구해야 하는 값은 "각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값"이다. 답을 구하기 위해서 우리가 고려해야 할 점들을 살펴보자. 연속해서 두 집은 털 수 없다. 집들이 원형으로 순환되어 배치되어있다. 그래서 첫 번째 집을 털었다면 마지막 집은 털 수 없다. 우선 첫 번째 조건을 고려하여 알고리즘을 설계하고 두 번째 조건을 만족시키기 위해 설계된 알고리즘을..
Algorithms/DP 2021. 7. 28. 15:26

[프로그래머스] (동적계획법) 등굣길 (C++)

등굣길 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 접근법 문제의 답을 구하기 위해서 먼저 일반화할 수 있는 규칙을 살펴보자. 격자 모양의 등굣길에서 임의의 점 (m, n)까지 갈 수 있는 최단경로의 개수는 어떻게 구할 수 있을까? 아래의 그림처럼 일반 적으로는 (m, n)으로 가는 경로는 (m-1, n)에서 오는 경로와 (m, n-1)에서 오는 두 가지의 경로뿐이다. 때문에 (m, n)으로 가는 최단 경로의 개수는 결국 (m-1, n)까지의 최단경로와 (..
Algorithms/DP 2021. 7. 27. 15:24

[프로그래머스] (동적계획법) 정수 삼각형 (C++)

정수 삼각형 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 접근법 이 문제에서 구해야 하는 값은 "삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 값"이다. 주어진 삼각형의 n번째 행을 "삼각형의 꼭대기에서 n번째 까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 값"으로 갱신해 모두 갱신하여 풀 수 있다. 아래와 같은 방법으로 모든 삼각형을 갱신한다. 삼각형의 가장 좌측 값은 좌측 상단이 없기 때문에 우측 상단값을 가져와서 자신의 값과 합친다. 삼각형의 가장 우측 값은 우측 상단이 없기 때문에 좌측 상단 값을 ..
Algorithms/DP 2021. 7. 26. 14:31

[프로그래머스] (동적계획법)N으로 표현 (C++)

N으로 표현 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - N으로 표현 programmers.co.kr 접근법 이 문제에서 구해야 하는 값은 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟값이다. 이 문제를 풀기 위해서는 집합의 개념과 동적 계획법을 활용할 것이다. 우리는 최악의 경우 N을 8번 써서 만들 수 있는 수 들도 계산해야 하는데, N을 1회 써서 만들 수 있는 수들의 집합을 활용해서 2회 써서 만들 수 있는 수들을 구하고, N을 2회 써서 만들 수 있는 수들의 집합과, 1회 써서 만들 수 있는 수들의 집합을 활용해서 3회 써서 만들 수 있는 집합을 구할 것이다. 이렇게 4회, 5회... 8회까지 계산을 할 것이기 때문에 ..
Algorithms/DP 2021. 7. 23. 19:28