mintuchel mintuchel

자음 모음 개수 판단을 위해 bitset &연산을 사용하였다. if (cnt==L && (ans & vowel).count() >= 1 && (ans & constants).count() >= 2) { print(); return; } DFS는 오름차순 생각해서 돌려줌. #include #include #include #include using namespace std; vector alphabet; bitset ans; bitset vowel; bitset constants; // 모음 1개 자음 2개 // 오름차순 int L,C; void print() { for (int i = 0; i < 26; i++) { if (ans[i]) cout = 2) { print(); return; } for (in..

가장 기본적인 순열문제임 백트래킹으로 풀면 된다 123 213 이 다르므로 DFS안에서 무조건 첨부터 끝까지 돌게 하면 된다 #include #include #define SIZE 11 using namespace std; bool visited[SIZE]; int arr[SIZE]; vector ans; int N, M; void print() { for (int i = 0; i < M; i++) cout M; for (int i = 1; i

지금까지 푼 DFS/BFS 문제 중 제일 난이도 있는 문제였음풀면서 BFS뿐만 아니라 그 외 것들을 구현하는데 생각을 더 해야했음 1. 우선 가장 중요한건 BFS돌면서 빙하를 녹이면 안된다는거임 왜냐하면 하면서 녹이면 그 다음꺼가 바다랑 맞닿는 면의 개수에 영향을 끼치기 때문그래서 녹일 양을 따로 저장해야함 2. 그 다음으로 중요한게 2분할 됐냐 확인하는거임 이건 모든 원소 다 돌면서 visited 됐는지 확인하고 BFS돌리고 그러면서 cnt++ 해서 판단가능함 BFS 한 턴으로 다 돌면 정상이고BFS가 두 턴 이상 나오면 breakBFS가 0이면 다 녹았다는 뜻이므로 종료 BFS가 0번이면 그건 다 녹을때까지 cnt가 두 번 이상 안나왔다는 뜻이므로 바로 종료해주면 된다  for (int i = 0; ..

간단한 누적합 + 슬라이딩 윈도우 문제 한 칸 뒤에꺼 더해주고 맨 앞에꺼 빼주고이거 반복하면 된다#include #define SIZE 100001using namespace std;int pay[SIZE];int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; for (int i = 1; i > pay[i]; long long sum = 0; long long ans = 0; for (int i = 1; i M) sum -= pay[i - M]; if (sum > ans) ans = sum; } cout

+ 24.8.17 다시 품 더 빨라졌다ㅎㅎ 그냥 일반적인 조합론 문제이다집이랑 치킨집의 좌표에 대한 정보를 희소행렬로 저장해주고조합따지기 위해 재귀 돌리다가 치킨집이 M개가 모였을때의 계산로직만 짜주면 된다 #include #include #include #include #define SIZE 13#define INF (int)1e9using namespace std;int N, M;vector> chicken;vector> home;bitset visited;int ans = INF;void solve(int start, bitset visited) { // M개일때 종료 if (visited.count()==M) { int dis = 0; int cy, cx, hy, hx; int nearest..

조합론 + 비트마스크 문제이다 사실 DFS 문제이긴 한데 비트마스크 쓰는 부분이 훨씬 눈여겨볼만 한거 같아 비트마스크 쪽에 놓는다. 초반에는 5x10짜리 2차원 배열을 통해 나타내려고 했는데 비트마스크가 훨씬 깔끔할거 같아서 비트마스크로 품 일단 총 50시간을 표현하려면 32bit로는 부족하므로 64bit인 long long을 써줌 그리고 각 시간표를 비트로 나타내야하는데 이건 이렇게 하면 됨 각 요일마다 10시간이므로 특정 요일을 표현하려면 해당 요일 (정수값-1)*10 만큼 옮겨주고 해당 요일에서 끝나는 시간대를 통해 얼마나 더 shift 해줘야하는지 알아내면 됨 금요일은 아예 저장하지 않아도 되니까 입력받을때 무시하면 됨 해당 강의를 들을 수 있는지 확인하고 백트래킹으로 풀면 된다 백트래킹인 부분이..

그냥 bitset 으로 풀어도되는데 비트연산 연습겸 비트연산으로 품! check 문은 1 M; for (int i = 0; i > str; if (str == "all") { data = (1 > x; if (str == "add") { data |= 1

배정가능한 예산 중 최대값을 찾는 것이므로 이분탐색으로 해결 가능 이분탐색하는 binarysearch함수는 left right이 된다 그림을 그려보면 #include #include #define SIZE 10000 using namespace std; int arr[SIZE]; int N,M; // 이 함수는 최적의 최대값을 찾기 위해 동작함 // 즉 left M) { right = mid - 1;} // sum값 늘리기 else if (sum < M) { left = mid + 1; prev = mid; } else { prev = mid; break; } } return prev; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); c..

이진탐색트리 그냥 이진트리랑 다르고 힙이랑도 다른거임 #pragma warning(disable:4996) #include #include typedef int BData; typedef struct _node { struct _node* left; BData data; struct _node* right; }Node; typedef struct _BinarySearchTree { Node* root; }BST; void BSTInit(BST* bst) { bst->root = NULL; } void BSTSearch(Node* curNode, int x) { if (curNode == NULL) { printf("Cant find x!\n"); return; } if (curNode->data == x..

DFS 재귀로 풀어주면 된다. 맨 밑 leaf node까지 재귀로 내려가준 다음에, 해당 노드부터 생존수를 계산하여 루트노드까지 올려보내면 된다 일단 조건을 보면 한 섬에는 양 또는 늑대가 삼. 즉 둘 중 하나임. 조건 상 뭐든 살아 그래서 양이면 num을 +값으로 놓고 늑대면 num을 음수로 놓으면 됨 부호가 양/늑대 구분하는 기준인거임 그리고 양이 다 죽으면 0이지 -200 이런 숫자는 말이 안되니까 sum 조건 상 이게 늑대든 양이든 뭐든 살아 int arr[SIZE]; vector tree[SIZE]; bitset visited; long long DFS(int v) { visited[v] = 1; long long sum = 0; for (auto it = tree[v].begin(); it !..