본문 바로가기
반응형

전체 글282

프로그래머스 표현 가능한 이진트리 - C++ 풀이 1. 주어진 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다. 1. 주어진 십진수를 이진수로 변환한다. 먼저 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 노드를 왼쪽부터 순서대로 살펴보는 것은 중위순회하는 것과 같다. 따라서 변환한 이진수는 트리를 중위순회한 결과와 같고, 이진수의 길이는 트리의 노드 개수와 같다. 포화이진트리는 노드의 개수가 2^n-1개이므로 포화이진트리가 되도록 부족한 길이는 0으로 채워준다. (더미 노드를 추가하는 것은 문제가 되지 않음) 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 .. 2023. 7. 22.
프로그래머스 미로 탈출 명령어 - C++ 풀이 1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가 3. 이동방향에 대한 우선순위는 d, l, r, u이다. 1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 dp(r, c, k)를 위와 같이 정의하자. R = C = 50, K = 2500이므로 구해야 하는 상태값의 개수는 50*50*2500개. 제한 시간 내에 모두 구하기 충분하다. 기저 사례는 k=0인 경우로 이때 위치한 칸이 도착지점인지 판단하면 된다. 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc.. 2023. 7. 22.
프로그래머스 택배 배달과 수거하기 - C++ 풀이 1. 배달은 갈 때, 수거는 돌아올 때 한다. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다. 1. 배달은 갈 때, 수거는 돌아올 때 한다. 이동 거리를 최소화해야 한다. 물류센터에서 출발할 때 트럭을 배달상자로 가득 채우고 출발한다. 가면서 각 집에 상자를 배달하여 트럭을 비우고, 다시 물류센터로 돌아오면서 수거상자들로 트럭을 채워오자. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 또한 이동 거리를 최소화하기 위해서는 최대한 먼 집부터 방문하는 것이 최적이다. (A= 0 || pp >= 0) { int dist = 0; // 트럭을 배달상자로 채움 truck = cap; // 배달은 갈 때 while (truck > 0 && dp >=.. 2023. 7. 22.
프로그래머스 이모티콘 할인행사 - C++ 풀이 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 2. 비트마스크를 사용하여 이모티콘들의 할인율을 설정하는 모든 방법을 탐색한다. 3. 서비스 가입자 수가 가장 많은 방법, 서비스 가입자 수가 같다면 판매 금액이 가장 높은 방법을 선택한다. 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 각 이모티콘별로 총 가지, 10%, 20%, 30%, 40% 중 하나의 할인율을 갖는다. 따라서 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 이모티콘의 개수 n은 최대 7로 매우 작기 때문에 모든 경우를 다 탐색하는 브루트포스를 사용하더라도 제한시간 내에 해결이 가능하다. 2. 비트마스크를 사용.. 2023. 7. 22.
백준 4097번 수익 - C++ 풀이 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 dp[i]를 위와 같이 정의하자. 예를 들어, dp[3]은 1-3일인 구간, 2-3일인 구간, 3-3일인 구간 중 최고 수익인 구간의 수익이다. 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 구간은 연속된 일자로 이루어져 있다는 성질을 이용한다. i일로 끝나는 구간은 1. i-1로 끝나는 구간에 i일을 추가하거나, 2. i일로 시작하면서 끝나는 구간(i일로만 이루어진) 둘 중 하나이다. 이 두 .. 2023. 7. 17.
반응형

티스토리툴바