Doby's Lab

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 이 문제는 Topological Sort가 필요한 알고리즘으로 이에 대해 알아보자. (+공부했던 블로그 https://m.blog.naver.com/ndb796/221236874984) 어떤 일들에 대한 순서들이 주어졌을 때, 그 순서를 결정해주기 위한 알고리즘이다. 어떠한 일을 노드라고 하자. 각 노드마다 진입 차수가 존재한다. 진입 차수란 어떤 한 노드를 가리키는 노드의 개수(차수)가 몇 개인지를 나타낸다. 진입 차수가..

https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i > INF 같은 엄청 큰 값은 안 된다. 트리를 구성하는 과정에 merge를 시키는데 큰 값을 순서로 뽑기 때문에 작은 값으로 할당한다. void sgInit(int node, int start, int end){ if(start == end){ sgTree[node].first = 0; sgTree[node].second = arr[start]; return; } int mid = (start +..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 진실을 아는 사람들을 모두 같은 집합에 넣어주고, 쿼리 중에서도 진실을 모르는 사람이지만 진실을 아는 사람과 같이 있을 경우 진실을 아는 사람들의 집합에 넣어준다. 그리고, 다시 쿼리를 순회하면서(다시 쿼리를 순회하기 위해 쿼리를 담아두어야 함) 어떠한 노드가 진실을 아는 사람들의 집합에 속하기라도 한다면 바로 과장되어서 말하지 못하게 처리한다. 과정마다 getRoot(node)를 쓸 것인지, parent[..

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 처음에 고안했던 방법은 수를 선택 여부에 따라 백트래킹하여 s가 되게끔 만족하는 수의 개수 중 최댓값을 도출하려 했다. >> 하지만, 이는 엄청난 경우의 수에 따른 메모리 초과뿐만 아니라 결괏값도 도출하지 못했다. #include using namespace std; int maxValue = 0; unsigned int s; void solve(unsigned int num, int cnt, int plus){ if(num == s){ maxValue = max(maxValue, cnt); return; } so..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 분리 집합(Disjoint Set)은 Union-Find기법으로 처리할 수 있다. union: 집합을 합침 find:어떤 두 원소가 하나의 집합에 속해있는지 확인 허나, 이 Union-Find는 이미 Kruskal's Algorithm을 공부하면서 알게 되었었다. https://draw-code-boy.tistory.com/197 [알고리즘] 최소 스패닝 ..

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 이번 문제는 floydWarshall의 reverse였다. >> 최단 경로가 갱신된 그래프를 반대로 초기의 상태로 만들어야 했다. 처음에는 아래 코드 (3) 번 조건에서 갱신이 되지 않은 그래프를 만드려고 graph[i][j]값에 INF를 할당했었는데 이는 최단 경로를 역 갱신하는 과정에서 오류를 발생시킨다. INF값을 할당해버리면 그 다음 노드들을 검사했을 때, 2번 조건에 ..

https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 쿼리로 각 부분 수열을 구하여 k보다 큰 수의 개수를 원하기 때문에 부분 수열은 정렬되어있는 게 좋다. 그리고, 개수를 가져올 땐 정렬되어있는 것에서 이분 탐색을 하면 된다. 하지만, 부분 수열을 가져오면서 정렬을 계속하는 건 비효율적이다. >> 머지 소트 트리를 사용한다. #include #include #include #define MAX (100000 + 1..

https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net 부분 배열의 정렬이 필요해서 머지 소트 트리가 필요한 문제라고 느꼈다. 문제는 그다음인데 k번째 수를 가져오기 위해 쿼리 함수를 작성하는 게 어려웠다. >> 쿼리 함수는 어떤 값보다 작은 원소의 개수를 카운트할 수 있도록 작성해주었다. + 이분 탐색 사용 여기다가 어떤 값들이 들어갈지 모르고, 그 값의 범위가 크기 때문에 이분 탐색을 고려할 수 있었다. 모든 값들을 넣기엔 시간이 부담스럽기 때문이다. ..