목록분류 전체보기 (146)
on my way
* 생각한 아이디어 및 문제 풀이계산 가능한 모든 경우의 수를 완전 탐색으로 계산하여 풀이하면 된다. 연산자의 우선 순위같은 것이 없고, 그냥 앞에서 뒤로 차례로 모든 연산자마다의 값을 max와 min으로 계산한다. * 코드#include#includeusing namespace std;int N;int number[12];int operators[4];int maxNum = INT32_MIN;int minNum = INT32_MAX;void Calculator(int plus, int minus, int mul, int div, int count, int sum) { if (count == N) { maxNum = max(maxNum, sum); minNum = min(minNum, sum); } ..
* 생각한 아이디어 및 문제 풀이수 하나를 더할 때 마다 답이 아니면 처음부터 진행하는 것이 아닌, 그 수를 빼고 다른 수를 더해 확인하는 백트래킹 방식을 사용하여 재귀함수 형식으로 문제를 풀이한다. 주의할 점은 sum이 해당하는 값에 도달하더라도 뒤의 것을 계속해서 탐색해야한다는 것이다. * 코드#include using namespace std;int arr[21];int N, S, cnt=0;void backTracking(int start, int sum) { if (start >= N) return; int tmp = sum; tmp += arr[start]; if (tmp == S) cnt++; for (int i=start+1; i> N >> S; for (int i=0; i> arr[i]..
* 생각한 아이디어 및 문제 풀이두 팀의 능력치를 구하고, 그 차이의 최솟값을 구하는 문제이다. 백트레킹으로 N명을 N/2명으로 나누어 각각 두 팀으로 나눠서 vector에 push해준다.각각의 능력치를 return하는 getStat 함수를 통해 능력치를 계산하였다.답은 두 팀 능력치 차이의 최솟값이다. * 코드#include #include using namespace std;int n;int team[20][20];int check[20];int ans = 0x7f7f7f7f; //초기화int getStat(vector oneTeam){ int stat = 0; int size = oneTeam.size(); for(int i=0; i aTeam; vector bTeam;..
완전 탐색(Brute-Force) 완전히 탐색, 즉 가능한 경우의 수를 모두 조사하는 방법이다. 예시) 번호 자물쇠 (경우의 수 0000~9999). 최악의 경우 10000*1초 = 대략 166분 그러나 컴퓨터 연산속도는 1초에 1억(=10^8) 백만(1,000,000)은 10^6 완전 탐색의 장단점 장점: 답을 무조건 찾을 수 있다. 단점: 답을 찾는데 시간이 많이 걸린다. 따라서, 탐색할 요소가 많을 때는 다른 방법을 사용하는 것이 현명하겠지만 탐색할 요소가 적거나, N제한이 작은 경우에는 완전 탐색만큼 정확한 탐색 방법은 없다. 또한 완전 탐색 문제를 풀 때에는 시간 제한을 체크하는 것이 중요하다. 재귀함수 어떤 함수에서 자기 자신을 호출하는 함수이다. (인셉션에서의 꿈 개념과 동일하다) 재귀함수에..
* 생각한 아이디어 및 문제 풀이 0. 이름 길이별로 벡터를 생성한다. 1. 등수가 k만큼 차이나는 사람과 이름 길이를 비교하고 해당 길이의 벡터에 ++을 한다. 2. 만약 큐의 사이즈가 K 이상이라면 비교 숫자를 벗어난 것이므로 큐의 맨 앞에 위치한 문구를 삭제한다. 3. 이를 반복해서 좋은 친구를 출력한다. * 코드 #include #include #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K, len; long long Good=0; string input; vector v(21); queue q; cin >> N >> K; for(..
* 생각한 아이디어 및 문제 풀이 1. 시작과 끝이 이어진 문제라 deque으로 풀어야 겠다고 생각했다. 2. 풍선의 값은 기본적으로 배열에 넣고, deque에는 각각 index를 넣는다. 3. 풍선 터뜨리고 움직이는 수가 양수라면 먼저 터뜨리고 움직이므로 1을 뺀만큼 이동을 한다. 4. 음수라면 그대로 취한만큼 이동한다. * 코드 #include #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); deque deq; vector result; int N, ballonValue[1001]; cin >> N; for(int i=0; i> ballonValue[i]; } for(int i=0..