룰루랄라 알고리즘

마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기 무조건 마지막 계단 n을 밟았다고 쳤을 때 나올 수 있는 방식은 마지막 계단 전에 밟은 계단이 n-1 일 때, n-2 일 때 둘로 나뉜다 dp[i] : i번째 계단을 밟았을때 까지의 최댓값 dp[i-2] + score[i] : i번째 계단을 밟기 전에 i-2계단을 밟았을 때 dp[i-3] + score[i] + score[i-1] : i번째 계단을 밟기 전에 i-1계단을 밟았을 때 3계단을 연속으로 밟을 수 없으므로 i-2번째 계단을 밟았을 땐 i번째 점수 score[i]에 dp[i-2]를 더해 주고, i-1번째 계단을 밟았을 때는 score[i], score[i-1]에 dp[i-1-2]인 dp[i-3]을 더해 준다.

연속해서 뽑지 못하는 수열에서 최댓값 찾기 dp[i] : i번째 까지 마실 수 있는 포도주의 최댓값 dp[i-2] : i-2번째의 포도주를 마지막으로 마셨을 때 dp[i-3]+wei[i-1] : i-3번째의 포도주를 마지막으로 마셨을 때 dp[i-4]+wei[i-1] : i-4번쨰의 포도주를 마지막으로 마셨을 때 3잔을 연속해서 마시지 못하므로 dp[i-2]를 제외한 dp[i-3]과 dp[i-4]는 wei[i-1]를 더해준다

-1 : 아직 한 번도 탐색하지 않은 좌표 0 : 목표 지점까지 경로가 없는 좌표 그리고 목표 지점까지 갈 수 있는 좌표라면, 방문한 횟수에 따라 수가 올라갈 것이다. 1. dp 테이블을 -1로 초기화 한 후 dfs함수를 돌려 만약 x,y가 M-1,N-1 즉 좌표의 도착점 까지 도달한다면 1을 리턴하여 더해준다. 2. x,y의 좌표가 -1이 아니라면 방문 한 적이 있는 좌표므로 그 값을 리턴하여 더해준다. 3. 일단 좌표를 0으로 초기화 해서 4방향 dfs를 수행하여도 갈 수 있는 곳이 없다면 0을 리턴 4. 경로가 있다면 정상적으로 dfs를 수행. 5. 출발지가 결국 경로의 수가 됨 dp테이블 [3, 2, 2, 2, 1] [1, -1, -1, 1, 1] [1, -1, -1, 1, -1] [1, 1, 1..

정점의 개수 V, 간선의 개수 E, 목적지 후보의 개수 W 출발지 s, 정점 g와 h 사이를 지나감 목적지 후보 stack[] 1. 양방향 노선인 간선의 정보 저장 2. 다익스트라 알고리즘을 이용하여 시작점이 s,g,t인 distance를 각각 distart, dig, dih에 저장 **함수에서 리스트 자체를 리턴하여 저장 할 수 있다!! **리스트를 리턴하지 않고 값을 하나하나 리턴한다면 수많은 다익스트라를 수행 해야 해서 시간초과에 걸릴 수 밖에 없음 3. 목적지 후보까지의 최단 경로는 s->g->h->목적지 후보, s->h->g->목적지 후보 두 가지이므로 목적지와 경로가 같다면 result에 저장 4. 오름차순 정렬하여 출력

정점의 개수 V, 간선의 개수 E 반드시 거쳐야 하는 정점 n1,n2 1. 양방향이므로 graph[u].append([w,v]), graph[v].append([w,u]) 2. 다익스트라 알고리즘 수행 3. n1과 n2를 반드시 거쳐야 하므로 u->n1->n2->v, u->n2->n1->v 두 가지 경로가 있음 4. 결과에 두 가지 경로중 작은 값을 저장

정점의 개수 V, 간선의 개수 E 1. distance 거리 INF로 초기화 2. 2차원 배열 graph를 이용해 간선의 정보 저장 3. 시작 노드로 가기 위한 최단 경로는 0으로 초기화 하여 heap에 삽입 4. 다익스트라 알고리즘 수행 5. 여전히 거리가 INF라면 경로가 없는 것이므로 INF출력 6. 그렇지 않다면 최단 경로 출력

정점의 개수 V, 간선의 개수 E 정점 정보 a,b 가중치 c 1. 2차원 배열이고 경로의 크기를 나타내는 graph를 INF로 초기화 2. 플로이드 워셜 알고리즘을 이용해 자기 자신으로 가는 가중치는 0으로 초기화 3. 자기자신이 아니라면 A에서 B로 가는 최단 거리보다 A에서 K를 거쳐 B로 가는 거리가 더 짧은지 검사하여 최단 경로를 저장 4. 여전히 graph가 INF라면 i에서 j로 갈 수 없는 경로임 5. 그렇지 않다면 최단 경로 출력

가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제 1. 시작점을 queue에 넣어서 너비 우선 색인 BFS를 이용해 다중 시작점에서 가까운 지점부터 날짜를 업데이트하기 시작함. 2. 이중 for문으로 graph에 0이 있다면 -1을 출력하고 그렇지 않다면 최댓값을 출력함