C++_코딩테스트7 [백준 14888번/C++] 연산자 끼워넣기 - 백트래킹 백트래킹 기본문제와 틀은 같으나, 최댓값과 최솟값을 저장할 set을 추가했고 첫 for문은 연산자 수만큼 반복했다. set은 중복값을 저장하지 않고 검색이 매우 빠르며 자동으로 수를 오름차순으로 저장해주기에 용이했다. 답 #include #include #include #include using namespace std; int N{}, tmp{}; int arr[12]; // 입력받은 숫자를 저장하는 배열 int middle[12]; // DFS 중간 중간에 값을 저장하는 배열 vector Operator(4); // 처음 입력받은 연산자 개수를 저장하는 배열 vector visited(4); // DFS를 하며 변화하는 연산자 개수를 저장하는 배열 // 그런데 지금 쓰고보니 이 배열은 쓰지 않아도 됐.. 2024. 2. 5. [백준 1927번/C++] 최소 힙 priority_queue에 그냥 greater를 붙이면 될 줄 알았는데 초기화에 기본 컨테이너(vecter가 될 수도 있고 deque일 수도 있음)를 넣어줘야 한다. 답 #include #include #include #include using namespace std; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N{}, tmp{}; cin >> N; priority_queue queue; for (int i = 0; i > tmp; if (tmp == 0) { if (queue.empty()) { cout 2024. 2. 5. [백준 15649번/C++] N과 M (1) - 백트래킹 백트래킹을 처음봐서 써먹을게 브루트포스밖에 없어서 그걸 썼는데 시간초과 -> 백트래킹을 배워왔다. 백트래킹 : 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾음 해가 아니어서 막힐 때 바로 포기 = 가지치기라고 하는데, 이를 통해 시간 단축 가능 보통 DFS에서 쓰인다. 처음에 이해하기 어려웠는데 맞은건 고정해두고 뒷부분만 바꿔가면서 진위 검증을 한다고 생각하니 이해가 됐다. 이해하고 그린 그림은 아래와 같다. DFS 함수에서 변수 정보와 배열 정보가 필요하기에 변수와 배열은 전역으로 생성했다. 이 방법이 카드 4장중 2장을 고르는 것에서는 브루트포스와 별 차이 없어보이는데, 만약 4장 중 3장을 고른다고 하면 첫 선택에서 1/2를 고정해두고 뒤만 바꿔서 1/2/3, 1/2/4 출력->두번.. 2024. 2. 5. [백준 20920번/C++] 영단어 암기는 괴로워(단어 정렬 문제) -> unordered_map으로 받아서 정렬까지 다 하려고 했는데, map, set은 키로 정렬이 가능하지 second로는 정렬이 불가능하다. 그래서 vector로 옮긴 뒤에 정렬하였다. 정렬 함수를 만들어서 우선순위대로 하였다. string은 비교시 더 작은 것이 사전순으로 앞 숫자기 때문에 기호의 방향에 주의하자. (아스키 코드로 생각하면 편하다) #include #include #include #include using namespace std; unordered_map dictionary; bool compairVec(const pair& A, const pair& B) { if (A.second != B.second) { return A.second > B.second; } else { if .. 2024. 2. 4. [백준 1629번/C++] 분할 정복 곱셈 처음 이 문제를 봤을 때 분할 정복으로 나눌 방법을 찾지 못해서 DC함수를 만들고 반복문 안에서 DC함수를 불러왔다. DC함수 안에서는 계속 곱한 수의 나머지에 A를 곱하고 %C를 한.. 작은 수에서는 괜찮았는데 아무래도 A, B, C 모두 최대 21억이다보니 long long으로 받아도 안됐었다. 그래서 반복문은 포기, B를 계속 2로 나눠서 수를 낮추는 방법으로 했다. 여기서 계속 %C를 해주는 것을 모듈러 연산이라고 하는데, 모듈러 연산: 정수들 간의 산술 연산을 특정 모듈로 나눈 나머지를 구하는 연산 으로, 결과를 0부터 모듈 값까지 범위로 제한한다. 이를 통해 오버플로를 방지할 수 있다. 답 #include #include #include using namespace std; int DC(int.. 2024. 2. 4. [백준 1992번/C++] 분할 정복 쿼드 트리 -> 처음에는 size를 매개변수로 넘길 생각을 못하고 그냥 0, 0에서 +2씩 추가하면서 모든 트리를 탐색하려고 했는데, 그것은 분할 정복의 방법이 아니며 불필요한 탐색을 할 가능성이 있어 고민을 하다 인터넷에서 힌트를 얻었다. 1. 더 작은 배열로 쪼개질 때 괄호가 생성됨 -> 쪼개지지 않으면 괄호를 출력할 필요가 없으므로 진위 확인 후 시작점과 같지 않으면 괄호를 출력하게 함 2. 입력 시 위의 사진과 같이 한 줄의 string형으로 들어오기 때문에, 한 원소씩 바로 받을 수 없고 string으로 받은 후 그 string의 원소를 쿼드트리에 다시 집어넣어야 한다. 답 #include #include #include using namespace std; vector Quad(64, vector(64).. 2024. 2. 4. 이전 1 2 다음
