우선순위 큐 ADT 항목(키, 원소)들을 저장 우선순위 큐 ADT 메서드 주요 메서드 insertItem(k, e): 키 k인 원소 e를 큐에 삽입 element removeMin(): 큐로부터 최소 키를 가진 원소를 삭제하여 반환 일반 메서드 integer size(): 큐의 항목 수를 반환 boolean isEmpty(): 큐가 비어 있는지 여부를 반환 접근 메서드 element minElement(): 큐에서 최소 키를 가진 원소를 반환 element minkey(): 큐에서 최소 키를 반환 예외 emptyQueueException(): 비어 있는 큐에 대해 삭제나 원소 접근을 시도할 경우 발령 fullQueueException(): 만원 큐에 대해 삽입을 시도할 경우 발령 우선순위 큐를 이용한 정..
Dictionary 인덱스를 숫자가 아닌 문자열, 튜플을 사용하려 할 때 빠른 접근/탐색이 필요할 때 집계가 필요할 때 (원소의 개수를 세는 문제) Dictionary와 list의 시간 복잡도 차이 Operation Dictionary List Get Item O(1) O(1) Insert Item O(1) O(1) ~ O(N) Update Item O(1) O(1) Delete Item O(1) O(1) ~ O(N) Search Item O(1) O(N) 원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용 Dictionary 생성 # 빈딕셔너리 생성 dict1 = {} # {} dict2 = dict() # {} Dictionary 원소 가져오기 # [] 기호 사용해 원소 가져오기 dict =..
문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 number k return "1924" 2 "94" "1231..
input() vs sys.stdin.readline() input() 매개변수로 prompt message를 받음 (입력을 받기 전 prompt message를 출력) 입력받은 값의 개행 문자 삭제시키고 반환 sys.stdin.readline() 한 줄 단위로 입력받음 (개행 문자 포함) 개행 문자 "\n"를 같이 입력받음 개행 문자에 대한 문자열 처리 필요 int()로 형변환을 해준다면 개행 문자는 사라지고 정수 형태만 남음 strip() 문자열 맨 앞과 맨 끝의 공백 문자 제거 sys.stdin.readlin().strip() 으로 사용 if) 입력 한 줄이 "011294/n" 로 주어질 때 (공백으로 분리되지 않은 정수) 문자열 끝의 공백 문자를 제거하기 위해 strip 사용 import sys ..
문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 ..
문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올..
문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109..
문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000) 출력 첫째 줄에 백..
문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.) 예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자. 일단, 지금 이..
1. 집합 자료형의 특징 중복을 허용하지 않는다. 순서가 없다(Unordered) 주로 중복을 제거하기 위한 필터 혹은 어떤 값이 포함되어 있는지 여부를 확인하는 용도로 쓰인다. 2. 집합 자료형 초기화 비어 있는 집합 S = set() 원소가 있는 집합 S = {1, 2, 3, 4} 리스트를 이용한 초기화 S = set([1, 2, 3]) 문자열을 이용한 초기화 S = set("Hello")#{'e', 'H', 'l', 'o'} 3. 교집합, 합집합, 차집합 교집합 s1 & s2 or s1.intersection(s2) 합집합 s1 | s2 or s1.union(s2) 차집합 s1 - s2 or s1.difference(s2) 4. 집합 자료형 관련 함수 값 1개 추가하기(add) s.add(x)# 이..
