728x90 반응형 시간 복잡도10 [백준/Python] 11866 요세푸스 문제 0 문제: https://www.acmicpc.net/problem/11866 사용 알고리즘: 덱 입력첫째 줄에 N 과 K 가 빈 칸을 사이에 두고 순서대로 주어짐 (1 1 번부터 N 번까지 N 명의 사람이 원을 이루며 앉아있을 때, N 명의 사람이 모두 제거될 때까지 K 번째 사람을 제거해 나감.-> 앞 뒤로 추가/제거가 가능한 덱을 사용해서 원처럼 동작하도록 구현 입력이 7 3 인 경우,1 2 3 4 5 6 7 의 숫자를 가진 사람들이 원을 그리며 앉아 있을 때, 3 번째 사람을 계속해서 제거해 나가야 한다. - 1 을 제거하고 다시 뒤에 붙임 2 3 4 5 6 7 1 - 2를 제거하고 다시 뒤에 붙임3 4 5 6 7 1 2 - 3을 제거 (K = 3)4 5 6 7 1 2 for 문을 돌면서 K.. 2024. 8. 5. [백준/Python] 2346 풍선 터뜨리기 문제: https://www.acmicpc.net/problem/2346 사용 알고리즘: 덱 입력첫째 줄에 자연수 N (1 둘째 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어짐 (종이에 0은 적혀있지 않음) 구현 로직1. 가장 먼저 1번 풍선을 터트려서 종이에 적힌 숫자 만큼 이동2. 도착한 곳의 풍선을 터트려 종이에 적힌 숫자만큼 이동3. 풍선이 다 터질 때까지 2를 반복 아래 그림처럼 원형으로 놓인 풍선을 일자로 핀다고 생각하면 된다.나는 덱의 0번째 인덱스를 기준점으로 잡고 숫자를 돌리다가 이 자리에 온 숫자를 pop 할 것이다. 풍선 안에 적힌 종이에는 0을 제외하고 -N 이상 N 이하의 정수가 적혀있는데, 도는 방향이 다르기 때문에 음수와 양수일 경우를 나눠서 처리해야 한다... 2024. 8. 1. [백준/Python] 9012 괄호 문제: https://www.acmicpc.net/problem/9012 사용 알고리즘: 스택 입력테스트케이스 개수 T밑으로는 T 개의 테스트케이스가 주어지며, 테스트케이스의 괄호 문자열의 길이는 2 이상 50 이하 괄호의 짝을 맞추는 문제 -> 스택 대표 문제라고 생각하면 됨 주어진 괄호 문자열을 돌면서 1. '(' 인 경우 스택에 추가2. ')' 인 경우빈 스택일 경우 짝이 안 맞으므로 answer 에 'NO' 를 기록빈 스택이 아닐 경우 스택의 맨 위의 요소 pop주어진 괄호 문자열을 다 돌고 나왔는데, 빈 스택이 아닌 경우는 짝이 안 맞는 경우이므로 answer 에 'NO' 를 기록for _ in range(n): s = deque() PS = input().rstrip() .. 2024. 7. 30. [백준/Python] 18258 큐2 문제: https://www.acmicpc.net/problem/18258 사용 알고리즘: 큐 입력첫째 줄에 주어지는 명령의 수 N (1 둘째 줄부터 N 개의 줄에는 명령이 하나씩 주어짐. 주어지는 정수는 1 이상 100,000 이하이다. 명령은 총 6가지push X: 정수 X를 큐에 넣는 연산pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력size: 큐에 들어있는 정수의 개수를 출력empty: 큐가 비어있으면 1, 아니면 0을 출력front: 큐의 가장 앞에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력back: 큐의 가장 뒤에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 일단.. 2024. 7. 30. 이전 1 2 3 다음 728x90 반응형
