1. 완전 탐색모든 경우의 수를 탐색한다.그래서 비용이 비싸다. 예를 들어그래프의 인접 행렬에서 연결된 노드들을 반환할 때 완전 탐색을 하게 된다.vector> adjacent(6, vector(6, 0));adjacent[0][1] = true;adjacent[1][1] = true;adjacent[2][2] = true;// 연결된 모든 노드 출력for (int y = 0; y "  2. 백트래킹백트래킹은 완전 탐색에서 가는 방향이 목표에 도달할 가능성이 없다고 판단되면더 이상 그 경로를 탐색하지 않고 되돌아가는 것을 말한다.모든 경우를 탐색하지 않고 조건에 따라 일정만 탐색하는 것을 말한다. 예시Q.N과 N개의 자연수가 주어진다.여기서 몇 개의 숫자를 골라 합을 mod11을 했을 때 나오는 가장 ..

문제 설명2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.코드 작성#include using namespace std;vector> solution(vector> arr1, vector> arr2) { int n = arr1.size(); int m = arr1[0].size(); int k = arr2[0].size(); vector> result(n, vector(k, 0)); for (int i = 0; i   해설(y1, x1) * (y2, x2) 행렬의 곱셈에서 결과 행렬의 크기는 (y1, x2)이다.이를 토대로 배열을 생성하고 0으로 초기화한다.행렬의 곱셈으로 결과 행렬의 각 요소에 값을 저..

문제 설명정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.n행 n열 크기의 비어있는 2차원 배열을 만듭니다.i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요. 코드 작성#include #incl..

문제 설명효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸)(1칸, 2칸, 1칸)(1칸, 1칸, 2칸)(2칸, 1칸, 1칸)(2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다.멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 문제 풀이 피보나치 수열의 문제와 동일하다.a3에 도달하기 위해선, a2까지 올라온 경우의 수와 a1까지 올라온 경우의 수를 더한다.a3 = a1 + a2; 코드 작성#inc..

문제 설명두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 문제 풀이각 숫자의 소인수들을 구합니다.소인수들의 최대 개수를 제곱하여 최소공배수를 구합니다.결과값을 반환합니다. 코드 작성#include #include #include using namespace std;int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, ..

문제 설명△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다. 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번..

문제 설명Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 문제 풀이노란색 격자의 가로, 세로 길이는 정해져있다.가로 : 카펫의 가로 길이 - 2세로 : 카펫의 세로 길이 - 2모든 격자(갈색 + 노란색)를 일렬로 나열하고 가로 길이 3부터 등분해본다.등분하였을 때 모든 가로길이..

문제 설명피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.예를들어F(2) = F(0) + F(1) = 0 + 1 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F(4) = F(2) + F(3) = 1 + 2 = 3F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다.2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 문제 풀이1재귀함수코드 작성int Fibonacci(int n) { if (n 잦은 함수호출로 인해 시간 초과가 발생하였다.  문제 풀이2반복 계산코드 작성int Fibonacci..