11659번: 구간 합 구하기 4 (acmicpc.net) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 인접리스트, DFS * 주의 1. 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다. 2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다. 3. 내림차순으로 정렬해줘야 한다. sort는 less가 default이기 때문에 greater..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 인접리스트, DFS * 주의 1. 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다. 2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다.

17472번: 다리 만들기 2 (acmicpc.net) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 유니온 파인드, 크루스칼, BFS void InputFunc(); - 입력 받는 함수 void CreateGroup(); void CreateGroupBFSFunc(int pX, int pY, int pGroupNum); - 섬을 찾아서 그룹을 만들고 번호를 부여함. void BridgeConnection(); void FindAllBridge(int pX, int pY); - 동서남북 ..

1976번: 여행 가자 (acmicpc.net) 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다. ..

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가 주어지..