본문 바로가기

::public/코딩테스트 풀이45

백 트래킹(backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 ; 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을 표기)하고 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법. 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태공간트리를 통해 표현 ; 각 후보군을 DFS(깊이 우선 탐색)방식으로 확인 Promising: 해당 루트가 조건에 맞는지를 검사하는 기법 Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는.. 2023. 8. 13.
하노이의 탑 하노이 탑이란 1883년 프랑스 수학자 루카스(Lucas)에 의해 고안된 문제인데, 가운데 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 문제였다. 이때 원판은 한번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다는 조건이 따른다. 최소 이동 횟수를 구하거나 원반의 이동 순서를 출력하는 문제가 나온다. [참고] https://shoark7.github.io/programming/algorithm/tower-of-hanoi [참고] https://splendidlolli.tistory.com/344 공식의 개념을 이해하라면 우선, n개의 원반을 '맨 아래 원반'과 '나머지 원반묶음'이라는 두 분류로 봐야한다. 그리고 나서 다시 '맨 아래 원반'과 '나머.. 2023. 8. 13.
피보나치 수 수학에서 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 재귀함수를 통해 푸는 방법은 가장 기본적이지만 수가 커질수록 함수 오버플로우가 발생한다. 즉, 시간초과. #include #include using namespace std; int fibonacci(int n) { if(n == 1 || n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } 시간초과를 해결하는 방법은 Bottom to Top 의 방향으로 쉽게 구현할 수 있다. n번째 피보나치 수를 구하기 위해 .. 2023. 8. 12.
문자열 밀기 #include #include #include using namespace std; int solution(string A, string B) { int answer = 0; if(A == B) return 0; int i = 0; while(i < A.size()) { // 1만큼 시계 반대방향으로 이동 rotate(A.begin(), A.begin() + A.size() - 1, A.end()); i++; if(A == B) return i; } return -1; } // 발상의 전환이 필요한 코드..awesome.. int solution(string A, string B) { B += B; return B.find(A); } 2023. 8. 8.
OX퀴즈 - 문자열 파싱 #include 과 istringstream 에 대해 더 찾아보고 공부하자. >> 연산자를 사용해 정해진 타입에 대한 파싱이 가능! #include #include #include #include using namespace std; vector solution(vector quiz) { vector answer; // quiz = ["3 - 4 = -3", "5 + 6 = 11"] / result = ["X", "O"] for(auto& q : quiz) { istringstream iss(q); char separator = ' '; vector vs; string strBuff; while (getline(iss, strBuff, separator)) { // separator을 구분자로 strBu.. 2023. 8. 8.
손익분기점 문제 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A, B, C가 주어졌.. 2019. 11. 9.

티스토리툴바