멀티탭의 잡다한 이야기

알고리즘 종류와 유형 1. 문자열 특정 문자열 검색하기 https://www.acmicpc.net/problem/6550 문자열 정렬 https://www.acmicpc.net/problem/20291 https://www.acmicpc.net/problem/17413 https://www.acmicpc.net/problem/20210 문자열 조건 따지기 https://www.acmicpc.net/problem/17609 https://www.acmicpc.net/problem/20437 2. 분리집합(유니온 파인드) 집합성 문제 https://www.acmicpc.net/problem/1717 https://www.acmicpc.net/problem/1976 https://www.acmicpc.net/..

문제링크 : https://www.acmicpc.net/problem/1174 알고리즘 종류 : 백트래킹 솔? : 보고 함 핵심 아이디어 : 줄어드는 수의 특성을 잘 생각해서 풀어야함 #include using namespace std; int N; string num = "0123456789"; vector correct; void backtracking(int idx, string temp) { if (!temp.empty()) { string _temp = temp; reverse(_temp.begin(), _temp.end()); correct.push_back(stoll(_temp)); } for (int i = idx + 1; i < 10; i++) { temp += num[i]; backtr..

문제링크 : https://www.acmicpc.net/problem/1068 알고리즘 종류 : DFS 솔? : 답지보고함 핵심 아이디어 : DFS라는 걸 알고, vector 배열에 자식노드를 줄줄이 꿰내고 잘 삭제해내는 아이디어 #include using namespace std; int N, erase; vector tree[51]; int leap_cnt = 0; int del_node; void dfs(int idx) { bool not_leap = false; //다음번 노드를 갔는데 NULL이면 not_leap가 바뀌지 않는다. //각 노드에 물려 있는 자식들을 순회한다. for (auto next : tree[idx]) { not_leap = true; //이는 즉 말단 노드라는 뜻이다. d..

문제링크 : https://www.acmicpc.net/problem/22856 알고리즘 종류 : 트리, 구현 솔? : 답지 보고함 핵심 아이디어 : 기존 중위 순회에서 2배에서 루트 우측 트리의 우측 노드 방문 횟수를 빼누면 된다는 아이디어가 필요하다. 근데 map STL로 트리를 다루는 거도 쉽지 않다.. 중위 순회를 구현한다. 계산된 (중위순회 방문횟수)x2 - (우측트리 우특 노드 방문 횟수) #include using namespace std; int N, Data, Left, Right; //최초 노드 카운트는 제외해야하기 때문에 -1로 설정 int cnt = -1, Rcnt = -1; map tree; void input() { scanf("%d", &N); for (int i = 1; i

https://www.acmicpc.net/problem/15486 알고리즘 종류 : 동적계획법 솔 ? : 보고함 접근 방법: 뒤에서부터 해당 날짜의 최대 수익을 DP에 저장하며 첫날의 최대수익을 출력한다 상담 날짜가 지나면 이전 날 최대수익을 가져옴 [X날에 상담을 했을때 수익]+[X상담에 드는 날만큼 빠진 수익]과 X날 전날까지의 수익을 비교해 더 큰놈을 DP 넣는다. #include #include #include #include using namespace std; int T[1500010]; int P[1500010]; int DP[1500010]; int main(void) { int N; scanf("%d", &N); for (int i = 1; i = 1; i--) { //max(DP[i+..

https://www.acmicpc.net/problem/14594 #include using namespace std; int main() { int N, M; int ranX[100]; int ranY[100]; int cnt = 0; bool wall[101]; fill_n(wall, 100, true); cin >> N; cin >> M; for(int i = 0; i > ranX[i] >> ranY[i]; } //입력단 for(int i = 0; i < M; i++) { for (int j = ranX[i]; j < ranY[i]; j++) { wall[j] = false; } } for(int i = 0; i < N; i++) { if(wall[i]){ cnt +=..