본문 바로가기

Algorithm231

[백준] 1966번 프린터 큐 사용 언어 - Python3 1966번: 프린터 큐 (실버3, 큐) 문제 ★큐 문제★ 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 정답 k-1명을 popleft() 하면서 바로 append해주는 deque([]) 문제 (코드 풀이) 1. 변수 선언 n 문서의 개수 / n 문서에서 m이 있는 인덱스 찾기! 가장 중요도가 높은, 큰 숫자를 best에 입력한다. q의 가장 왼쪽에 있는 숫자를 pop하고 front에 입력한다. 2. 맨 왼쪽의 숫자(front) 와 가장 큰 숫자(best)를 비교한다. m앞에 있는 숫.. 2023. 1. 22.
[백준] 11866번 요세푸스 문제0 사용 언어 - Python3 11866번: 요세푸스 문제 0 (실버5, 큐) 문제 ★큐 문제★ 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 정답 k-1명을 popleft() 하면서 바로 append해주는 deque([]) 문제 (코드 풀이) popleft()를 k번째 전까지 총 k-1번 진행한다. popleft() 된걸 바로 append하면서 뒤에 순차적으로 추가해준다. 마지막 k번째도 popleft()로 삭제하면서 그 값을 정답에 append한다. 마지막까지 한 원소만 남았을 때까지 while문을 진행한다. 마지막 한 원소만 제외하고 answer를 출력한다. answer의 마지막 원소는 따.. 2023. 1. 22.
[백준] 2164번 카드2 사용 언어 - Python3 2164번: 큐 2 (실버4, 큐) 문제 ★큐 문제★ 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 정답 deque([]) 문제 (코드 풀이) 1. 시간제한 & queue.popleft() 파이썬 라이브러리 중 collections의 deque로 q를 구현하기 import sys from collection import deque n = int(sys.stdin.readline()) q = deque([]) pop 명령어가 입력되었을 때, 큐에서 가장 앞(왼쪽)에 있는 정수를 빼.. 2023. 1. 22.
[백준] 18258번 큐 2 사용 언어 - Python3 18258번: 큐 2 (실버4, 큐) 문제 ★큐 문제★ 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정답 deque([]) 문제 (코드 풀이) 1. 시간제한 import sys n = int(sys.stdin.readline()) from collection import deque deque로 queue를 구현한다. queue = deque([]) 2. queue.popleft() pop 명령어가 입력되었을 때, 큐에서 가장 앞(왼쪽)에 있는 정수를 빼고.. 2023. 1. 21.
[백준] 1300번 K번째 수 사용 언어 - Python3 1300번: K번째 수 (골드2, 이분 탐색) 문제 ★이분 탐색 문제★ 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 정답 i*j 배열의 규칙을 알아내는 이분탐색 문제!! 1~k 범위를 줄여가며 검색한다. (코드 풀이) 1. 변수 선언 n 배열의 크기 k b의 인덱스 2. 이분 탐색 정의 몇 번째인지 인덱스를 구해야하므로 k의 범위를 이분 탐색한다. 배열은 항상 1*1로 시작하기 때문에, start =1로 한다. end = k까지만 진행해서 더이상의.. 2023. 1. 21.
[백준] 2110번 공유기 설치 사용 언어 - PyPy3 2110번: 공유기 설치 (골드4, 이분 탐색) 문제 ★이분 탐색 문제★ 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net python3으로는 시간 초과로 오답이지만, pypy3으로는 정답! 이분탐색은 while문으로 돌아가서 python보다 빠른 pypy3으로 했을 때만 정답이 나올 수 있다. 정답 집 좌표값의 차이를 start/end/mid 값을 지정하는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 n 집의 개수 c 공유기의 .. 2023. 1. 21.
[백준] 2805번 나무 자르기 사용 언어 - Python3 2805번: 나무 자르기 (실버2, 이분 탐색) 문제 ★이분 탐색 문제★ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 나무의 수 n개 나무의 길이 m개 tree는 정렬된 상태로 입력받기 2. 이분 탐색 정의 높이가 1 이상, max(tree) 이하 여야 자를 수 있기 때문에, 시작점은 1 , 끝점은 max(tree)로 선언한.. 2023. 1. 21.
[백준] 10816번 숫자 카드 2 사용 언어 - Python3 10816번: 숫자 카드 2 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 리스트 원소별 개수 구하기 mycard를 sorted 정렬하여 입력받는다. 정렬한 내카드를 한개씩 확인하면서 개수를 센다. count = {} 딕셔너리를 만들어서 여러개일 경우 중복 개수를 세준다. list_1 = [1, .. 2023. 1. 21.
[백준] 1920번 수 찾기 사용 언어 - Python3 1920번: 수 찾기 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 0. 이분 탐색 전 정렬하기 이분 탐색을 하기 위해선 탐색 기준이 정렬되어 있어야한다. a를 정렬한 후 arr과 비교해야 a의 탐색 범위를 줄이는 의미가 있기 때문이다. 1. 시작/끝/중간 값 선언 n 범위 안에서 ar.. 2023. 1. 21.
[백준] 1874번 스택 수열 사용 언어 - Python3 1874번: 스택 수열 (실버2, 스택) 문제 ★스택 문제★ 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 정답 스택 문제 !! (코드 풀이) 1. stack 쌓기 cur 변수를 이용해서 입력값인 num과 같아질때까지 1씩 증가시키며 빈 리스트 stack에 append해준다. cur == num 인 경우, stack의 마지막 원소인 stack[-1]은 num과 같아질 것 이고, 이 때 pop을 진행.. 2023. 1. 20.

티스토리툴바