www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 아이디어: #우선순위큐 파이썬에서 우선순의 큐를 구현하는 방법 # 우선순위가 높은 큐가 먼저 나온다. import queue q = queue.PriorityQueue() q.put((10, "a")) q.put((5, "b")) q.put((15, "c")) q.qsize() # 3 q.get() # (5, 'b') heapq로 구현하는 방법도 있다. import heapq h = [] heapq.heappush..
분류 전체보기
www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 아이디어: #큐 큐를 이용해서 n까지의 수를 모두 넣은 후 앞에서부터 차례대로 제거하면서 제거한 수를 다시 큐에 집어넣는 형태로 반복한다. 파이썬에서 queue를 구현하는 방법 1. 리스트 - 비효율적임 2. Queue # 내장 함수 queue를 사용하여 구현 import queue q = queue.Queue() q.put("a") q.put("b") q.put("c") q.qsize() # 3 q.get() # 'a' q.qsize() # 2 근데 queue를 이용해서 문제를 풀었더니 시간초과가 나..
www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 아이디어: #스택 이것도 스택의 대표문제인 괄호문제. 오른쪽 괄호인 경우에는 push 하고, 왼쪽 괄호인 경우에는 pop해서 짝이 맞는 지 확인한다. 이때 스택에 남아 있는 괄호가 없다면 오른쪽 괄호가 더 많은 거니까 False이고, 문자열을 모두 돈 후에 스택에 괄호가 남아있다면 왼쪽 괄호가 더 많은 거니까 False이다. import sys while (True): st = sys.stdin...
www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 아이디어: #스택 스택의 대표 유형이라고 볼 수 있다. 주어진 문자열을 돌면서 피연산자일 경우에는 push, 연산자일 경우에는 스택에서 두 개를 pop해서 연산을 한 후 값을 다시 push한다. 문자열을 모두 돌면 스택에 딱 한 값이 남고 그 값을 pop하면 답을 구할 수 있다. 파이썬에서는 스택 자료구조를 따로 제공하지 않기 때문에 list를 사용하여 구현한다. push는 append로, pop은 ..
www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 아이디어: 이분탐색 이분탐색을 이용하여 푸면 된다. 하지만, 구현 과정에서 그냥 mid 값을 출력하니 틀렸다. 조금만 생각해보면 당연한 것이다. 조건에 맞을 경우에만 답을 업데이트해주고 그 답을 출력해야 한다. 그런데 또 파이썬으로 제출하면 시간초과가 떠서 pypy로 제출했는데, 질문을 보니 시간을 단축할 수 있는 방법을 생각해보라고 해서 이왕 정렬하는 거 배열의 끝에서 ..
www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 아이디어: #정렬 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 따라서 정렬 조건은 1. 최종점수 2. 풀이를 제출한 횟수 3. 마지막 제출 시간 이다. 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 한 문제에 대한 풀이를 여러번 제출할 수 있으며 그 중 최고 점수가 그 문제의 최종 점수이다. 입력..
www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 아이디어: 파이썬으로 풀면 아주 간단하게 풀 수 있다. 일단 중복을 제거하기 위해 set을 사용하고, 후에는 sorted()함수에 lambda를 사용하여 다중 조건을 걸어 정렬을 한다. 코드: #문자열, 정렬 import sys n = int(sys.stdin.readline()) arr = [] for _ in range(n): arr.append(sys.stdin.readline().rstrip(..
www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 아이디어: 정렬 B의 가장 큰 수에 A의 가장 작은 수를 곱하면 된다. A는 오름차순으로, B는 내림차순으로 정렬한 후 각각 곱한다. 5 1 1 1 6 0 2 7 8 3 1 이 예제에서 A를 오름차순으로 정렬하면 0 1 1 1 6, B를 내림차순으로 정렬하면 8 7 3 2 1 이므로 구하는 합은 0+7+3+2+6=18 이다. 코드: 파이썬에서 내림차순으로 정렬하는 방법, lambda를 쓰는 방법 잘 익혀..
www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 아이디어: 뭔가 일단 정렬을 해야 할 것 같다. 근데 이걸 투 포인터로 어떻게 풀 수 있을까? 모든 경우를 찾아본다면, 가능한 두 수를 모두 뽑고 그 합과 같은 숫자가 있는지 탐색할 수 있을 것이다. 탐색은 이분 탐색이 가능할 것 같다. 근데 이게 시간 안에 풀어질까..? 그래서 구글링함^^ 내 생각이 조금은 맞았다. 대신 반대로, arr에 있는 모든 수를 돌면서 합이 arr[i]가 되는 두 수가 있는지를 찾는다. 이때 투 포인터를 이용한..
www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 아이디어: G = 현재 몸무게^2 - 기억하던 몸무게^2 현재 몸무게와 기억하던 몸무게가 뭐든 될 수 있으니까..(이게 무슨..) 자연수의 제곱 중에서 투포인트를 사용해서 차가 G가 되는 경우를 구하자. 일단 가능한 몸무게의 배열을 만들고 (1~200000까지의 제곱) result, left, right 모두 0으로 초기화한다. result가 g보다 큰 경우 left++, 작은 경우 right++ import sys ..
