알고리즘 연습 Level 6 | 프로그래머스미완Q.물건 값보다 많은 돈을 낼 경우 거스름돈을 돌려주게 됩니다. 거스름돈은 한 금액의 돈으로 줄 수도 있지만, 여러 금액의 동전을 섞어 거슬러 줄 수 있습니다.거스름돈이 N원일 때, 1원, 2원, 5원 동전이 있다면 몇 가지 방법으로 돈을 거슬러 줄 수 있을까요? change 함수를 통해 경우의 수를 반환해주는 함수를 만들어 보세요. K에는 사용할 수 있는 동전의 종류가 들어 있습니다.예를 들어, N = 5이고 K = [1, 2, 5]이면 1원, 2원, 5원 동전을 가지고 5원을 맞추는 경우의 수를 찾으면 됩니다.1원 5개1원 3개, 2원 1개1원 1개, 2원 2개5원 1개이렇게 총 4가지 경우가 있으면, 4를 리턴해 주면 됩니다.A.1234567891011..
Algorithm
알고리즘 연습 Level 6 | 프로그래머스 Q.과자를 좋아하는 동우는 책상 위에 일렬로 놓아진 과자를 발견하였습니다. 과자에는 맛을 숫자로 평가한 종이가 붙어 있습니다. 동우는 맨 왼쪽부터 순서대로 과자를 먹기로 하였습니다. 동우는 먹을 과자를 고를 때 이전에 먹은 과자보다 맛이 더 좋은 과자만 먹습니다.제일 처음에 맛이 3인 과자를 먹었다면, 다음에는 4보다 작은 맛의 과자는 먹지 않습니다.책상위에 놓인 과자의 맛이 입력되면, 동우가 최대 과자를 몇 개를 먹을 수 있는지 반환해주는 eatCookie 함수를 완성하세요.예를 들어 [1, 4, 2, 6, 3, 4, 1, 5] 가 입력된다면 동우는 1, 3, 5, 6, 8번째 과자(각각의 맛은 1, 2, 3, 4, 5)를 골라 총 5개를 먹을 수 있고, 5..
문제 카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다. 도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다. city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다. 0인 경우에는 자동차가 자유롭게 지나갈 수 있다. 1인 경우에는 자동차 통행이 금지되어 지나갈 수..
문제 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 입력 형식 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다. 1 0 && curVal == g_vecPicture[x - 1][y]) { cnt += floodFill(x - 1..
문제 하노이의 탑은 대표적인 퍼즐의 일종입니다. 세 개의 기둥이 있고 맨 왼쪽의 기둥에는 원판의 크기 순서대로 N개가 쌓여 있습니다. 이렇게 쌓여 있는 원판을 가장 오른쪽 기둥으로 모두 옮겨야 합니다. 단, 한 번에 원판을 하나씩 이동시킬 수 있고, 큰 원판을 작은 원판 위에 쌓을 수 없습니다. N개의 원판은 총 2N -1 번의 과정을 거쳐 이동할 수 있습니다. 하지만 어떠한 과정으로 원판을 옮겨야 2N -1 번만에 옮길 수 있는지는 아직 모릅니다. 원판이 N개 있을 때, Hanoi 함수에서 어떠한 과정으로 2N -1 번만에 옮길 수 있는지 과정을 리턴하세요. 리턴값의 표기 방법은 다음과 같습니다. 3개의 기둥은 순서대로 각각 1, 2, 3번으로 표기합니다. 원판을 기둥1에서 기둥3으로 이동했다면 [1,..
문제 N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다. 이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에 서 있는 상태를 나타냅니다. 이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다. 예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다. 1번째 방법은 [1,2,3] 2번째 방법은 [1,3,2] 3번째 방법은 [2,1,3] 4번째 방법은 [2,3,1] 5번째 방법은 [3,1,2] 6번째 방법은 [3,2,1] 이 때 K가 5이면 [3,1,2]가 그 방법입니다. 사람의 수 N과 순서 K..
문제 1,2,4 세 개의 숫자만 쓰는 124나라가 있습니다. 124나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법의 1 → 1 10진법의 2 → 2 10진법의 3 → 4 10진법의 4 → 11 10진법의 5 → 12 10진법의 6 → 14 10진법의 7 → 21 10진법의 수 N이 입력될 때, 124나라에서 쓰는 숫자로 변환하여 반환해주는 change124 함수를 완성해 보세요. 예를 들어 N = 10이면 “41”를 반환해주면 됩니다. 리턴 타입은 문자열입니다. 풀이 #include #include #include using namespace std; string change124(int no) { string answer = ""; char nums[3] = { '1', '2', '4' };..
문제 영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 N행 4열로 나누어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 땅을 밟으면서 한 행씩 내려올 때, 영희는 각 행의 4칸 중 1칸만 밟으면서 내려올 수 있습니다. 땅따먹기 게임에는 같은 열을 연속해서 밟을 수가 없는 특수 규칙이 있습니다. 즉, 1행에서 (5)를 밟았다면, 2행의 (8)은 밟을 수가 없게 됩니다. 마지막 행까지 모두 내려왔을 때, 점수가 가장 높은 사람이 게임의 승자가 됩니다. 여러분이 hopscotch 함수를 제작하여 영희가 최대 몇 점을 얻을 수 있는지 알려주세요. 예를 들어 1235 5678 4321 의 땅이 있다면, 영희는 각 줄에서 (5), (7), (4) 땅을 밟아 16점을 최고점으로 받을 수 있으며, hop..
문제 1보다 큰 N개의 도시 중 한 곳에 공항을 지을 예정입니다. 사람들의 편의를 위해 공항으로부터 각 사람들까지의 도시간 이동 거리가 최소가 되는 도시에 짓기로 하였습니다. 편의상 도시는 일직선상에 놓여있다고 가정하며 좌표의 범위는 음수가 포함됩니다. 또한 좌표는 정렬되어 있지 않습니다. 직선상의 위치와 그 도시에 사는 사람들의 수가 주어질 때, 공항을 지을 도시의 위치를 반환해주는 함수 chooseCity 함수를 완성하세요. 거리가 같은 도시가 2개 이상일 경우 위치가 더 작은 쪽의 도시를 선택하면 됩니다. 예를 들어 다음과 같은 정보의 도시가 있다고 가정해 봅시다. 위치 1 2 3 인구수 5 2 3 이 살 경우, 각각의 도시에 공항을 지었을 때의 사람들의 이동 거리는 8, 8, 12 이므로 1번 또..
문제 1년을 기준으로 매월 K일이 주어졌을 때 해당 일이 평일인지(월~금) 또는 주말인지(토, 일) 구하는 알고리즘을 작성하시오. 입력: day, k day: 매년 1월 1일의 날짜. 월요일부터 일요일까지를 나타내는 int형 값. 월: 0, 화: 1, 수: 2, … 토: 5, 일: 6 k: 날짜(1~28 사이의 자연수) 윤년은 계산하지 않고 일반적으로 월은 1월부터 12월까지 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31일로 가정한다. 예를 들어 1월 1일이 월요일이라 가정하고 매 달 1일의 날짜를 구하려고 하면 입력은 day = 0, k = 1이다. 결과는 1월 1일이 월요일, 즉 평일이므로 0, 2월 1일은 목요일이므로 평일 0, .. 이와 같은 방식으로 반환되는..
