Kowal's Igloo

문제 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오. 예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자. 이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다. 입력 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 코드 입력된 숫자 배열에서 가장 큰 숫자까지의 소수 여부를 한 번에 구하고, 이후 소수인지 여부가 저장되어있는 is_prime 배열에서 결과를 하나씩 출력했다. def getPrime(n): is_prime = [True] * (n+1) # 1 ... n+1 is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): # i는 2부터 i의 제곱근까지 반복 if not is_prime..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 코드 # 유클리드 호제법: a와 b의 최대공약수는 a%b와 b의 최대공약수와 같다 def gcdIter(a, b): while(b): a %= b; a, b = b, a return a; a, b = map(int, input().split()) gcd = gcdIter(max(a, b), min(a, b)) lcm = int(a*b / gcd) # 최소공배수 = 두 수의 곱 /..

문제 문제가 길어서 요약해보겠다. 해시 함수는 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 입력으로 들어오는 문자열은 영문 소문자(a, b, ..., z)로만 구성되어있으며, 각 문자에는 1부터 26까지의 번호가 붙는다. 이때 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다. 수열의 값을 모두 더한 후 유한한 범위의 출력을 갖기 위해 M으로 나눠준다면, 해시 함수의 식은 다음과 같다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 해시 값이 같아져 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니 이를 개선해서, 수열의 각 항마다 고유한 계수를 부여하는 방법이 있다. 이를 수식으로 표현하면 ..

문제 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. 입력 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자..

🧙 채용 매칭 플랫폼: 기업 사용자가 "멀티플레이어 전략 게임을 개발할 서버 개발자" 등의 프로젝트 개요를 입력하면 서비스에 올라와 있는 사용자들의 이력서와 비교해 가장 유사도가 높은 순서대로 추천한다. 1. 추천 시스템이란? 1.1 데이터의 종류 1.2 유사도 1.3 유사도 측정 방식 1.4 추천 시스템의 종류 1.5 추천 시스템의 한계 2. 우리 서비스에 적용 2.1 Step 1. 키워드 추출 2.2 Step 2. 단어 벡터화 2.3 Step 3. 벡터 간 코사인 유사도 계산 2.4 전체 코드 2.5 실행 결과 2.6 개선점 3 참고 자료 추천 시스템이란? 사용자의 정보 데이터를 분석하여 개인의 취향에 맞는 아이템을 추천하는 알고리즘이다. 예를 들어, 사용자는 상품에 좋아요를 남기거나, 상품을 구매하..

문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "le..

문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 입력 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 방안 처음 이 문제를 보고... 2750번 수 정렬하기 1처럼 쉬울 줄 알고 냅다 제출해버렸다. 하지만 시간 초과가 떴는데..!! 그 이유는 입력 조건에 있다. 수 정렬하기 1번의 정렬해야 할 수 N 값의 범위는 1000보다 작거나 같은 정수였는데, 이 문제에서는 1,000,000보다 작거나 같은 정수이기 때문에, 연산량이 늘어나 시..