룰루랄라 알고리즘

이 방법 말고도 stack을 pop하여 마지막 값 -1을 없애버려도 되지않을까

트리의 지름은 루트(또는 아무 노드)에서 가장 먼 노드를 찾고 그 노드부터 가장 먼 노드를 찾아 길이를 구하면 됨 dfs(node_index, result2)를 수행 한 후에는 자기 자신으로의 가중치를 0으로 초기화 한다.

그래프를 따라 번갈아가면서 색을 칠하다가 이미 방문했던 정점이 이전 정점 색과 같은 색이라면 이분그래프가 아니다. 색은 dfs 함수에서 group과 -group을 번갈아 넘겨주면서 1과 -1로 표현한다. result를 True로 선언 하고 dfs 함수에서 만약 정점의 색이 같다면 False를 리턴해 result에 저장 마지막에 result의 값에 따라 이분그래프 판별 출력 *주의* 재귀 함수 dfs에서 return을 했을 때 현재 돌고있는 함수만 종료 된것이지 dfs함수 전체가 종료되는 것이 아니다. return False를 하더라도 종료되는 것은 dfs의 전체 과정이 아니라 딱 현재 실행되고 있는 함수뿐이다. 처음에 전역에서 호출된 dfs와 그 dfs가 호출한 dfs는 서로 다른 함수이며, 그 dfs가..

정점의 개수 N, 간선의 개수 M 1. 양방향 노선이므로 graph[a][b] ,graph[b][a] 모두 1로 초기화 2. 자기 자신으로 가는 단계는 0으로 초기화 3. 기존의 최저 단계와 a가 k를 거쳐 b로 가는 단계를 비교해 최솟값 저장 4. graph[i] 의 합이 가장 적은 사람 즉 케빈베이컨의 합이 가장 적고 인덱스가 가작 작은 사람 출력

마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기 무조건 마지막 계단 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. 오름차순 정렬하여 출력