알고리즘 공부 계획서

목표

• 상반기 안에 알고리즘 프로 취득
• 알고리즘 문제해결전략 예제 난이도 하 문제 해결
  • 한 달에 3~4문제
• 1월 부터 매달 사전 문제 반드시 해결하고 매주 프로 도전하기

문제 목록

문제	페이지
PICNIC	155
LIS	230
JLIS	236
PI	239
ASYMTILING	259
NUMBERGAME	340
LUNCHBOX	376
ARCTIC	450
TRAVERSAL	686
NERD2	702
INSERTION	718

개념

탐색

이진탐색

• 찾고자 하는 값의 범위를 찾는다.
• while (min < max) 일 때 까지 반복
• mid = (min + max) / 2 로 바로 중간 값을 잡는다
• 원하는 범위의 값이 만족하면 mid 값은 정답의 후보, min = mid + 1;
• 원하는 범위의 값에 만족하지 않으면 max = min;

이러한 방법으로 범위를 반반으로 줄이는 방법

인덱스트리

• 구간의 합을 구하거나, 구간의 값을 업데이트 하면서 구간의 합을 구할 때..
• 구간의 값을 업데이트 하면서 무엇인가 값을 구할 때..
• 주어진 값 N개 보다 4배로 생성(통상적)
• 값이 들어갈 idx를 구한다 java idx = 1; while (idx < N) { idx *= 2; } idx--;
• tree를 만들고, update가 되면 update를 시켜 준다.
• 부모 노드의 idx 계산에 유의해서 만듬

그래프

union find 자료 구조

• a 노드와 b 노드가 같은 부모를 바라보고 있는가?? a와 b가 연결이 되었는가?? 판단
• D[i] = i 로 초기화 노드의 갯수 N개 생성
• a와 b가 연결이 되어 있다면, D[find(a)] = find(b);
• find 함수는 D[a] == a 면 return a; 아니면 D[a] = find(D[a]);
• isUnion(a, b)는 find(a) == find(b)

최소 신장 트리(소검 페이지 군사도로 연결)

• 간선을 받는데, 간선의 갯수만큼 간선리스트를 만든다.
  • G[E][3] / [0] 출발점 [1] 도착점 [2] 비용
• 간선의 비용대로 오름차순
• 간선의 수만큼 for문을 돌리면서 간선의 비용이 작은 순으로 union을 한다
  • 이 때 union-find를 사용
• 간선의 개수가 N-1일 때 break;

위상정렬(topological 정렬)

• 우선순위가 있는 그래프, DAG, 방향성이 있고, 사이클이 없는 그래프
• 선수학습, 공정의 과정 등등
• Node class와 Link Class 생성
  • Node : no, indgree, totalTime(노드까지 도착해야할) List
  • Link : targetNode, 비용(시간) 등등..
• Q를 생성하여 indegree가 없는 것들을 넣어 준다.
• Q가 없을 때 까지 하나씩 꺼낸다.
• 해당 목적지 노드의 indgree를 하나 줄이고, 해당 조건 시간 만큼 비교를 하고 Node의 totalTime을 업데이트
• 해당 목적지 노드의 indegree가 0일 경우 Q에 추가

다익스트라(최단거리 구하는 방법)

• 간선간 가중치에 음수가 없을 경우 사용
• Node class와 Link Class 생성
• D[i] 배열 생성
  • i노드 까지 가는데 최소 가중치 저장
  • 초기 값은 해당 문제의 최대값으로 넣어줌, 시작점은 0으로 업데이트
• pq를 사용하고, 정렬은 가중치에 대해 오름차순으로
  • Queue<int[]> pq = new PriorityQueue<>(new Compa)
  • 첫번째 요소는 노드, 두번째 요소는 D[i](해당 노드까지 도착하는데에 비용)
• pq에서 하나씩 꺼내어 빌 때까지 돌림
• 만약 queue의 비용이 D[i]와 같지 않으면 continue
  • 왜냐하면 최단거리로 갈떄마다 D[i]의 값을 업데이트 하기 때문에 D[i] 값이 최소값임
• 해당 노드의 간선만큼 for문을 돌리고, 비용을 비교
  • D[link.target.no] > D[q[0]] + link.time 만족하면 최소값 업데이트 하고, pq에 넣어줌
• 값이 업데이트 되지 않았으면(맥스값) 도달하지 못함, 그렇지 않을 경우 최소 값

벨만포드무어(최단거리 구하는 방법)

• 간선간 가중치가 음수일 경우에도 사용 가능
• 간선리스트 생성 path[E][3]
• D[i] 배열 생성
  • i노드 까지 가는데 최소 가중치 저장
  • 초기 값은 해당 문제의 최대값으로 넣어줌, 시작점은 0으로 업데이트
• 노드의 갯수만큼 for문 돌리고 그 안에 간선의 갯수만큼 돌림 (V * E)
  • D[path[j][0]] 출발지에 한 번 갔다면(max_value 값이 아님) 그때 비용과 그 출발지의 도착점의 비용이 출발점과 주어진 가중치 비교

for (int i = 1; i < N; i++) { for (int j = 0; j < M; j++) { if (D[path[j][0]] != MAX_VALUE && D[path[j][1]] > D[path[j][0]] + path[j][2]) { D[path[j][1]] = D[path[j][0]] + path[j][2]; } } }

• 음수 사이클 확인은 간선 만큼 돌리면서 간선 값이 업데이트가 된다면 음수사이클 생기는 것임
• 값이 업데이트 되지 않았으면(맥스값) 도달하지 못함, 그렇지 않을 경우 최소 값

플로오드(최단거리 구하는 방법)

• 전체 쌍일 경우 가능
• 인접행렬 생성함, 초기 D[i][j]에 최대값 넣어줌
• 주어진 간선의 값을 넣어줌
• N3 포문을 세번 돌림
  • for k = 1 ~ N / for s = 1 ~ N / for e 1 ~ N
• D[s][e] > D[s][k] + D[k][e] 일경우 값을 업데이트
• 값이 업데이트 되지 않았으면(맥스값) 도달하지 못함, 그렇지 않을 경우 최소 값

LCA(최소 공통 조상)

• 인접리스트를 통해 그래프 정보를 받음
• bfs를 돌면서 depth[]와 parents[0][i] 정보를 입력
• fillParents()
  • for k = 1 K-1 / for i = 1 N
  • parents[k][a] = parents[k-1][parents[k-1][i]];
• lca()
  • a가 depth더 크게 맞춤
  • a와 b의 depth를 맞춰 줌
  • depth가 같기 때문에 a와 b의 부모를 찾기 위해 k = K-1; k >= 0 위에서 부터 바로 위 조상까지 돌림
• return paretns[0][a];