알고리즘 (17) 썸네일형 리스트형 데크, 우선순위 큐 Deque스택과 큐의 특징을 모두 갖고 있는 복합 자료형양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상 자료형Deque deque = new LinkedList();우선순위 큐어떠한 특정 조건에 따라 우선순위가 가장 높은 엘리먼트가 먼저 추출되는 자료형정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있다.시간 복잡도삽입,삭제: O(S(n)) 다익스트라 최단 거리를 구하는 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색에지는 모두 양수시간 복잡도: O(ElogV)원리인접 리스트로 그래프 구현하기최단거리 배열 초기화값이 작은 노드 고르기최단 거리 배열 업데이트 하기3~4 반복해 최단거리 배열 완성방문한 배열은 제외 위상 정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘시간 복잡도 O(V+E)ex) '답이 여러가지 경우에는 아무거나 출력한다' 라는 말이 키핵심 이론진입차수: 해당 노드를 바라보는 엣지의 수그래프 데이터가 주어지면, 연결 리스트를 만들고, 진입 차수 배열을 0으로 초기화진입 차수가 0인 노드 선택, 정렬 배열에 저장가리키는 데이터를 -1씩 해준다.다시 0인 노드를 선택, 정렬 배열에 저장가리키는 데이터를 -1 유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산, 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘연결 되어 있지 않으면 자기 자신이 대표노드가 되므로, 자기 자신을 저장항상 대표 노드끼리 연결해 준다.find 작동 원리대상 노드 배열에 index값과 value 값이 같은지 확인다르면 value와 같은 index로 이동index와 value가 같을 때 까지 반복나오면서 값을 1로 만들어 줘야함유니온 파인드 목적같은 집합인지 찾는 것중요사항find 구현값이 들어오면 그 값이 index와 value가 같은지 확인find를 돌아 나오면서 값을 변경하는 경로 압축과정다르면 그 index위치의 value는 재귀로 find를 돌았을 때 시작노드 그래프 노드와 에지(연결선)로 구성된 집합 유니온 파인드 그래프의 사이클 유무 판별하는 알고리즘 위상 정렬 사이클이 없는 방향이 있는 그래프 일 때 ex) 수강신청, 테크트리 같이 전 후 관계가 있는 그래프 다익스트라, 벨만-포드, 플로이드-워셜 최단거리 알고리즘 S 시작점에서 다른 모든 노드로 가능 최단거리를 구하는 알고리즘 간선의 가중치가 음수면 안된다. (다익스트라) 간선의 가중치가 음수도 가능(벨만-포드) 시작점이 없고, 모든 노드에 최단거리, 대신 시간이 오래걸림(플로이드-워셜) 최소 신장 트리 모든 노드를 연결하는 데 최소 비용을 사용해서 하는 알고리즘 유니온 파인드를 포함 표현 방법 에지리스트 가중치 없는 그래프 구현 2차원 배열로 표현 가중치가 있는 그래프 2차원 배열을 3으로 저장 벨만 포드, .. 소수 구하기 에라토스테네스의 체의 원리를 이용해 구하기 1부터 소수를 구하는 경우 앞에서부터 소수인지 확인하고 배수를 지운다. 시간복잡도 O(Nlog(logN)) 숫자를 점점 지워나가므로 그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 최적의 해를 보장 X 과정 현재 상태에서 가장 최선이라고 생각되는 해를 선택 현재 선택한 해가 제약 조건에 벗어나지 않는지 검사 해 집합이 전체 문제를 해결 할 수 있는지 검사 이진 탐색 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상 찾기 O(logn) 과정(오름 차순일 때) 현재 데이터에서 중앙값 선택 중앙값 > 타깃 데이터 일 때, 왼쪽 데이터 셋 선택 중앙값 < 타깃 데이터 일 때, 오른쪽 데이터 셋 선택 위에 내용을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 이전 1 2 3 다음