문제: www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제풀이 최소 힙의 구현 문제이다. C++ STL을 이용하면 쉽게 풀 수 있다. 코드(직접 구현) #include using namespace std; int rear=0; int arr[100005]; void push(int); void pop(); bool empty(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i..

문제: www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이 입력되는 좌표 Xn에 대하여 Xn 보다 작은 좌표의 수를 각각 출력해주는 문제이다. 좌표의 개수는 1000,000으로 1000,001 크기의 벡터를 선언하여 벡터의 인덱스를 이용해 문제를 풀었다. pair 벡터를 선언해 {좌표, 순서} 순으로 저장하고 좌표를 기준으로 오름차순 정렬했다. 이후 벡터를 탐색해 좌표 크기 순서대로 정답 벡터에 압축한 ..

문제:www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제풀이 BFS/DFS를 이용하여 풀었다. 그래프의 연결 요소 즉, 서로 연결되지 않은 그래프들의 수를 구하는 문제이다. 연결 요소의 수를 구하는 방법으로 방문하지 않은 노드를 만나면 1을 카운트하고 해당 노드의 탐색을 진행했다. 코드 #include #include using namespace std; int N, M; int visited[..

문제: www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제풀이 C++ STL queue에 있는 prioriy_queue를 이용하여 문제를 풀었다. prioriy_queue는 정렬을 할 때 알아서 힙 정렬을 제공해주기 때문에 prioriy_queue의 사용법만 안다면 매우 쉬운 문제였다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); ci..

문제: www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문제풀이 IOI가 연속되는 개수를 세서 N에 도달하면 정답 개수를 1개 카운트한다. ex) IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI 위와 같이 계속 IOI가 연속된다면 그 개수를 센다. 코드 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; ..

문제: www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제풀이 그리디 알고리즘을 이용하여 문제를 해결했다. pair 벡터에 회의의 시작시간과 끝 시간을 넣고 종료 시간을 기준으로 오름차순 정렬을 하고 회의 종료 시간이 가장 빠른 회의를 선택한다. 이 때 회의의 시작시간이 이 전 회의의 종료시간과 겹친다면 다음으로 종료시간이 빠른 회의를 선택하여 위의 과정을 반복한다. 코드 #include #include #include using namespace std; bool compare(pair p1, pair p2){ //종료시간을 기준으로 정렬 if(p1.second != p..