본문 바로가기
반응형

Problem Solving/프로그래머스14

프로그래머스 표현 가능한 이진트리 - 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.
반응형

티스토리툴바