![]()
문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다. 놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M..
![]()
🔎문제 해석 N의 크기가 최대 200,000이므로, O(N^2)인 알고리즘은 사용하면 안 된다. 따라서 모든 수열의 경우의 수를 탐색해야 하는 이 문제는 투 포인터 알고리즘을 사용해서 O(N) 알고리즘으로 풀어야 합니다. 우선 다른 투 포인터 알고리즘 문제와 동일하게 start, end를 사용합니다. 우선 start와 end를 0으로 초기화해줍니다. 그다음 숫자가 해당 부분수열에서 몇 번 포함되었는지를 기록하는 배열도 필요합니다. N의 최대크기는 200,000이고, N의 최댓값은 100,000이므로 배열의 최대 크기는 100,001이 될 것입니다. V [100001]; end가 n이 되기 전까지 해당 과정을 반복합니다. end가 가리키는 원소가 등장하는 횟수를 비교해 줍니다. k개 이하라면, 등장하는 횟..
![]()
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 설명 곡괭이의 종류는 3개이고, 광물의 종류는 3개입니다. 곡괭이 하나로 광물을 5개 캘 수 있고, 5개를 연속으로 캐며, 5개를 캐면 다시는 사용하지 못합니다. 곡괭이로 광물을 캘 때, 광물에 따라 피로도가 다릅니다. 다이아 곡괭이 -> 모두 피로도가 1 철 곡괭이 -> 다이아 = 5, 나머지 =1 돌 곡괭이 -> 다이아 = 25, 철 = 5, 돌 = 1 종료조건은 모든 곡괭이를 ..
![]()
문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언..
![]()
문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는..
![]()
문제 우주비행이 꿈이었던 진우는 음식점 '매일매일 싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. [예시] 진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다. 1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두 번 연속으로 움직일 수 없다. 진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느 위치든 착륙하는 것이다. 최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡문제 요점 입차시간과 출차시간을 비교해서 계속해서 누적 주차시간을 더해줘서 결과적으로는 차량별로 주차요금을 계산하는 문제입니다. 여기서 중요한 점은 바로 차량번호를 오름차순으로 정렬해서 주차요금을 계산해줘야 합니다. 🔎문제 풀이 우선 차량은 입차와 출차. 두 가지 경우의 수가 있습니다. A가 입차를 했을 경우, 다시 A가 들어왔다면 출차인 경우입니다. A가 입차를 했는데, 만약 A가 다..
![]()
문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🔎문제 해석 해당 칸에서 숫자를 넣고, 가로줄, 세로줄, 3*3 사각형 범위 검사를 해서 통과하면 다음 단계를 진행하는 문제이다. 만약 막혔다면 이전단계에서 다른 숫자를 선택하는 백트래킹 알고리즘을 사용하면 된다. 해당 좌표에서 포함되는 사각형의 범위는 어떻게 구하면 될까? 만약 x, y 좌표가 0,0이라면 사각형은 첫 번째 범위일 것이다. 가로 범위에서 3개의 구분이 있고, 세로 범위에서 3개의 구분이 있다. 따라서 (x좌표 /3 , y좌표/3)이 해당 ..
