전체 글91 카펫의 크기 구하기 - 완전 탐색 카펫의 전체 크기를 출력 갈색과 빨간색으로 이루어진 격자 모양의 카펫이 있다. 갈색의 개수와 빨간색의 개수가 주어졌을 때 카펫의 전체 크기를 맞추는 문제이다. 빨간색은 갈색으로 둘러 쌓여있는 구조이다. 빨간색을 갈색으로 둘러 쌓으려면 위/아래, 좌/우로 한줄씩 더 나와야 한다는 사실을 알 수 있다. 빨간색의 개수가 주어졌을 때 약수끼리의 곱(a*b)으로 표현 할 수 있다. 이 때 약수끼리의 곱을 행과 열의 길이로 대입해서 풀면 된다. 약수를 구하는 방식은 완전 탐색으로 0으로 나누어 떨어지는 숫자를 구하면 된다. 최적화를 하면 완전 탐색으로 자기 자신의 숫자까지 오는게 아니라 제곱근까지 오면 된다. 위에서 찾은 약수끼리의 곱으로 a행과 b열로 구성 되었을 때 둘러 쌓을 수 있는 최소 숫자를 구한 후 매개.. 2019. 10. 24. 숫자 야구 게임 - 완전 탐색 숫자 야구 게임에서 정답이 될 수 있는 숫자 조합의 개수를 출력 주어진 힌트를 가지고 정답이 될 수 있는 숫자의 조합을 모두 찾는 문제이다. 완전 탐색으로 모든 조합을 찾아 낼 수 있으면 쉽게 풀 수 있다. 모든 숫자를 순회하면서 각 숫자조합 마다 힌트와 일치하는지 검사한다. 주어진 힌트(strike 숫자, ball 숫자)들과 완전히 개수가 일치하면 정답 중 하나라는 뜻이다. 문제의 핵심 어느 숫자가 힌트의 모든 조건과 일치하면 정답이다. 문제를 해결하는데 정답을 가정하고 역순으로 접근하는 방법도 도움이 된다. int solution(vector baseball) { int answer = 0; // 야구게임에서 사용 할 수 있는 모든 경우의 수 for(int i = 123; i 2019. 10. 23. 모든 소수 찾기 - 완전 탐색 주어진 문자열을 각각의 숫자로 분리하여 만들 수 있는 모든 경우의 수가 소수인지 아닌지 검사하는 프로그램을 만들어라. '17' ==> [1, 7, 17, 71] 모든 경우의 수 위의 집합에서 소수만 뽑으면 7, 17, 71이 나온다. 위의 프로그램을 구현하기 위해 필요한 지식 소수 검증 함수 STL의 순열 알고리즘 소수란? 1과 자기자신으로만 나누어 지는 수를 말한다. 소수를 검증하는 알고리즘을 구현하는 방식 1부터 자기자신의 숫자까지 반복문을 순회하며 나누어 떨어지는지 검사 에라토스테네스?의 체 (이름이 너무 어렵다... 그냥 비스므리한 이름이다. 여하간) 위의 2가지 방식을 잘 섞으면 효율이 좋은 알고리즘을 만들 수 있다. 위의 1번 문항을 보면 자기자신의 숫자까지 반복문을 순회한다고 .. 2019. 10. 22. 문자열 조작 1 - 재귀함수 주어진 괄호 문자열을 '올바른 괄호 문자열' 형태로 만든 후 출력 주어진 괄호 문자열을 정해진 알고리즘 대로 구현 할 수 있는지, 재귀함수를 구현 할 수 있는지를 묻는 문제다. 입출력 예제 )( => () ()))((() => ()(())() '(', ')'의 개수가 일치하는 문자열은 '균형잡힌 괄호 문자열' 균형잡힌 괄호 문자열에서 괄호들이 올바르게 짝이 맞으면 '올바른 괄호 문자열' #include #include using namespace std; bool IsPerfectPair(string p) { int value = 0; for(int i = 0; i < p.length(); ++i) { if(p[i] == '(.. 2019. 10. 21. 문자열 조작 1 - 완전 탐색 주어진 문자열을 압축 했을 시 길이가 가장 작아지는 문자열의 길이를 출력 문자열 내 반복되는 문자열이 존재 할 시 반복되는 횟수만큼 압축하라는 문제다. 입출력 예제 aabbaccc -> 2a2ba3c 제한사항: 문자열의 길이 1 이상 1000이하 #include #include #include using namespace std; int solution(string s) { int answer = INT_MAX; int len = s.length(); if(len == 1) return 1; for(int selection = 1; selection 1) { compressedString += to_string(compressed) + target; } else { compressedString += t.. 2019. 10. 21. 1025. Divisor Game 난이도: Easy 문제 설명 Alice and Bob take turns playing a game, with Alice starting first. Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of: Choosing any x with 0 < x < N and N % x == 0. Replacing the number N on the chalkboard with N - x. Also, if a player cannot make a move, they lose the game. Return True if and only if Alice wins th.. 2019. 9. 19. 이전 1 2 3 4 5 6 ··· 16 다음