L.O.K

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 어려운 알고리즘이 필요한 문제는 아니었지만 적절한 풀이 발상이 쉽지 않은 문제였다. 곡갱이는 종류에 상관없이 광물을 5개까지만 캘 수 있고 한번 캐기 시작하면 교체할 수 없다. 곡갱이의 종류에 따라 피로도가 달라지므로 최소 피로도를 구하려면, 가장 성능 좋은 곡갱이(다이아)로 가장 피로도가 높은 광물집합( 광물 5개 이하로 구성된 )을 캐야 한다. 1) 곡갱이를 다이아-철-흙 순으로 곡갱이 큐에 넣는다. ( 성능순 ) 2) 나열된 광물을 앞에서부터 5개씩 끊어 광물집합 객체를 생성하고 우선순위 큐..

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 폭격미사일은 X 좌표 범위(start,end)를 가지고 요격미사일은 특정 x좌표에서 발사될 때, 최소한의 요격미사일 발사로 폭격미사일을 요격해야하는 문제이다. 주어진 폭격미사일 범위를 end좌표로 오름차순 정렬하는 것이 중요하다. 요격미사일은 폭격미사일이 끝(end)나는 지점에서 최소한 한 개가 발사되어야 하기 때문이다. 그러므로 폭격미사일 배열을 end를 기준으로 오름차순 정렬해야..

11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net ◎ 문제 풀이 산다 2) 판다 3) 아무것도 안한다. 3가지 경우가 있고 목표하는 n 날에 최대이익을 구하는 문제이니, 처음에는 DP를 발상하였다. 그러나 DP로 풀기에는 한계가 있었다. 주식을 하나 팔 수도, 두 개 팔 수도 있었다. DP로 이런 복잡한 경우의 수까지 고려할 수 없었다. 주식은 가장 쌀 때 사서 비쌀때 파는 것이다. 그러므로 그리디 알고리즘이 적합하다. 매일 주가를 기준으로 향후 가장 비싼 주가인 날에 팔면 된다. 주가를 내림차순으로..

1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net ◎ 문제풀이 1부터 N까지 공백없이 이어붙인 수열에서 임의로 몇 개의 수가 제거되었을 때, 제거된 수열만보고 N의 최솟값을 알아내는 문제이다. 수열의 좌측의 수부터 하나씩 그 수를 포함하는 수의 최솟값을 구하면된다. 134211 이 임의로 제거된 수열이라고 해보자. 가장 좌측인 1을 포함하는 수의 최솟값은 1이다. 그 다음 3을 포함하는 수의 최솟값은 3이다. 그 다음 5를 포함하는 수의 최솟값은 5이다. 그 다음 2를 포함하는 수의 최솟값은 2이다. 그 다음..

1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net ◎ 문제풀이 문제를 풀려면 우선순위큐 두 개를 사용해야 한다. 입력받은 주유소는 우선순위큐에 저장하고 거리를 기준으로 오름차순하여 정렬한다. 오름차순으로 정렬해야 현재 자동차 주유량을 기준으로 주유소에 차례로 접근이 가능하다. 현재 자동차 주유량이 10L라고 해보자. 10L로 접근가능한 주유소를 우선순위큐에서 하나씩 꺼낸다. 주유소의 주유량을 주유량 우선순위큐에 저장한다. 주유량 우선순위큐는 내림차순이다. 주유량 우선순위큐에..

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net ◎ 문제풀이 각 지점에서 트럭이 택배를 싣고 내릴 때, 최대 몇 개의 택배를 전달할 수 있는지 묻는 문제이다. 가장 최적의 상황을 발상하기 어려운 문제였다. 처음에는 시작점을 오름차순하고 그 다음 도착점을 오름차순하여 택배를 트럭에 싣는 방식을 생각했다. 그러나 문제가 있었다. 지점이 1 부터 5까지 있다고 해보자. 1을 시작으로 하고 5를 도착으로 하는 택배는 1부터 5까지 트럭이 이동하는 동안 공간을 차지하고 있게 된다. 이는 최적의 상황..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net ◎ 문제풀이 근처 빵집에 위치한 가스관(열)과 원웅이네 빵집의 가스관(열)을 연결하는 경로의 최대 개수를 구하는 문제이다. 중요한 조건은 세 가지가 있다. 1) 파이프라인 연결은 중간에 건물이 있으면 연결되지 못한다. 2) 한번 설치된 파이프라인 경로는 다른 경로와 겹치지 않는다. 3) 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 설치가 가능하다. 1)은 백트래킹 가자치기 조건이다. 2)는 한번 방문한 노드는 ..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net ◎ 문제풀이 카드 묶음을 비교하여 하나로 만들 때, 비교횟수의 최솟값을 구하는 문제이다. 비교횟수가 최소가 되려면 카드묶음이 큰 거를 가장 마지막에 비교해야 한다. 그리고 두 개의 카드묶음을 하나로 합치면 또 하나의 카드 묶음이 만들어진다. 비교횟수가 최소가 되려면 새로 생성된 카드묶음을 포함한 가장 개수가 적은 카드묶음 두 개를 합쳐야 한다. 다시말하여, 새로운 카드묶음이 추가될 때 마다 카드묶음 자료구조에서 매번 최솟값을 구해야 한다는 의미다...

1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net ◎ 문제풀이 문제마다 데드라인이 정해져 있을 때, 컵라면을 최대로 몇 개까지 받을 수 있는지를 구하는 문제이다. 이 문제는 그리디 풀이에 HeapQueue를 떠올리면 간단히 풀리는 문제이다. ( 나는 떠올리지 못했다.. ) 단위시간이 1씩 늘어가면 컵라면을 받을 수 있는 개수도 바뀐다. 시간의 변화에 따른 최적해를 구해야 하므로 그리디로 접근해야 한다. 단위시간 1을 하루로 생각해보자. 한 문제를 푸는데 하루가 걸린다. 데드라인이 2일이라면 이틀 안에 풀면 된다. 최적해..

1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net ◎ 문제풀이 일직선상에서 책을 놓을 때 최소 걸음을 구하는 문제이다. 어떤 경우가 최소가 될 수 있는지 정확히 따져야 한다. 최소 걸음으로 갈 수 있는 경우는 다음과 같다. 1) 좌우를 번걸아 이동하면 안된다. 좌측으로 갔다가 우측으로 이동하면 0을 거친다. 0을 거치면 어차피 또 다시 책을 들고 갈 수 있으니 최소가 아니게 된다. 자료구조를 좌우로 분리하는 것이 좋다. 2) 가장 멀리 떨어져 있는 책을 가장 마지막에 놓아야 한다. 마지막 조건을 보면 마지막에 책을 ..