알고리즘/구현(24)
-
[백준/C++] 1021번 회전하는 큐
문제: www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제풀이 덱을 순차 탐색하여 뽑아야 하는 숫자의 인덱스를 찾은 후 front에서의 거리와 back에서의 거리를 비교하여 더 적은 쪽으로 덱을 회전시킨다. 코드 #include #include using namespace std; void funcL(deque& d, int num){ while(d.front() != num){ d.push_back(d.front()); d.pop_front(); } ..
2021.03.21 -
[백준/C++] 2493번 탑
문제: 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..
2021.03.20 -
[백준/C++] 5397번 키로거
문제: 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...
2021.03.19 -
[백준/C++] 1927번 최소 힙
문제: 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..
2021.03.11 -
[백준/C++] 18870번 좌표 압축
문제: 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 벡터를 선언해 {좌표, 순서} 순으로 저장하고 좌표를 기준으로 오름차순 정렬했다. 이후 벡터를 탐색해 좌표 크기 순서대로 정답 벡터에 압축한 ..
2021.02.26 -
[백준/C++] 11279번 최대 힙
문제: 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..
2021.02.25