Algorithm159 #15649 N과 M (1) # 문제 # 입력 및 출력 # 풀이 전에 2309번 일곱 난쟁이 문제를 dfs로 풀려고 했는데 백트래킹까지 있어야 제대로 풀리는 문제여서 이번에 백트래킹을 좀 공부해보기로 했다 백트래킹 유형에서 제일 간단한 문제로 보이는 N과 M 문제를 먼저 풀어보았다 백트래킹이란? 가능한 모든 방법을 탐색하는 알고리즘으로 모든 방법을 탐색하는 DFS에서 가능성이 있는 루트만 검사하도록 가지치기(Purning)를 수행 즉, 가능성이 없는 루트를 가지치기로 쳐내서 탐색하는 기법 해당 문제는 길이가 M인 중복없는 수열을 구하는 것으로 dfs의 기준은 길이로 두었음 길이가 0인 수열부터 시작해서 1, 2, ... , M까지 dfs 진행 길이가 M인 수열이 되면 출력하고 dfs(M-1)로 돌아감 dfs(M-1)은 길이가 M-1.. 2022. 6. 8. #1021 회전하는 큐 # 문제 # 입력 및 출력 # 풀이 앞 뒤로 입력 및 출력이 가능해야 하므로 덱을 쓰는게 좋아보였다 최소 연산 수를 출력해야하는데 직접 연산을 해서 최소 연산수를 찾기엔 연산을 하고 나면 큐가 변경되는 문제가 있어서 해당 숫자가 앞으로 접근했을때 몇 번째에 위치하는지와 뒤로 접근했을때 몇 번째에 위치하는지 찾는 함수를 만들었다 그래서 작은 수를 가진 접근으로 연산하도록 했음 #include #include using namespace std; deque q; int find_front(int num) { for (int i = 0; i < q.size(); i++) { if (q.at(i) == num) return i; } return 0; } int find_back(int num) { for (in.. 2022. 6. 7. #16953 A → B # 문제 # 입력 및 출력 # 풀이 그리디 문제를 풀려고 했는데 풀다보니 그래프 탐색으로 풀어버렸다ㅋㅋ 트리라고 생각하면 이해가 쉬울 것이다 처음 입력받은 2가 루트노드가 되고 그 다음 *2 값을 왼쪽 노드로 *10+1 값을 오른쪽 노드로 넣어준다 하지만 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 구해야하는 b값보다 커지면 그 이하는 더이상 볼 필요가 없어짐 나는 bfs로 구현하기 위해 큐를 사용했음 위의 규칙을 지키지 위해 b값보다 커지는 노드는 큐에 아예 넣지 않음 이렇게 계산해서 b값과 같아지는 노드를 찾으면 해당 노드의 높이를 출력함 b값을 찾지 못하고 while문이 종료되면 -1출력 #include #include using namespace std; queue q; int main() { l.. 2022. 6. 6. #1010 다리 놓기 # 문제 # 입력 및 출력 # 풀이 N=3, M=5라고 가정해보자 다리가 겹치면 안되기 때문에 서쪽의 첫번째 사이트에서 선택할 수 있는 동쪽의 사이트 개수는 M-N+1개다 따라서 dp[3][5] = dp[2][4] + dp[2][3] + dp[2][2] 인데 dp[2][3] + dp[2][2] = dp[3][4]이므로 dp[3][5] = dp[2][4] + dp[3][4]로 정의할 수 있음 따라서 점화식은 dp[n][m] = dp[n-1][m-1] + dp[n][m-1] #include using namespace std; int dp[30][30]; int main() { int T, n, m; cin >> T; while (T--) { cin >> n >> m; for (int i = 1; i 2022. 6. 5. #5430 AC # 문제 # 입력 및 출력 # 풀이 시간 제한은 1촌데 문자열로 입력받아서 뒤집는 연산을 하기엔 배열 길이 100,000까지여서 시간 초과가 걸릴 것 같았다 그래서 큐를 쓰려고 했는데 이것도 뒤집기 연산을 하려면 push pop이 너무 많아질 것 같았다그래서 앞뒤로 삽입 삭제 연산이되는 deque 자료구조를 쓰기로 했다 // 틀린 풀이 #include #include #include using namespace std; int main() { int T, N, num; char c; cin >> T; while (T--) { string cmd; deque q; bool reverse = false, error = false; cin >> cmd >> N >> c; for (int i = 0; i < N.. 2022. 6. 4. #10799 쇠막대기 # 문제 # 입력 및 출력 # 풀이 처음엔 레이저 부분인 ()를 .으로 치환해서 풀 생각이었다 // 틀린 풀이 #include #include using namespace std; int main() { string str; cin >> str; int cnt = 0, stick = 0; while (str.find("()") != string::npos) { // ()부분 .으로 치환 int index = str.find("()"); str.replace(str.begin() + index, str.begin() + index + 2, "."); } for (int i = 0; i < str.size(); i++) { if (str[i] == '(') { stick++; cnt++; } if (str[.. 2022. 6. 3. 이전 1 ··· 11 12 13 14 15 16 17 ··· 27 다음
