![]()
문제 교재의 내용과 강의자료를 참고하여 0-1 배낭 문제를 해결하는 알고리즘의 구현을 완성하시오. 강의자료에서 knapsack2() 또는 knapsack3()를 참조할 것. 단, 입력값은 단위 무게당 이익의 순서로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘 실행 결과의 출력은 알고리즘의 실행 과정에서 결과 테이블 P에 저장한 무게(i) 또는 이익(j)이 0이 아닌 모든 항목 P[i][j]를 (i, j)의 오름차순으로 모두 출력한다는 것에 주의하시오. 입력 첫 번째 줄에 아이템의 개수 n이 주어진다. 두 번째 줄에 n개의 무게 w[i]가 주어진다. 세 번째 줄에 n개의 이익 p[i]가 주어진다. 네 번째 줄에 배낭 무게의 개수 T가 주어진다. 이후로 T개의 줄에 한 줄에 하나씩 배낭 무게 W가 주어..
![]()
문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution함수를 완성해주세요. 제한사항 n은 500,000,000이하의 자연수입니다. 1 1 11 42 2 2 12 44 3 4 13 111 4 11 14 112 5 12 15 114 6 14 16 121 7 21 17 122 8 22 18 124 9 24 19 141 10 41 20 142 1~20까지 입출..
![]()
문제 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방에 "..
![]()
문제 주어진 무방향 무가 중치 그래프 G = (V, E)에서 해밀턴 회로의 개수를 출력하시오. Algorithm 5.6을 구현할 때, 출발 정점은 1로 간주한다는 것을 주의하시오. 입력 첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어진다. 둘째 줄부터 m개의 간선이 주어진다. 출력 첫째 줄에 해밀턴 회로의 개수를 출력한다. 문제 해석 이 문제를 풀기 위해서는 해밀턴 회로와 해밀턴 경로의 차이를 알아야 한다. 해밀턴 회로 VS 해밀턴 경로 해밀턴 회로 한 정점에서 출발을 해 모든 정점을 딱 한 번씩 방문하고 다시 출발 정점으로 돌아와야 한다. 출발 정점과 해밀턴 회로는 무관하다. 해밀턴 경로 해밀턴 경로는 해밀턴 회로와 다르게 출발 정점에 따라 값이 다르다. 한 정점에서 출발해서 모든 정점을 한 번씩 ..
![]()
문제 주어진 평면 그래프 G = (V, E)에 대해서 인접한 지역을 서로 다른 색으로 색칠하기 위해 필요한 최소 색의 수 m의 값과 해당하는 m의 값으로 색칠할 수 있는 경우의 수를 출력하시오. 단, 그래프의 입력은 간선의 집합으로 주어지고, 주어진 그래프는 평면 그래프라고 가정해도 된다. 입력 첫 줄에 정점의 수 n과 간선의 수 k가 주어진다. 둘째 줄부터 k개의 간선이 주어진다. 출력 첫째 줄에 색칠 가능한 최소의 m값을 출력한다. 둘째 줄에 해당 m값으로 색칠할 수 있는 경우의 수를 출력한다. 문제 해석 그림과 같이 인접해 있는 영역끼리는 서로 다른 색을 칠해야 한다. 여기서 인접한다의 의미는 영역들끼리 가로 세로중 하나라도 맞닿아있어야 한다. v1과 v3, v2는 가로 세로 중 한 영역이 맞닿아있..
![]()
문제 n개의 원소를 가진 정수의 집합 S가 주어지고, 임의의 정수 W가 주어졌을 때, 합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오. 입력 첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다. 둘째 줄에 n개의 정수가 주어진다. 출력 첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다. 둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다. 단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로) ※처음 문제를 보고 떠오른 생각 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다. Backtracking을 이용해서 모든 경우의 수를 구한다. 유망성검사를 통해서 가지치기를 함. 만약 뽑은 원소들의 합이 W면 종..
![]()
문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 ..
![]()
Backtracking 되추적 알고리즘이라고 한다. 결과를 찾는 도중 막히면 다시 되돌아가서 다시 결과를 찾음. 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS vs Backtracking DFS는 모든 노드를 탐색한다. Backtracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 해가 안될 거라고 판단이 되면 경로를 이탈하고 다시 되돌아간다. --> 이것을 가지치기라고 한다. 가지치기를 통해서 불필요한 경로를 차단해서 효율성을 높일 수 있다. Promising 유망성 검사 - 이 경로가 특정조건을 걸어서 해가 될 것인지 안될 것인지 판단함. nonpromising 하다면, 그 경로는 끝까지 갈 필요가 없으므로, 다시 되돌아감. promising 하다면 계속 진행함. Prun..
![]()
문제 다음 소스는 N번째 피보나치를 구하는 C++함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 ..
