박트리

두 개의 네비게이션 문제 그래프가 주어지고 1번 회사에서 N번 집까지 가는동안 경보음을 최소로 듣는 경우를 구하는 것이다. 문제 풀이 먼저 출발지인 회사에서 집으로 가는 경로 들은 여러곳이 있을 것이다.dist[x] 를 x에서 부터 n까지 가는 최단거리라고 정의하자.그렇다면 현재 위치 u와 연결된 v들에 대해서 dist[v]+w(u,v) == dist[u] 라면 v는 u에서 가는 최단 경로이다.아니라면 v로 가면 경보음이 울리게 된다. 이와 같은 정리를 이용해서 아이폰과 안드로이드를 사용하였을 때 u->v의 경보음이 울리는지울리지 않는지 판별하면 된다.모든 위치 u와 그와 연결된 v에 대해서 위의 값을 구하고 새로운 그래프를 만든후 다시 한번 최단경로 알고리즘을 돌리면 된다. 약간 디테일한 구현 방법으로..

할인권 문제 그래프가 주어지고 a -> b 경로의 비용이 할인권 k보다 비싸다면 할인권을 사용할 수 있을 때q개의 여행 경로에 대해서 할인권 사용 횟수를 구하는 문제이다. 문제 풀이 올-페어 최단거리를 구하면 된다.다익스트라를 n번 돌리거나, 플로이드-워셜 알고리즘을 사용하면 된다.해당 a->b 최단거리가 k보다 크다면 할인권을 사용하면 된다. 소스 코드

부분배열 문제 주어진 배열에서 연속 합이 s가 넘는 부분배열중 길이가 최소인 부분배열의 길이를 구하는 문제이다. 문제 풀이 투포인터로 시작점과 끝점을 정하고 적절히 이동하면 해결가능하다. 현재 시작점 ~ 끝점까지의 연속 합이 s보다 작은 경우 끝점을 하나 늘리고, 아닌 경우 배열의 길이를 계산한 후에 시작점을 줄이면 된다. 소스 코드

그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..

수강신청 문제 n개의 강의가 있고 학점제한이 m일 때 최대로 수강할 수 있는 수강학점을 구하는 문제이다. 문제 풀이 동적계획법으로 \(dp[i][k] =\:i번\:째\:강의까지\:수강하고\:k학점\:들었을\:때\:최대\:수강학점\) 으로 정의하고 구현하면\(O(NM)\) 에 해결 가능하다. 슬라이딩 윈도우 기법으로 공간 복잡도를 줄일 수 있다. 소스 코드

새로운 방 문제 (1,1)에서 (n,n)으로 최단거리로 이동하고, 만나는 방의 모든 돈을 곱해서 6진수로 변환할 때 뒤에서 부터 연속된 0의 갯수의 최대값을 구하는 문제이다. 문제 풀이 최단 거리로 이동하므로, 아래 또는 오른쪽으로만 이동 가능하다. 따라서 동적계획법을 적용할 수 있고, 결국 (n,n) 방에 도착 하고 소인수 분해 하였을 때 min(2의 개수, 3의 개수) 의 최대값을 구하는 문제로 바뀐다. 한 방에 3은 최대 6개 들어 갈수 있고 (n,n) 에서 최대 6만개 까지 존재 할수 있으므로 \(O(N^2 * 60000)\) 으로 해결 가능하다.\( dp[i][j][k]=\: i\: 행\: j\: 열에서\: 현재\: 까지\: 모은\: 3이\: k\: 개\: 일\: 때\: 최대로\: 모을\: 수있..

김씨만 행복한 세상 문제 주어진 그래프로 이분그래프를 만들 수 있는가? 를 판별하는 문제이다. 문제 풀이 주어진 그래프를 입력 받고 임의의 정점에서 다른 정점으로 이동할 때마다 타입을 반전시켜준다. 모순이 발생하면 이분그래프를 만들수 없는 그래프이다. 소스 코드