와드의 블로그

문제N개의 아파트가 일렬로 쭉 늘어서 있습니다. 일부 아파트 옥상에는 4G 기지국이 설치되어 있습니다. 기지국이 설치된 아파트를 기준으로 전파를 양방향으로 W만큼 전달할 수 있습니다. 모든 아파트에 전파를 전달하기 위해 5G 기지국을 추가로 설치하려고 할 때, 추가로 설치해야 하는 기지국 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다.입력: 아파트의 개수 n (1 ≤ n ≤ 200,000,000), 현재 기지국이 설치된 아파트 번호 배열 stations (크기 10,000 이하), 전파 도달 거리 w (1 ≤ w ≤ 10,000)출력: 추가로 설치해야 하는 기지국의 최소 개수링크: https://school.programmers.co.kr/learn/courses/30/lessons/12979풀이..

문제A팀과 B팀이 자연수가 적힌 카드를 내며 게임을 합니다. 규칙은 각 팀의 카드를 한 장씩 내어 숫자를 비교하고, 숫자가 더 큰 쪽이 1점을 얻는 방식입니다. (숫자가 같거나 작으면 점수를 얻지 못합니다.) A팀이 낼 카드의 순서가 미리 주어졌을 때, B팀의 카드 배열을 적절히 재배치하여 B팀이 얻을 수 있는 최대 승점을 구하는 프로그램을 작성하는 문제입니다.입력: A팀의 카드 배열 A, B팀의 카드 배열 B (각 배열의 길이는 1 이상 100,000 이하, 원소는 1,000,000,000 이하의 자연수)출력: B팀이 얻을 수 있는 최대 승점링크: https://school.programmers.co.kr/learn/courses/30/lessons/12987풀이: 정렬과 탐욕법(Greedy)을 활용한..

문제자연수 n개로 이루어진 집합 중에 다음 두 조건을 만족하는 집합을 '최고의 집합'이라고 합니다.각 원소의 합이 S가 되는 수의 집합위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합집합의 원소의 개수 n과 모든 원소들의 합 s가 주어질 때, 최고의 집합을 오름차순으로 정렬하여 반환하는 프로그램을 작성하는 문제입니다. 만약 최고의 집합이 존재하지 않는다면 크기가 1인 배열에 -1을 담아 반환해야 합니다.입력: 자연수의 개수 n (1 ≤ n ≤ 10,000), 모든 원소들의 합 s (1 ≤ s ≤ 100,000,000)출력: 조건을 만족하는 최고의 집합을 오름차순 정렬된 1차원 배열로 반환링크: https://school.programmers.co.kr/learn/courses/30/lessons/1..

문제카카오톡 오픈채팅방에서는 누군가 들어오거나 나갈 때 관리자에게 메시지가 보입니다. 채팅방에 들어온 유저는 닉네임을 변경할 수 있으며, 닉네임을 변경할 경우 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 새로운 닉네임으로 변경되어야 합니다. 유저의 아이디(uid)와 닉네임의 변경 기록이 주어질 때, 모든 기록이 처리된 후 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 반환하는 문제입니다.입력: 채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record (길이 1 이상 100,000 이하)출력: 모든 기록이 처리된 후의 최종 메시지 배열링크: https://school.programmers.co.kr/learn/courses/30/lessons/428..

문제파일명을 주어진 기준에 따라 정렬하는 프로그램을 작성하는 문제입니다. 파일명은 영문자, 숫자, 공백, 마침표, 빼기 부호로만 이루어져 있으며 크게 세 부분(HEAD, NUMBER, TAIL)으로 나뉩니다.HEAD: 숫자가 아닌 문자로 이루어져 있으며, 최소 한 글자 이상입니다.NUMBER: 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있습니다. (0~99999)TAIL: NUMBER 이후의 나머지 모든 부분입니다. (비어있을 수 있습니다.)정렬 기준은 다음과 같습니다.HEAD 기준 사전순 정렬: 대소문자를 구분하지 않습니다. (예: muzi == MUZI)NUMBER 기준 오름차순 정렬: HEAD가 같을 경우, 숫자 값(정수)을 기준으로 오름차순 정렬합니다. (예: 012 == 12)입..

