본문 바로가기

Algorithm/Brute Force

 (122)
(C++) - 백준(BOJ) 1759번 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 재귀를 통해 적절히 모든 경우의 수를 탐색하면 됩니다. 풀이방법 1. 사전순으로 c개의 알파벳을 l개만큼 순서에 상관 없이 뽑아줍니다. 2. 모음이 최소 1개, 자음이 최소 2개라면 정답이므로 출력해줍니다. Code #include using namespace std; int l,c,ck[16]; char letter[16]; vector candidates; void dfs(int depth, int..
(C++) - 백준(BOJ) 1039번 : 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 이차원 배열 d를 다음과 같이 정의합니다. : d[n][k] => n이라는 수를 만들기 위해 사용한 움직임 개수 k에는 n이 저장됩니다. 2. 재귀함수를 통해 i번째와 j번째를 모두 확인하면서 swap해봅니다. swap의 결과 가장 앞의 수가 '0'이라면 원복해줍니다. 모두 확인한 후에는 원래자리로 다시 swap합니다. 3. 함수의 반환값을 출력합니다. Code #include using namespace std..
(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 외벽 점검 https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr brute force로 푼 문제였습니다. 풀이방법 1. dist를 오름차순으로 정렬해줍니다. 2. 조합을 통해 dist를 정해줍니다. dist배열의 왼쪽이 투입할 우선순위가 제일 높습니다. 매 조합으로 dist를 정할 때마다 weak를 계속해서 돌리며 최소의 투입인원을 찾습니다. 8! * 15 * 8 = 4838400으로 1초 내에 수행 가능합니다. weak를 ..
(C++) - 프로그래머스(월간 코드 챌린지 시즌2) : 약수의 개수와 덧셈 https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr brute force 문제였습니다. 풀이방법 한 숫자에 대해 약수의 개수를 찾고 짝수면 해당 수를 더하고 홀수면 해당 수를 빼줍니다. Code #include #include using namespace std; int getNum(int num){ int cnt = 0; for(int i = 1; i
(C++) - 백준(BOJ) 1062번 : 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 효율적으로 탐색해야하는 문제였습니다. 풀이방법 그냥 있는대로 탐색한다면 조합을 뽑는데 최대 26C13이 나오므로 1천만의 시간복잡도 가집니다. 따라서 뽑은 후 50 * 15를 하면서 최대 단어의 개수를 구하므로 50 * 15 * 1천만 = 7억 5천정도의 시간복잡도로 시간초과에 걸립니다. 따라서 효율적인 탐색방법을 고안해야합니다. 먼저 모든 단어는 "anta"로 시작되고, "tica"로 끝납니다. 이 말..
(C++) - 백준(BOJ) 4641 : Doubles www.acmicpc.net/problem/4641 4641번: Doubles 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4가 2의 www.acmicpc.net brute force문제였습니다. 풀이방법 while loop를 돌며 x를 계속 입력받습니다. x가 -1이면 loop를 탈출합니다. x가 양수라면 vector에 넣어줍니다. x가 0이면 답을 구하고 vector와 ans변수를 초기화해줍니다. Code #include using namespace std; vector num; int ans; int main(){ while(1)..
(C++) - 백준(BOJ) 2503번 : 숫자야구 www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 111부터 999까지 loop를 돕니다. 같은 숫자인 경우나 0을 포함하는 경우는 건너뜁니다. 2. 질문에 나온 수로 ball과 strike의 개수를 세줍니다. 한 질문에 대한 ball이나 strike개수가 다르다면 답이 될 수 없으므로 flag를 세워줍니다. 3. 모든 질문에 대한 ball과 strike개수가 같다면(if(!flag)) 답입니다. 4. 조..
(C++) - 백준(BOJ) 10448번 : 유레카 이론 www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 누적합을 1000까지 구해줍니다. 2. 누적합이 1000을 넘는 구간은 45번째 수부터이므로 3개 수들 합이 찾으려는 수와 같은지 3개의 for문을 이용해 찾아줍니다. Code #include #define ll long long using namespace std; int triangleNum[1001]; int t; bool ck(int num..

티스토리툴바