while(1) 작심삼일();

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) 최악(둘 다 마지막에 도착)을 고려하더라도 O(2N) 이기에 O(N)이 된다. #include using namespace std; int arr[100001]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이) 팀이 구성됐건, 안됐건 한번도 방문한 적 없는 정점을 dfs를 돌린다. 처음 시작 값을 havaTeam에 다 넣고, selected에는 개수들을 넣어둔다. 이후 어느 값이건 순환이 되어 돌아온 시점이 되면, 그 값이 처음 시작 값인 지 확인을 하고, 1 -> 2 -> 3 -> 2 와 같은 잘못된 순환은 팀이 될 수 없으므로 0을 리턴시키고, 원래 시작 값으로 돌아왔다면 팀이 정상적으로 꾸려진 것..

http://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이) 음수 + 0 부분과 1 이상인 부분을 나누기 위해 one_idx를 먼저 잡은 뒤, 작은 쪽부터 수들을 묶어줬다. 양수를 묶을 때 체크할 부분은 1 + 1, 1 + 2는 곱한 것 보다 더한 것이 더 크기 때문에 이 부분을 따로 처리해주어야 한다. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.t..

http://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이) bfs를 통해 방문하지 않은 곳을 전부 색칠한다. 여기서 나와 연결되어 있는 정점들은 계속 반대의 색상을 넣어준다. 전부를 돌면서 다 색상을 칠한 뒤 이분그래프의 개념과 동일하게 다 맞게 칠해졌는지 확인한다. 참고 : ko.wikipedia.org/wiki/이분_그래프 #include #include #include #include using namespace std; int K..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이) 위상정렬 알고리즘으로 해결할 수 있었다. 선행 작업들에 대한 차수를 inDegree 배열에 담아두고 0인 것부터 하나씩 꺼내서 계산해두고 꺼내진 정점과 연결되어 있는 작업들의 차수를 하나씩 내려주고 다시 0이 된 것들이 있다면 큐에 담아서 직전 과정을 반복하는 과정으로 해결할 수 있었다. 이번 문제와 같은 의존관계를 가지고 있는 그래프를 의존성 그래프라고 하는데, 이런 그래프에는 ..

http://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이) 크루스칼 알고리즘을 이용하기 위해 간선 가중치를 기준으로 오름차순으로 정렬해주었고 이후 union-find 알고리즘을 사용하여 싸이클을 확인한 후 같은 집합이 아니라면 추가해주는 방식으로 해결하였다. #include #include #include using namespace std; int V, E, s, e, w, ans = 0; int pa..