https://www.acmicpc.net/problem/17615문제조건파랑/빨강 볼이 일직선상에 놓여있다.같은색 볼끼리 인접하게 놓으려고한다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다옮길 수 있는 볼의 색깔은 한 가지이다.접근방법 이중 for문으로 단순하게 풀수 있겠다라고 생각했지만, 입력값이 무려 50만,,,, 무조건 O(n log n)시간안에는 끝내야한다.어떻게 깔끔한 방법이 없을까 생각을 해보다가 아무리 생각해도 방법이 떠오르지않아서, 경우의수 4가지를 하나씩 직접 구현하고, 비교해줬다.두개의 색깔만 존재하므로, 중간에 볼이 끼어서 존재할수 없고, 무조건 한쪽으로 몰려서 절반으로 나뉠수밖에없다.선형탐색을 진행하며 다른 색의 공이 있으면, 뛰어넘어서 위치를 뛰어넘을..

https://www.acmicpc.net/problem/2463문제조건가중치그래프가 존재한다.서로다른 정점 u, v에 대해서 경로가 있다면 경로가 없을때까지 최소 가중치 간선을 제거한다. u 접근방법 딱봐도 MST(최소비용신장트리)와 정말 유사하게 동작하는 문제였다. 그리디한 접근법인 Prim, Kruskal 알고리즘을 떠올렸는데, 이 알고리즘의 핵심은 서로소 분리 집합으로 초기에 모든 노드(정점)을 각각 독립적인 집합으로 초기화 시킨후, 집합이 하나가 될때까지 최소비용인 간선들을 더해가는 것이다. Kruskal 알고리즘과 이 문제의 차이점은, 최대 가중치를 가진 간선부터 그래프에 추가한다는 점이다. 간선의 가중치를 내림차순으로 정렬한다.임의의 간선부터 시작해서 정점이 속해있는 집합이 서로다른 경우에만..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제조건 주식하나 사고, 팔고, 아무것도 안하는 것중 하나만 할 수 있다. 각 날마다의 주가가 주어지고, 조건 1 을 반복하면서 최대이익을 구한다. 이 문제는 예시로 시작하는 것이 편할거 같다고 생각한다. ex) 날 별로 주가가 3, 5, 9일 때 : 3, 5 두 날 전부 주식을 사고, 9일때 주식을 팔면된다 산금액 : 8(3x1 + 5x1) 판금액 : 18(9 x 2) 최대이익 : ..

https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 문제조건 0과 1로만 이루어진 문자열 S가 있음 0과 1의 개수가 각각 짝수개임 각각 절반의 개수를 제거했을때, 사전순으로 가장 빠른 문자열 구하기 1분만에,,? 풀었나,,? 이렇게 쉬운게 왜 정답률이 50%가 안되지 라고생각하며 풀었다. #include #include using namespace std; //S가 포함하는 0과 1의 개수 모두 짝수 //절반 제거후 사전순으로 가장..