개발15 c++) 백준 14888 백트래킹, 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1. 접근 수열과 수열의 각 수 사이에 들어갈 연산자가 주어진다. 수열은 순서에 맞게 계산해야하므로 사실 고려할게 없다. 우리가 고려해야할 것은 주어진 연산자들의 모든 순서와, 그로 인해 계산된 결과들을 출력하는 것 뿐. 사실상 연산자들을 선택하는 순열로 생각하면 된다. 2. 풀이 operands 배열엔 수열을 이루는 수들을 입력받는다. operato.. 2024. 3. 25. 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. c++ 하노이의 탑, 재귀함수, 백준 11729 1. 하노이의 탑 재귀함수 문제로 가장 유명하면서도, 재귀함수에 대한 이해를 위해 아주 기초적인 문제이다. 하노이의 탑은 1883년 프랑스 수학자 에두아르 뤼카가 제시한 문제로 그림과 같이, 주어진 크기가 다른 N개의 원판과 3개의 막대(A,B,C)에 대하여 A의 모든 원판을 C로 옮기는 것인데 조건이 있다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 문제는 보통 이같은 조건을 지키며 A에서 C로 모든 원판을 옮기는 최소 실행수 또는 그 순서를 요구한다. 해결에 들어가기 전에 하노이의 탑 (Tower of Hanoi) - 플래시게임 | 와플래시 게임 아카이브 (tistory.com) 하노이의 탑 (Tower of Hanoi) 하노.. 2024. 3. 22. C++) 백준 10816 숫자 카드 2 입력받은 N개의 수 중에서 또 다른 입력받은 M개의 수가 각각 몇개 존재하는지 찾는 문제이다. 입력 개수와 찾는 수 50만 개에 대해 선형탐색을 사용하면 시간초과가 난다. C++에서 Map은 O(log n)의 레드블랙트리로 구현되어있으므로, 이를 이용하면 시간 내로 문제를 해결 할 수 있다. 물론 다른 방법, 이분탐색을 사용할 수 있지만 여기선 Map을 이용한 방법을 다루겠다. 실제 사용함으로 STL 자료구조에 더 친숙해지기 위함이다. map 로 key는 각 수(중복X), value값으론 그 개수를 기록한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,inp.. 2024. 3. 13. 이전 1 2 3 4 다음
