https://www.acmicpc.net/problem/12019 12019번: 동아리방 청소! 첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 www.acmicpc.net 날짜, 청소할 수 있는 횟수, 이전에 청소한 날짜를 고려한 다이나믹 프로그래밍을 통해 문제를 해결했다. vector dirty_sum(101, 0); 에 누적합을 구하는 방식으로 [날짜] = 더러움 (청소를 안 한다고 했을 때)를 저장하여 이전에 청소한 날짜를 알았을 때 현재 불쾌함을 구할 수 있도록 했다.((dirty_sum[here] - dirty_sum[before_clean + 1]) * ..

https://www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net 투 포인터를 이용하여 문제를 해결했다. right + 1이 right보다 크다면 증가하는 부분이므로 right를 오른쪽으로 옮겨가다가 right+1이 right보다 작은 구간을 만났을 때 right를 가운데로 하여 왼쪽과 오른쪽을 체크해 나아가는 방식으로 문제를 해결했다. 그리고 다음의..

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 타잔 알고리즘을 이용하여 SCC를 구하고 SCC들 사이의 그래프를 만든다. 그리고 출발지 SCC에서 다익스트라를 이용해 각 SCC까지 갈 때 얻을 수 있는 최대 돈을 구하고, 아웃백이 있는 SCC 중 최대 값을 구해서 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n..

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 타잔 알고리즘을 이용해 강한 연결 요소 (SCC)를 구해서 문제를 해결했다. 코드 #include #include #include #include using namespace std; //강한 연결 요소(SCC)알고리즘 공부 //타잔 알고리즘 int v, e; vector adj[10001]; vector node_numbe..

https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 출발 도시에서 도착 도시로 최소비용으로 가는 것을 다익스트라를 이용해서 구하는데, 이때 몇 개의 간선을 지났는지에 따라 최소비용을 따로 구하는 방법으로 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, m, k; int s..

https://www.acmicpc.net/problem/16571 16571번: 알파 틱택토 현재까지 진행된 틱택토 게임 보드가 띄어쓰기로 구분되어 3줄에 걸쳐 주어진다. 0은 빈칸, 1은 X, 2는 O를 의미한다. 단, 항상 X가 선공이다. 그리고 이미 게임이 종료된 상태는 입력으로 주어지 www.acmicpc.net 현재 플레이어가 승리하면 1, 무승부면 0, 패배하면 -1을 반환하는 함수를 만들었다 그러므로 다음 플레이어가 최대한 작은 값을 반환하도록 해야 한다. 그리고 map을 이용하여 같은 보드 상황의 값을 다시 계산하지 않도록 했다. 코드 #include #include #include #include #include using namespace std; //알고리즘 문제 해결 전략 책 공부..