SCCC - Soongsil Computing Contest Club
-
9. 그래프, dfs, bfsSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 15:10
복습 그래프 그래프는 간선으로 연결된 정점들의 집합이다. 인접 행렬은 N제한이 적을 때 사용한다. 보통은 인접 리스트로 구현하지만, 말 그대로 연결리스트를 사용하지는 않고, vector를 사용할 것이다. 배열을 정점 개수만큼 잡아주고, 정점이 이어질때마다 하나씩 추가해준다. 단방향그래프 directed graph 방향이 있는 그래프. 한쪽 방향으로만 이동 가능 양방향그래프 undirected graph 방향이 없는 그래프. 양쪽 방향으로 모두 이동 가능 사이클 cycle 한 정점에서 출발해서 중복된 간선을 거치지 않고 다시 해당 정점으로 올 수 있으면 cycle이 있다고 한다. 트리 tree 사이클 없는 그래프. 루트 root 루트가 있는 트리, 루트트리는 부모자식관계를 정의할 수 있다. 트리 트리에서는..
-
8. dp - 토글링, 역추적SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 22. 14:31
복습 우선 오늘 배울 것은 dp개념이 잡혀있지 않다면, 필요가 없다. dp를 조금 풀고 와서 하는게 좋다. 토글링 현재까지, 대부분의 문제는 128MB 이상의 넉넉한 메모리 제한을 갖고 있다. 따라서 배열의 크기를 별로 상관하지 않고 문제를 풀 수 있었다. 하지만, 출제자가 의도적으로 메모리 제한을 굉장히 낮게 한다면, 우리는 머리를 조금 더 써야한다. 바로 여기서 토글링의 개념이 나온다. 이전값, 현재값, 다음값 이 세가지 값 외에 다른값은 쓰이지 않을 때, 우리는 토글링을 사용하여 배열을 축소할 수 있다. 2의 나머지의 성질을 이용하여 [i%2]의 값을 이용하여 [(i+1)%2)]의 값을 채우고, 그 다음엔 (i+2)%2 == i%2 이므로 다시 [i%2]의 값을 채우면 되는것이다. 참고 문제 : b..
-
7. dp - LCSSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 21. 13:39
복습 boj.kr/13301, boj.kr/17391 LCS(Longest Common Subsequence) ACAYKP, CAPCAK이 있을 때 최장 공통 부분 문자열을 구해보자. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 dp[i][j] = 첫번째 문자열의 i번째, 두번째 문자열의 j번째까지 봤을 때 가장 긴 공통 부분 문자열 arr[i] == arr[j] 일 때 dp[i][j] = dp[i-1][j-1] + 1; arr[i] != arr[j] 일 때 dp[i][j] = max(dp[i][j-1], dp[i-1][j]); 참고 문제 : boj.kr/9251, boj.kr/..
-
6. dp : LIS, KnapsackSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 16. 02:24
오늘도 dp. 가장 긴 증가하는 부분 순열 Longest Incresing Subsequence 11053번 문제를 보면서 생각해보자. dp[i] : i번째 원소가 마지막인 가장 긴 증가하는 부분 수열 예를 들어 10, 20, 10, 30, ... 이렇게 있을 때 dp[1] = 1 dp[2] = 2 dp[3] = 1 dp[4] = 3 ... dp[i] = max(dp[j]) + 1 (if arr[j] > N; for(..
-
5. 1차원, 2차원 dpSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 15. 00:30
DP = 디피 = 다이나믹 프로그래밍 = Dynamic Programming 문제를 쪼개서 해결하는 방법의 한 분류. 주어진 초기값을 바탕으로 순차적으로 값을 메모를 해가면서 구한다. 1차원 dp (1)피보나치 수 그냥 재귀적으로 해결하면 O(2^N)이 걸리지만, DP를 사용하면 O(N)이 걸린다. 다음은 for문을 이용한 dp #include using namespace std; int dp[100]; int main(){ int N; cin >> N; dp[0]=0; dp[1]=1; // 초기값 설정 for(int i=2; i
-
4. 정수론-소인수분해, gcd, lcm, sieveSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 14. 02:51
복습 mod n 덧셈 7 = 3 (mod 4) ex) a+b = (a+b)%n (mod n) 7 + 9 = 16 = 0 (mod 4) 3 + 1 = 4 = 0 (mod 4) 12312312 + 234234234 = 0 + 2 = 2 (mod 4) 곱셈 7*9 = 63 = 3 (mod 4) 3 * 1 = 3 (mod 4) 즉, 미리 mod를 적용해주면 식이 간단해진다. 답이 심각하게 커지는 경우, mod를 많이 쓰며 나중에 다이나믹 프로그래밍에서 많이 나온다. 참고 문제 : [boj.kr/17466] 소인수 분해 어떤 수를 소인수 분해 하려면, 2부터 sqrt(N)까지 원소들의 조건을 따지면서 분해하면 된다. (1) N이 합성수인 경우, N = p1^r1 * p2^r2 * p3^r3 * ... * pk^r..
-
3. heap, priority_queue, set, mapSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 9. 20:49
0. 복습 boj.kr/10989 (counting sort), boj.kr/1427 heap 자료구조. push, pop이 있음. heap의 push는 스택과 동일하지만, pop은 가장 큰 값(max heap), 또는 가장 작은 값(min heap)을 뺀다. 구현은 트리로 한다. min heap은 부모보다 자식이 더 크고, max heap은 부모가 자식보다 더 크다. 기본적으로 push는 O(N)의 시간복잡도를 가지고 있지만, 힙의 push는 O(logN)만에 가능하다. 트리의 가장 끝에 원소를 넣고, 자신의 부모와 비교한 후 필요하면 swap한다. pop도 O(logN)이다. 트리의 루트를 pop하고, 자식들과 값을 비교 한 후 트리에 값을 메운다. 힙 구현 #include #include #incl..
-
2. pair, sort, binary searchSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 1. 8. 02:51
복습 boj.kr/1001 pair #include using namespace std; int main(){ pair mypair; cin >> mypair.first >> mypair.second; cout > c >> d; A.push_back(a); B.push_back(b); C.push_back(c); D.push_back(d); } for(int i=0; i
-
다익스트라(dijkstra)SCCC - Soongsil Computing Contest Club/2019 Spring-Study 2019. 6. 3. 01:25
1. 다익스트라 특정 하나의 노드에서 각 노드까지의 최단길이를 모두 구하는 알고리즘. 제일 작은 노드 탐색 갈 수 있는 노드들 값 갱신 이거 1,2 무한반복 : 다익스트라. 쉽죠? 일종의 그리디라고 할 수 있는 다익스트라. 그리디의 모순에 의한 증명으로 증명 할 수 있다. >>위의 알고리즘을 사용해서 최단경로를 만들었을 때 다른 노드를 경유하여 들어오는 경로가 최단이지 않으면 증명 완료. 대표적인 다익스트라 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V..