16139번: 인간-컴퓨터 상호작용 (acmicpc.net) 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net * 이 전의 누적합으로 사용했던 배열 SumArr[MAX]를 알바벳 개수 만큼 증가 시킴. -> SumArr[26][MAX] #include #include #include #include using namespace std; #define MAX 200'001 int SumArr[26][MAX]; // 구간 합. int main(void) { ios_b..

2559번: 수열 (acmicpc.net) 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적 합 * 가장 큰 값만 찾기 때문에 priority_queue 사용함.(기본 정렬 = less) * S값보다 크거나 같을 때부터 누적 합을 해주어 queue에 넣어줌. #include #include #include #include using namespace std; #define MAX 100'001 int SumArr[MAX], Arr[MAX]; // 구간 합. int main(void) { ios..

10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net ※틀린 답: 시간초과 (N^2) 왜 틀렸는지.. 그럼 어떻게 풀어야하는지.. 질문검색을 뒤져보는 중에.. 무슨 말이지??? .. 그래서 예제를 이용해서 천천히 정리해보았다. 1. 부분합을 M으로 나눈 나머지가 같은 것끼리 그룹을 짓는다고 생각해봅시다. SumArr[i] = (Arr[i] + SumArr[i-1]) % M; 범위 (1,1) (1,2) (1,3) (1,4..

11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 1. "11659 - 구간 합 구하기4"를 2차원으로 변형한 문제라고 접근했다. 2. 동일한 크기의 행렬을 하나 더 만들어 입력을 받는 동시에 이전의 합과 현재값을 더하여 index 1 ~ index 현재까지의 합을 구해주었다. 3. begin : (x1, y1) end: (x2, y2) 로 구분하여 end부터 begin까지의 합을 구해주었다...

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 값을 표현한 것이다. ..