출항사

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr numbers 배열이 주어진다. 우리가 구하고 싶은 값은 numbers[i]를 기준으로 [i+1 ... numbers.length] 사이에 있는 숫자중 가장 가까우면서 numbers[i]보다 큰 숫자이다. 제한이 100만이기 때문에 O(N), O(NlogN) 이내에 풀어야 할 것 같은데 logN은 이분탐색말고 떠오르지 않으니 그냥 O(N)으로 접근해보자. 뒤에 있는 숫자 중 하나를 채우는 것이기 때문에 딱봐도 뒤에서부터 무엇인가 하면 될것 같은 느낌이 든다. 그래서 뒤에서 부터 값을 채우도록 문제를 접근해보자..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저 나이브하게 문제를 접근해보자. 존재하는 곡괭이의 개수는 최대 15개이다. 그리고 광물의 개수는 50개이다. 곡괭이 무조건 5개의 광물을 캐야한다는 조건이 있다. 50개의 광물을 캐기 위해서는 10개의 곡괭이가 필요한 것을 알 수 있다. 즉, 최대 10개의 곡괭이만 사용하게 된다. 그러면 15개의 곡괭이 중 10개를 뽑는데 15C10의 시간복잡도가 소요된다. 그리고 뽑은 곡괭이를 최소값이 되도록 나열해야 하는데, 10!의 시간복잡도가 소요된다. 이 둘을 곱하면 절대 문제를 해결할 수 없다는 것을 알 수 있..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 귀찮았던 구현 문제이다. 주어진 조건대로 구현을 하면 되는데 주의할 부분이 하나 있다. 문제에서 요구하는 시뮬레이션 순서는 아래와 같다. 시간이 되면 새로운 과제를 시작한다. 새로운 과제를 수행할때, 기존에 수행하던 과제가 있으면 대기열로 해당 과제를 보낸다. 현재 진행중인 과제가 끝이 나면, 대기중인 과제를 이어서 수행한다. 이렇게 케이스를 나눠볼 수 있다. 사실 케이스를 더 쪼갤 수 있지만, 새로운 과제가 있다면 무조건 시작해야 하기 때문에, 조건문 순서를 잘 걸어두면 간소화할 수 있다. 대기열에 들어간 ..

간단한 그래프 탐색 문제이다. 문제를 해석해보면, 직관적으로 펭귄과 가장 가까운 빨간 블록 2개를 찾고, 이 2개의 블록을 찾기까지 만나는 깰 수 있는 블록들의 개수를 세면 된다. 이게 가능한 이유는 그래프가 트리로 주어지고, 빨간 블록들이 서로를 찾으려면 무조건 펭귄을 지나야 하기 때문이다. 따라서 BFS나 DFS를 돌려 각 칸에 도달하기 까지 거리를 구하고, 1 > N >> S >> P; for (int i=1; i> x >> y; adj[x].push_back(y); adj[y].push_back(x); } visited[P] = 0; dfs(P); priority_queue pq; for (int i=1; i

일단 다익스트라 응용 문제인 것은 간단하게? 눈치챌 수 있다. 문제를 해석해보면, 아줌마는 총 10개의 노드를 순차적으로 이동한다고 한다. 여기서 문제의 핵심은 무조건 이 순서대로 이동한다는 것이다. 문제에서 주어지는 '나'의 순서는 필요없다. 그냥 모든 노드를 이동할 수 있고, 야쿠르트 아줌마를 만날 수 있는 노드가 몇번인지?를 구해야 한다. 아줌마가 이동할 노드들이 주어진다. 이때 각 노드별로 다익스트라를 돌려보자. 어차피 10번만 돌리면 되기 때문에, 10번의 다익스트라로 아줌마가 이동할 경로의 모든 최솟값 경로를 구할 수 있게 된다. 이제 나를 기준으로 다익스트라를 돌려주자. 내가 모든 노드에 도달할 수 있는 최소 비용을 구했다면, 이제 아줌마의 경로를 따라가봐야 한다. 아줌마가 i, i+1, i..

우선순위 큐 두개로 해결할 수 있는 문제이다. recommend 명령어가 1인지, -1인지에 따라 큰 값부터, 작은 값부터 찾아야 하는 값이 달라진다. 그래서 최대 힙과 최소 힙을 함께 사용하면 된다는 것을 눈치챌 수 있다. 그리고 별도의 방문 배열을 만들어서 각 문제가 solved 된 적이 있는지 확인하기로 하자. 그러면 최대힙에 있는 문제가 해결되었을때, 최소힙에서 이를 판별할 수 있게 된다. 구현이 조금 귀찮았던 문제다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 200010 #define X first #define Y second using namespace std; typedef lo..

스택으로 해결할 수 있는 문제이다. 현재 건물의 높이를 기준으로, 왼 오른쪽을 전부 바라봤을때 볼 수 있는 건물의 개수를 세라고 한다. 앞에서 부터 값을 저장한 스택과 뒤에서 부터 값을 저장한 스택을 사용하면 각 칸별로 바라볼 수 있는 건물의 개수를 구할 수 있다. 그다음 구해야 하는 것은 가장 가까운 건물의 번호이다. 가까운 건물의 번호는 스택으로 볼 수 있는 건물을 셀때 약간의 조건문을 통해 갱신하면 된다는 것을 쉽게 알아챌 수 있다. 스택을 갱신할 때마다 건물과 거리를 갱신하자. 그리고 이 번호가 갱신되는 순간 건물의 번호를 갱신해주면 된다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 10..

투포인터로 해결한 문제이다. N개의 물건 가격이 주어진다. 이때 1, 2, 3개 중 하나를 선택해 총 무게를 K로 만들 수 있는지 묻고 있다. N의 제한이 5000이하이기 때문에 2개를 선택하는 경우까지는 확인할 수 있지만, 3개를 선택하는 것이 관건이다. 정확히 K를 맞춰야 하는 것에 집중해보자. 그리고 하나의 물건을 기준으로 잡자. 이 무게를 X라고 할때 우리는 2개의 물건을 더했을때 N-K가 나오는 조합이 있는지 확인해야 하고 2개의 합이 N-K인지 확인하기 위해 투 포인터를 사용한다면, O(N)에 N-K 값이 있는지 알 수 있다. 따라서 O(N^2)에 3개를 선택한 경우도 구할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #defi..