알고리즘

(C++) 백준 2841번 - 외계인의 기타 연주

문제 링크 : https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 풀이 이전의 스택 문제들과 비슷하게 접근하여 풀었다. 기타의 줄이 6줄이므로 6개의 stack을 가지는 배열을 선언하였다. 아무 프렛도 안 누른 상태를 가정하여 0을 스택에 넣고 시작했는데, 이 덕분에 스택이 비어 오류가 발생하는 것을 걱정하지 않아도 된다. #include #include using namespace std; stack A[6..

(C++) 백준 2493번 - 탑

문제 링크 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 처음에 다음과 같이 풀어보았다. #include #include using namespace std; stack T, tmp, answer; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--){ int i; cin >> i; T.push(i); } while(1){ int num = T.s..

(C++) 백준 1406번 - 에디터

문제 링크 : https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 C++의 STL List 라이브러리를 사용하여 풀이하였다. 연결 리스트로 풀면 실버2 문제치곤 어렵지 않게 해결할 수 있다. 백준 5397번 키로그와 거의 동일한 문제여서 동일하게 풀이를 하면 된다. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; ci..

(C++) 백준 5397번 - 키로거

문제 링크 : https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 C++의 STL List 라이브러리를 사용하여 풀이하였다. 연결 리스트로 풀면 실버2 문제치곤 어렵지 않게 해결할 수 있다. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--){ list L; auto cur = L..

(Python) 백준 1966번 - 프린터 큐

문제 링크 : https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 큐와 이차 배열을 사용하여 문제 풀이를 진행했다. 중요도와 문서 번호를 동시에 큐에 담아서 진행하는 것이 풀이의 핵심이라고 볼 수 있겠다. 이차 배열이 아니라 딕셔너리를 사용하여서 풀이하는 것도 가능할거 같다. import sys from collections import deque for _ in range(int(sys.stdin.readline())): n, m = map(i..

(Python) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 저번에 풀이했던 1978번과 같은 방식인 에라토스테네스의 체로 풀이를 했다. 다만 2부터 (자기 자신 - 1)을 모두 나눠보면 시간 초과가 발생하여 어떻게 해야 하는지 고민하던 중, 2부터 √자기자신 까지만 나눠도 된다는 사실을 알게 되어 그렇게 풀이해 보니 제한 시간 내에 통과할 수 있었다. import sys import math n, m = map(int, sys.stdin.readline().split..

(Python) 백준 1874번 - 스택 수열

문제 링크 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 deque를 stack으로 사용하여, 입력으로 들어오는 수열을 만들기 위해 발생할 수 있는 모든 경우를 생각하며 하나씩 구현하였다. import sys from collections import deque n = int(sys.stdin.readline()) stack = deque() # 입력 ..

(Python) 백준 10866번 - 덱

문제 링크 : https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections imp..

(Python) 백준 10845번 - 큐

문제 링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Queue의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections imp..

(Python) 백준 10828번 - 스택

문제 링크 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Stack의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections im..