출항사

배열로 높이가 주어질때, 물을 채운다고 생각해보자. 결국 물을 넘칠때까지 따르면 정답을 구할 수 있다. 각 칸을 기준으로 최대 높이 몇까지 채워질 수 있을까? i에 물을 최대한 채울때, 왼쪽과 오른쪽을 전부 살펴보자. 이때 왼쪽에서 제일 높은 높이와 오른쪽에서 가장 높은 높이가 물을 채울 수 있는 기준이 된다는 것을 알 수 있다. 그리고 이 두 값중 작은 값까지 물을 채울 수 있으므로, 이 높이에 대해 O(2N)으로 전처리를 수행하면 간단하게 구할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 100010 #define X first #define Y second using namespa..

투포인터로 해결한 문제이다. 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..

간단한 그래프 문제이다. 1번 노드를 기준으로 리프 노드까지 탐색하고, 이때 지나갈 수 없는 노드의 번호가 주어진다. 이때 리프 노드까지 정상적으로 탐색할 수 있는가?를 묻고 있다. 1번 노드를 기준으로 BFS or DFS를 돌리고, 리프 노드들을 확인해 하나라도 도달한 케이스가 있는지 확인하면 모든 조건을 만족할 수 있다. 현재 그래프가 유향 그래프로 주어지므로, 리프 노드는 간선의 개수가 0인 노드들이 될 것이다. 이 노드들을 모두 확인했을 때 도달한 적이 있다면 yes를, 하나라도 도달할 수 없다면 Yes를 출력하자. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #define NUM 100010 #define X..

팀의 초기 순위가 주어진다. 여기서 M개의 팀 쌍의 순위가 바뀌었다는 정보가 주어졌을 때, 가능한 경우인지 가능하다면 최종 순위는 몇 위인지 찾아야 한다. 그리고 가능하더라도 순위의 경우의 수가 1이 아니면?를 출력해야 한다. 순서가 정해져 있고, 이 순서를 기반으로 탐색을 진행해야 하기에 위상정렬을 떠올려볼 수 있다. 각 인덱스를 기준으로 자신보다 높은 순위가 몇개 남았는지를 세주자. M개의 정보가 들어온다. 이때 x, y중 초기 순위가 더 높은 값이 있고 작은 값이 있다. 이 둘을 바꾼다는 것은 이 우위가 바뀐다는 것이고, 간선의 방향을 뒤집어 줘야 한다. 그리고 나보다 높은 순위가 몇 개 남았는지 세는 값도 업데이트를 해줘야 한다. 자 이제 새롭게 만든 그래프를 기반으로 위상정렬을 돌리자. 이때 최..

간단한 탑다운 DP 문제이다. Ai = A[i/P] + A[i/Q]일때, An을 구해야 한다. N이 최대 1e12까지 가능하다. P와 Q는 최소 2부터 시작이다. 따라서 트리 구조로 탐색을 진행한다고 생각해봤을때, 트리의 깊이가 급격히 낮아지는 것을 알 수 있다. 중복되지 않는다고 해도 최대 log2 1e12안에 모든 탐색을 할 수 있다. 이는 깊이 38짜리 트리이다. 방문을 표시하기 위한 배열을 만들 수 없으니, map을 활용하기로 하자. 이제 배열대신 map에 값을 사용해서 재귀 탐색을 수행할 수 있다.이미 구했던 값을 다시 계산할 필요가 없으므로 메모이제이션 기법을 함께 활용하면 아주 간단히 풀린다. #include #define MINF 0x7f7f7f7f #define INF 2000000000..

N개의 u, v가 주어진다. 구하고 싶은 값은 K인데 i uj, vi < vj를 만족하는 K를 구해야 한다. K를 기준으로 생각해보자. K의 왼쪽과 오른쪽을 기준으로 가장 큰값과 가장 작은 값들만 전처리 해놓는다면, O(1)에 K가 조건을 만족하는지 알 수 있을 것이다. 왜냐면 결국 왼쪽에서 가장 큰값이 오른쪽에서 가장 작은값보다 클때 무조건 정답이 될 수 있기 때문이다. 그래서 O(N) 탐색 두번을 통해 왼쪽, 오른쪽을 기준으로 최소 최대값을 전처리하고, 전처리한 값을 기준으로 K를 찾으면 된다. 시간복잡도는 O(N)이 소요된다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #d..

문제를 해석하니 Set + 오프라인 쿼리 + 유니온 파인드 세 가지 기법을 활용하면 무조건 정답을 구할 수 있다는 풀이가 나왔다. 우선 모든 간선을 끊어주자. 그리고 쿼리를 뒤에서부터 수행하면서 노드를 하나씩 연결해 주자. 이때 부모 노드를 찾아줘야 하는데, 부모 노드에서 K개의 색깔을 얻을 수 있다면 해당 집합에 속한 모든 노드는 K개의 색을 얻을 수 있다. 부모 노드를 찾기 위해서는 유니온 파인드 알고리즘을 사용하면 된다. 그리고 색을 중복되지 않게 세줘야 하기 때문에 set으로 관리해 주자. 하지만, 여전히 문제가 있다. 자식 노드와 부모 노드가 merge 될 때, 자식 노드에 들어있는 색을 부모로 모두 옮겨야 하는데, 이 작업을 수행하는 시간 복잡도는 O(NlogN)이고, 최대 N번 수행되므로 최..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N개의 몸무게가 주어지고, 시소가 주어진다. 시소에는 2, 3, 4 칸 중 하나에 앉을 수 있다. 이때 균형을 맞출 수 있도록 앉는 경우의 수를 구해야 한다. N은 10만 이하이므로 O(N^2)에는 안풀린다. 우리가 궁금한 것은 개수다. 그러니 각 몸무게별로 인원 수를 map에 저장하자. 그리고 이 key 값들을 이용해서 짝의 개수를 세면 된다. 앉을 수 있는 자리가 2, 3, 4이므로 2중 for문을 돌려주자. 현재 몸무게를 w라고 할때, 2, 3, 4 모두에 앉혀봐야 한다. 그리고 이때 반대편에 앉을 수 ..