본문 바로가기

Algorithm/Brute Force

 (122)
(C++) - 백준(BOJ) 1535 : 안녕? https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 기본 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 사람 수 n, 잃는 체력 l, 얻는 기쁨 j를 일차원 배열로 선언 후 적절히 입력받습니다. 📔 풀이과정 dfs함수를 수행합니다. 현재 depth번째 사람에게 다름 두 가지 상태가 있습니다.1. depth번째 사람에게 인사하기2. depth번째 사람에게 인사하지 않기각자에 대해 모든 경우를 조사한 시간복잡도는 2^20이 되게 됩니다. 📔..
(C++) - 백준(BOJ) 1254 : 팰린드롬 만들기 https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 문자열 s, 최대 팰린드롬 길이를 저장할 maxPalinLen을 선언한 후 적절히 입력받습니다. 📔 풀이과정 문자열의 중간이 팰린드롬일 때 마자 maxPalinLen에 해당 길이를 저장합니다.이후 문자열의 길이 - maxPalinLen이 추가해야할 단어의 길이가 됩니다. 📔 정답출력 (s.size() - maxPalinLen) * 2 + maxPa..
(C++) - 프로그래머스(위클리 챌린지) : 5주차_모음사전 https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 기본 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 모음목록 문자열 str, 모음으로 이뤄진 사전 내용을 저장할 map변수 comb을 선언해줍니다. 📔 풀이과정 dfs를 수행해 5개의 모음 중 i개로 만들 수 있는 문자열들을 모두 구해 comb에 저장해줍니다. 📔 정답출력 comb에 대해 for loop를 ..
(C++) - 백준(BOJ) 12919 : A와 B 2 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 문자열 s, t를 입력받습니다. 📔 풀이과정 1. s에서 t로 만든다면 매 문자에 대해 2가지 경우의 수를 확인해야 하므로 2^50시간복잡도를 가지게 됩니다. 이는 시간초과로 틀리게 됩니다. 2. 반대로 t에서 s를 만드는 생각을 해야 합니다. 때문에 명령어는 다음처럼 바뀌게 됩니다. 2-1. 문자열 ..
(C++) - 백준(BOJ) 22251 : 빌런 호석 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 시작 층 startFloor, 보여줄 화면의 자리수 display, 남은 bit 수 bitNum, 제한 수 limitNum, 어떤 수를 바꾸는데 바꿔야할 bit개수 convertBit를 선언 후 적절히 입력받습니다. 📔 풀이과정 1. startFloor가 11인데 display가 4라면 0011식으로 보여야 합니다. 사전처리를 해서 startFloor를 수정해줍니다. 2. dfs함수를 수행합니다. 📔 정답출력 dfs함수의 결과를..
(C++) - 백준(BOJ) 9081 : 단어 맞추기 https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 test case t, 두 번째 문자열을 출력하기 위한 cnt, 문자열 s, ans를 선언한 후 입력받습니다. 📔 풀이과정 next_permutation함수를 이용해서 문자열s 다음을 출력합니다. cnt가 2라면 바로 break해줍니다. 📔 정답출력 ans를 출력합니다. 📕 Code #include using namespace st..
(C++) - 백준(BOJ) 15658 : 연산자 끼워넣기 (2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 수 개수 n, 수의 정보를 입력받을 일차원 배열 nums, 최솟값을 저장할 minAns, 최댓값을 저장할 maxAns, 연산자 개수를 저장할 op를 선언후 적절히 입력받습니다. 📔 풀이과정 첫 번째 수 부터 연산자를 입력받습니다. 이후 연산자별로 backtracking함수를 수행합니다. depth가 ..
(C++) - 백준(BOJ) 6987 : 월드컵 https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 전수조사 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 받은 결과 2차원 배열 result, 만들 결과 이차원 배열 madeResult, round별 home, away team들이 저장될 vector vs를 선언해줍니다. 매 round별 두 team이 대결하므로 6개의 팀 중 2개를 조합으로 구성해 vs에 저장해줍니다. 📔 풀이과정 매 test case마다 dfs함수를 수행합니다. 매 round별 ..

티스토리툴바