문제: www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제풀이 스택을 사용하여 i번째 탑의 높이보다 크고 다른 탑에 의해 가려지지 않은 탑들만 스택에 남겨야한다. (i번째 탑에 서서 왼쪽의 탑들을 보았을 때 보이는 탑들) 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; pair tower[N]; f..

문제: www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제풀이 C++ STL list iterator를 이용하여 문제를 풀었다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int T; cin>>T; list l; while(T--){ string str; cin>>str; list::iterator cursor = l...

문제: 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..