본문 바로가기
반응형

알고리즘207

백준 2023번 신기한 소수 - C++ 풀이 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 길이 n짜리 신기한 소수 x가 있다고 하자. 그럼 x[0...(n-2)] 또한 신기한 소수이다. 따라서 재귀를 이용하여 구할 수 있다. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면, P(n) = P(n-1)*10+i 중에서 소수인 것의 집합이 된다. 기저 사례는 n=1인 경우이고, 10 미만의 소수 {2, 3, 5, 7}을 리턴해주면 된다. #include #include using names.. 2022. 9. 14.
백준 5397번 키로거 - C++ 풀이 1. 커서 앞쪽 문자와 뒤쪽 문자를 분리하여 각각 스택에 저장한다. 2. -가 들어오면 앞쪽 스택에서 pop 하고, 알파벳이 들어오면 앞쪽 스택에 push 한다. 3. >가 들어오면 뒤쪽 스택에서 하나를 pop 해 앞쪽 스택에 push 하고, 가 들어오면 뒤쪽 스택에서 하나를 pop 해 앞쪽 스택에 push 하고,가 들어오면 커서가 한 칸 뒤로 이동한다. 커서 바로 뒤에 있던 알파벳이 커서 앞으로 가는 것과 같다. 따라서 뒤쪽 스택에서 하나를 pop해 앞쪽 스택에 push 한다. > T; while (T--) { string s; cin >> s; cout 2022. 9. 8.
백준 2210번 숫자판 점프 - C++ 풀이 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다. #include #include using namespace std; int board[5][5]; unordered_set st; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void DFS(int n, int r, int c, int curr) { if (n == 6) { st.insert(curr); return; } fo.. 2022. 9. 6.
백준 2607번 비슷한 단어 - C++ 풀이 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 3. 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 두 알파벳의 등장 횟수가 각각 -1, 1 씩 차이 난다. 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 알파벳의 위치(순서)는 중요하지 않다. 각 알파벳의 등장 횟수만 같다면 같은 구성을 갖는다. 따라서 단어마다 각 알파벳의 등장 횟수를 세준다. A-Z까지 등장 횟수가 모두 일치한다면, 처음부터 같은 구성을 갖는 경우이다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, .. 2022. 9. 5.
백준 4716번 풍선 - C++ 풀이 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. A 풍선과 B 풍선의 합은 항상 K로 유지되어야 한다. 따라서 풍선이 모자라서 더 먼 곳을 택해야할 때 생기는 손해가 가장 큰 팀에게 먼저 풍선을 배부해서 손해를 줄여야 한다. 즉, | DA-DB | 값 내림차순으로 정렬한 뒤, 각 팀의 이동 거리가 최소가 되도록 배부해준다. #include #include #include using namespace std; typedef long long ll; struct Team { int k, da, db; }; int N, A, B; vector teams; bool cmp(const Team& lhs, const Team& rhs) { return ab.. 2022. 9. 3.
반응형

티스토리툴바