목록문자열 (43)

1일1알

백준 9935번 문자열 폭발 C++

1. 문자열을 처음부터 순회하면서 스택에 하나씩 넣는다. 2. 폭발 문자열의 마지막 문자와 지금 순회중인 문자가 같다면 스택에서 폭발 문자열의 크기만큼 뺀다. 3. 뺀 문자열과 폭발 문자열을 비교하여 같다면 그대로 지나가고 같지 않다면 뺀 문자열을 다시 스택에 넣는다. 4. 순회가 끝났으면 스택에서 문자를 전부 빼서 역순으로 출력한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(f..
알고리즘 2022. 3. 28. 12:10
백준 1120번 문자열 C++

A에만 문자를 추가할 수 있기 때문에 b 안에서 a와 가장 비슷한 문자열을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str1, str2; cin >> str1 >> str2; int ans = 50; for (int i = 0; i < str2.length(); i++) { if (i + ..
알고리즘 2022. 3. 24. 11:59
백준 12904번 A와 B C++

처음에는 S에서 백트래킹을 해서 T로 가는 방법을 생각해봤는데 범위를 보니 무조건 시간초과가 날 것 같아서 다른 방법을 생각해 보았다. T에서 S로 거꾸로 거슬러 올라가는 방법으로 문제를 해결하였다. T의 맨 뒤가 A라면 그냥 A를 빼고 T의 맨 뒤가 B라면 B를 빼고 문자열을 뒤집어준다. 이걸 반복하다가 S와 길이가 같아졌을 때 S와 T가 일치하면 S로 T를 만들 수 있는 것이고, 일치하지 않는다면 만들 수 없는 것이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = l..
알고리즘 2022. 3. 18. 11:19
백준 2418번 단어 격자 C++

1. 3차원 dp 배열을 만든다. dp[ 행 ] [ 열 ] [ 문자열 크기 ] 2. 문자열의 0번 원소와 같은 행과 열의 dp [ 행 ][ 열 ][0] 을 1로 설정한다. 3. k를 1부터 문자열 크기 - 1 까지순회하면서 k번째 원소와 같고 주변에 k-1번째 원소가 있다면 dp[i][j][k]에 dp[주변 행][주변 열][k - 1]을 더해준다. 4. 모든 dp[행][열][문자열 크기 - 1]을 더한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; ..
알고리즘 2022. 2. 14. 11:15
백준 1802번 종이 접기 C++

종이의 중간지점을 정해서 접었을 때 대칭되는 점들이 모두 다르다면 동호의 규칙대로 접을 수 있는 것이다. 종이가 전부 접힐 때까지 분할 정복을 통해 해결할 수 있다. 그리고 문자열의 길이가 항상 2^n - 1이라고 했기 때문에 길이가 짝수가 되는 경우는 고려하지 않아도 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; bool isAns = true; string str; void rec(int idx, int n) { if (n == 0) retu..
알고리즘 2022. 2. 6. 14:55
백준 6576번 쿼드 트리 C++

분할 정복으로 n * n 의 픽셀을 구하고 그것을 16진수로 출력하는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; string str; int idx = 0; void rec(vector& board, int row, int col, int n) { if (idx >= str.length()) return; if (str[idx] == 'Q') { idx++; rec(board, row, col, n / 2); rec(board, row, ..
알고리즘 2022. 2. 6. 14:49
이전 Prev 1 ··· 3 4 5 6 7 8 Next 다음