Doby's Lab

격리 동안 코딩이나 포스팅을 못 하고 있으니 답답하다. 코딩도 어플을 이용하여 하고 있지만 불편하다. 빨리 격리 풀리고 풀었던 문제랑 공부한 알고리즘 포스팅 해두고 싶다! Edmonds-Karp랑 Euler Tour Technique 정리 되었으면!! Edmonds-Karp를 비롯해서 Bipartite Matching까지 공부하고 싶다.. 아직은 Edmonds-Karp랑 친해지는 중이다.. https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제를 읽어보면 간단한 위상 정렬 문제인 것 같지만, 문제에서 주어진 3번 조건 "가능하면 쉬운 것부터 풀어야 한다."가 발목을 잡게 된다. >> 위상 정렬을 하되, 오름차순으로 우선순위 큐에 집어놓고 위상 정렬을 돌리면 해결 가능하다. [AC 코드] #include #include #include #define MAX 32001 using namespace std;..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터 알고리즘을 이용하여 O(N)만에 풀 수 있는 문제였다. 이번 문제에서 겪었던 어려운 점은 투 포인터의 반복문을 돌리면서 '어떻게 조건을 분기시키며 그 조건 결과에는 어떤 연산을 시켜야 할까'가 고민이었다. 투 포인터라는 이름에 꽂혀서일까 두 개의 조건으로만 분기하려 했었다. sum이 s보다 클 때 sum이 s와 같을 때 sum이 s보다 작을 때 이 3가지를 따지면 그에 맞..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 종종 유용하게 사용되는 테그닉, 투 포인터(Two Pointers)에 대해 알아보자. 예를 들어, 배열 A가 존재한다고 했을 때, 링크를 걸어둔 문제처럼 A[i] + A[i+1] + … + A[j-1] + A[j] 중 M이 되는 경우의 수를 구하라 했을 때, 어떻게 할 것인가? 구간 합이라 세그먼트 트리를 이용해야 할 거 같지만 세그먼트 트리를 구성한 다음..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 어떤 건물이 지어지기까지 특정한 건물이 지어져야 한다는 전제 조건이 존재한다. 즉 건물이 지어지는 데에 순서가 있다는 뜻이다. "N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다."라고 되어있는데 여기서 오해를 하여 해석한 부분이 어떤 건물을 짓는데 걸리는 최소 시간으로 해석했다. >> 즉, 최단 경로처럼 이해했다는 말이고, 이 문제는 "어떤 건물이 지어지기까지 특정한 건물이 ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 각 쌍들 간의 관계로 키를 작은 순서대로 세운다. >> Topological Sort를 떠올릴 수 있다. [AC 코드] #include #include #include using namespace std; int n, m; int inDegree[32001]; vector adj[32001]; vector result; void topologicalSor..

직전 포스팅 백준 1005번을 풀면서 겪었던 오류가 있었다. 전위 연산자와 후위 연산자와 관련된 문제였다. 매일 for문을 돌리면서 후위 연산자만 썼었는데 이 기회에 정리해두자. 우선 예제 코드를 만들어보자. n1과 n2 둘 다 1로 선언 후, n1은 Prefix Operator, n2는 Postfix Operator로 연산한다. #include using namespace std; int main() { int n1 = 1; cout 즉, 중괄호 맨 처음에 오는 부분을 기준으로 우선순위를 결정한다는 생각이다. 후위 연산자 주관적 정리 (증감)(1) -> (비교)(2) -> {(할당)(1), (덧셈, 뺄셈)(2)}(3) 그럼 마찬가지로 전위 연산자는 연산을 수행한 후, 값을 할당한다고 했다. 이 점을 바..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 언뜻 보기에는 최단 경로를 구하는 문제인 듯해 보이지만 간선이 아닌 노드에 건물의 시간 값이 들어있기 때문에 최단 경로 문제가 아니다. 어떤 한 노드로 가는 길에 건물들을 다 짓는 데 걸리는 시간을 구하는 문제다. 건물을 짓는 데에는 순서가 있고, 이 순서를 코드로 짜야하는데 이 시점에서 Topological Sort를 떠올릴 수 있다. 문제에 나와있는 예시처럼 1번에서 4번 건물까지 지으려..