2-2 전공 (알고리즘)

Longest increasing SubsequenceSubsequence : 불연속자연수를 받아서 Longest incresing인(같은걸 허용안하고 계속 커지는 subsequence를 찾아라)연속이면 문제가 쉬움불연속이라서 어려운 거임결국 O(nlogn)으로 풀 수

완전 정보 게임게임의 정보가 참가자 모두에게 공개된 게임ex) 바둑, 오목, 체스누가 먼저 하는가에 따라서 승부는 이미 결정되어 있다(양쪽 다 최선을 다할 때)불완전 정보 게임에서는 최선을 다한다는 말을 할 수 없음최선을 다한다 : 완전 정보 게임에서는 그게 뭔지 정확

다이나믹 프로그래밍은 어려워도 방향이 존재함(왼쪽에서 오른쪽으로 푼다던지, 값이 작아지는 쪽으로 푼다던지 ... 이런식으로 방향 정할 수 있음)근데 그래프는 방향이 있나? -> 없음프로그램을 짠다고 했을 때 근처만 본다. -> 짜는게 굉장히 어려움저번에 배운 다익스트라

여기서 Cut Vertex찾는거Cut Vertex원래 입력 : 연결된 그래프가 주어짐연결된 그래프 중 제거했을 때 그래프가 끊어지는게 되는 거를 찾을 거임어떤 시간에? O(n+m)시간에 찾을거임이것보다 느리게는 쉬움이미 알고 있는 방법어느 한 군데에서 reachabil