문제주차장의 요금표와 차량이 들어오고(IN) 나간(OUT) 기록이 주어집니다. 차량별로 누적 주차 시간을 계산하여, 누적 주차 시간이 기본 시간을 초과하면 초과한 시간에 대해 단위 시간마다 단위 요금을 청구합니다. (단, 출차 기록이 없다면 23:59에 출차한 것으로 간주합니다.) 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아 반환하는 프로그램을 작성하는 문제입니다.입력: 주차 요금표를 나타내는 정수 배열 fees (기본 시간, 기본 요금, 단위 시간, 단위 요금), 자동차의 입출차 내역 records출력: 차량 번호가 작은 자동차부터 주차 요금을 차례대로 담은 정수 배열링크: https://school.programmers.co.kr/learn/courses/30/lesso..

문제자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같이 3가지입니다.x에 n을 더합니다.x에 2를 곱합니다.x에 3을 곱합니다.자연수 x, y, n이 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하는 문제입니다. 만약 x를 y로 만들 수 없다면 -1을 반환해야 합니다.입력: 시작 숫자 x, 목표 숫자 y (1 ≤ x ≤ y ≤ 1,000,000), 더할 숫자 n (1 ≤ n 출력: 변환에 필요한 최소 연산 횟수 (변환 불가 시 -1)링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538풀이: 방문 배열과 BFS를 활용한 최단 거리 탐색주어진 연산을 간선으로 생각하고, 시작 숫자..

문제영재는 1번부터 n번까지 번호가 증가하는 순서대로 메인 컨베이어 벨트에서 전달되는 택배상자를 트럭에 실어야 합니다. 단, 택배 기사님이 미리 알려준 순서(order)에 맞게 실어야 합니다. 순서가 맞지 않는 상자는 보조 컨베이어 벨트에 임시로 보관할 수 있습니다. 보조 컨베이어 벨트는 맨 앞의 상자만 뺄 수 있는 구조(LIFO, 스택)입니다. 보조 컨베이어 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못한다면 작업을 중단합니다. 이때 영재가 트럭에 실을 수 있는 상자의 최대 개수를 구하는 문제입니다.입력: 택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order (길이 1 이상 1,000,000 이하)출력: 영재가 트럭에 실을 수 있는 택배상자의 개수를 반환합니다.링크: https:/..

문제카카오 매칭 팀은 메시지 전송 효율을 높이기 위해 LZW(Lempel–Ziv–Welch) 압축 알고리즘을 구현하려고 합니다. LZW 알고리즘은 다음 과정을 거칩니다.길이가 1인 모든 단어를 포함하도록 사전을 초기화합니다.사전에서 현재 입력과 일치하는 가장 긴 문자열 s를 찾습니다.s에 해당하는 사전의 색인 번호를 출력하고, 입력에서 s를 제거합니다.입력에서 처리되지 않은 다음 글자가 남아있다면(c), s+c에 해당하는 단어를 사전에 등록합니다.단계 2로 돌아갑니다.영문 대문자로만 이뤄진 문자열이 주어질 때, LZW 압축을 거친 후의 색인 번호 배열을 출력하는 프로그램을 작성하는 문제입니다.입력: 영문 대문자로만 이뤄진 문자열 msg (길이 1 이상 1,000 이하)출력: 주어진 문자열을 압축한 후의 ..

문제회사원 Demi는 N시간 동안 야근 피로도를 최소화하도록 일하려고 합니다. 야근 피로도는 남은 일의 작업량을 제곱하여 더한 값입니다. 1시간 동안 작업량 1을 처리할 수 있을 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 배열이 주어지면 야근 피로도의 최솟값을 구하는 프로그램을 작성하는 문제입니다.입력: 퇴근까지 남은 시간 n (1,000,000 이하), 각 일에 대한 작업량 배열 works (길이 20,000 이하, 원소 50,000 이하)출력: 야근 피로도를 최소화한 값(제곱의 합)을 반환합니다. 남은 작업량이 없다면 0을 반환합니다.링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927풀이: 우선순위 큐(Max Heap)를 ..