본문 바로가기

분류 전체보기76

[2252] 줄 세우기 // 2252 줄 세우기 // topology sort #include #define NMAX 32001 using namespace std; int N, M; int s, e; int visited[NMAX]; int inputEdgeCount[NMAX]; vector ordered; vector adj[NMAX]; void dfs(int u){ visited[u] = 1; for(int v: adj[u]){ if (visited[v] == 0) dfs(v); } // 목적지 -> 출발지 역순으로 들어감 ordered.push_back(u); } vector topologicalSort(int N){ // 초기화 ordered.clear(); memset(visited, 0, sizeof(visited.. 2024. 2. 19.
[1717] 집합의 표현 // 1717 집합의 표현 // union find // 경로압축 -> 대표 루트로 업데이트해준다. #include #define NMAX 1000001 using namespace std; int n, m; int cmd, a, b; int parent[NMAX+1]; int getParent(int a){ if(parent[a] == a) return a; return parent[a] = getParent(parent[a]); // find 한 값을 배열에 저장 후 반환 //return getParent(parent[a]); } bool find(int a, int b){ // 같은 집합이면 true, 아니면 false int x = getParent(a); int y = getParent(b); .. 2024. 2. 19.
[2042] 구간 합 구하기 // 2042 구간 합 구하기 // segment tree #include #define NMAX 1000000 using namespace std; int N, M, K; int a, b; long long c; // 입력의 수는 -2^63 ~ 2^63-1 int start; long long ans; long long tree[NMAX*3]; // 값 추가 되었을 때 업데이트 // b번째 수를 c로 바꾼다. // 현재 값과 새로운 값의 차이만큼 루트노드로 올라가며 값을 갱신 void update(int idx, long long value){ // 값 교체 idx = idx + start; tree[idx] = value; // 그 위의 값들 갱신 for(int p = idx/2; p > 0; p =.. 2024. 2. 15.
0214 MEMO 0214 1) DP 2) 트리 3) 힙, 우선순위큐 4) 트라이, 해시 # 참고 ios::sync_With_stdio(0); cin.tie(0); # 배열 초기화 memset(visited, -1, sizeof(visited)); # split대신 !strcmp(cmd, "push") // 있으면 1 # replace str.replace(문자열 시작 위치, 사이즈, 치환할 문자열); std::replace(s.begin(), s.end(), x, y); # 자료형 int long // 배열이 너무 크면 ? # 힙 // 선언 priority_queue heap; // 올림차순 - 최소힙 priority_queue heap; // 내림차순 - 최대힙 (default) // 추가 및 삭제 -> O(logN).. 2024. 2. 14.
1202 보석도둑 // 1202 보석도둑 -> 왜 시간초과일까 ㅜ // heap 응용 #include using namespace std; int x; int n, k; int m, v; int bagg; int res = 0; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; // 1 ~ 300,000 priority_queue pq; // 올림차순 - 최대힙 // val, mass for(int i=0; i> m >> v; pq.push(make_pair(v, m)); // value -> mass 순 } priority_queue bag; for(int i=0; i> bagg; bag.push(bagg); } // 각 가방에 보석 하나씩 배치 for(.. 2024. 2. 14.
[1991] 트리순회 // 1991 트리순회 // 이진트리 -> map, pair 이용 #include using namespace std; int n; map tree; char a, b, c; void preorder(char node){ // 전위순회 cout a >> b >> c; tree[a] = make_pair(b, c); } // 항상 A가 루트노드 preorder('A'); cout 2024. 2. 14.

티스토리툴바