20040번: 사이클 게임 (acmicpc.net) 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 사이클 찾기: 여기서 빨간색 줄을 마지막으로 연결한다고 가정했을때, 왼쪽은 3번 키값의 value는3, 5번키값의 value는 3으로 같고, 오른쪽은 5번 키값의 value는3, 1번키값의 value는 1로 다르다. 이렇게 사이클은 새로운 edge를 추가할때 출발점의 부모와 도착점의 부모가 같으면 사이클이 발생했다고 판단한다. 3. 구현:

문제링크: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 안녕하세요. 핑크코냥입니다. 1780번 종이의 개수 문제는 분할정복의 기본적인 틀에서 개수만(?) 조금 늘린 문제입니다. 문제에서 요구하는 것을 간단하게 정리해보면 아래와 같습니다. 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. 2. (1) 이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각 잘린 종이에 대해서 (1) 의 과정을 반복한..

문제 링크: https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 파일 입출력이 약간 까다로운 댁 응용문제였다. 간단하게 문제의 조건을 요약해보자면, 1. Ac는 정수 배열에 연산하기 위해 만든 언어 2. R(뒤집기) - 배열에 있는 수의 순서를 뒤집는 함수 3. D(버리기) - 첫 번째 수를 버리는 함수 4. 함수는 조합해서 한 번에 사용할 수 있다. ex) RDDD, DDRD, RDRD 뒤집기를 reverse를 처음에 이용해서 코드를 작성했지만, 알고리즘 분류에 "덱"이라고 쓰여있어서 bool 값으로 ..

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net * 문제 풀이 알고리즘 문제 내에 있는 예제를 예시로 들면, {1 5 2 1 4 3 4 5 2 1} 에서 가장 긴 바이토닉 부분 수열은 {1, 2, 3, 4, 5, 2, 1} = 답 7이 됩니다. 밑에 작성한 알고리즘은 왼쪽에서 부터 증가하는 부분 수열의 DP(InC)와 오른쪽에서 부터 증가하는 부분 수열의 DP(DeC)를 구해서 그 합 중 가장 큰 수가 해답이 되도록 작성하였습니다. InC = { 1, 2, 2, ..

문제를 풀기만을 위한 코드 이여서 좀 복잡해 보입니다. 한 4번 틀렸는데 양방향을 고려해야하기 때문에 vec에 1->2 (가중치: 4)이면 vec에 양방향으로 움직일 수 있도록 vec[a].push_back(make_pair(c, b)); vec[b].push_back(make_pair(c, a)); 이렇게 넣어주시면 됩니다. 그리고 계속 틀려서 봤더니 inf가 int 범위를 넘어버리면 음수가 되기때문에 마지막 결과를 inf만 고려하는 것이 아니라 음수도 고려해주셔야 합니다. ^^

문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지..