본문 바로가기

📚 전공 공부/문제해결기법

(11)

[문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(..

[문제해결기법] 10. 계산 기하 계산 기하 2, 3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 기본 가정 : 2차원 공간, 정수좌표만 고려함. 실수 연산은 지양 polygon : 선분들로 이뤄진 닫힌 도형. 두 선분이 만나는 점은 하나뿐이다. 모든 점을 지나는 경로 n개의 점이 주어지면, 이 점들을 모두 지나고 시작점으로 돌아오는 경로를 구하시오. 단, 교차하지 않게 풀이 방법 y좌표가 가장 낮은 점을 기준점으로 잡음. O(n) 이 점을 지나는 직선과 다른 점들을 잇는 직선을 모두 구하고, 각의 크기에 따라 정렬한다. O(n log n). 그리고 이 순서대로 방문하면 됨 각의 계산 : arctan 함수와 비슷한 성질을 가지고, 분모가 0인 경우가 없도록 하는 함수를 직접 만들어서 계산한다. 점과 폴리건의 포함 관계 점의 좌..

[문제해결기법] 9. Flow Networks Flow Networks 가중그래프 G (모든 가중치는 양수) 에지의 가중치 = c(e) 시작점 s에는 들어오는 에지 없고, 도착점 t에는 나가는 에지가 없다 Flow : 이용가능한 용량을 기반으로, 간선을 따라 이동하는 값 모든 에지에 대해서, 0 ≤ f(e) ≤ c(e) flow 값 ( |f| )은 s에서 나가는 플로우 총량 = t로 들어오는 플로우 총량 최대 플로우 = 최소 cut 컷(cut) 주어진 노드 V를 두 집합으로 분할 컷 X에 대해서, f(X)는 X를 지나는 flow 총량 c(X)는 X를 지나는 에지의 c값 총량 최대 플로우 구하기 Ford-Fulkerson algorithm s→t 경로를 찾는다. BFS 진행 각 경로의 c(e) 최솟값을 m이라고 하자 각 경로의 에지마다, c(e) -=..

[문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까? 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리. 최소 신장 트리 (MST) 만들기 Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴. 구현법에 따라 시간복잡도가 차이남 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최..

[문제해결기법] 7. 이분 탐색 1. 탐색 오름차순으로 정렬된 N개의 정수 배열 A[0], ..., A[N-1]이 있다. X가 주어졌을 때, A[i] = X라면 i를 리턴하는 함수 find(N, X)를 작성하시오. 이 함수는 내부적으로 compare(i, val)을 호출하는데, 이는 A[i]=val이면 0, A[i] val이면 -1을 리턴하는 함수이다. N은 최대 100이다. int find(int sub, int N, int X) { int start = 0, end = N-1, t; while (start 0) start = mid + 1; // 기준값보다 작으면 start를 당기기 else if (v) end = mid - 1; // 기준값보다 크면 end를 당기기 else return mid; }..

[문제해결기법] 6. 세그먼트 트리 1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right..

[문제해결기법] 5. 욕심쟁이 기법 1. 욕심쟁이 알고리즘 : Greedy algorithm 매 단계마다 각 단계에서 최선의 선택을 한다. (현재 순간마다) 알고리즘이 매우 간단하나, 구한 답이 정답인지 검증이 필요하다. 기본 형태 2. 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해서 시작 시간 Si와 끝 시간 Fi가 주어진다. 각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하시오. ❖ 입력 ➢ 첫 줄에는 회의의 수 n ➢ 둘째 줄부터 n+1줄까지 두 정수 Si와 Fi ❖ 출력 ➢ 잡은 회의를 차례대로 출력(둘 이상의 답이 있을 수 있음) 가능한 접근 방법 - 회의시간이 짧은 것 부터 넣는다 -> 반례 존재 - 다..

[문제해결기법] 4. 자료구조2 1. 트리 지름 트리의 두 정점 u, v의 거리의 최댓값 (1) O(n^3) : brute force (2) O(n^2) : u를 고정하고 bfs한다. (3) O(n) 트리에서 임의의 정점 x를 선택하고 x에서 가장 먼 정점 y를 찾는다.(bfs) 이후 y에서 가장 먼 정점 z를 찾는다. 그러면 y와 z가 가장 멀리 떨어져있는 정점 쌍이다. 증명 원하는 답이 두 정점 u와 v이다. 그렇다면 3가지 가능성이 있는데, x에서 가장 먼 점이 y라고 하면 (1) x = u / x = v (2) y = u / y = v (3) x,y,u,v 모두 다른 경우 (1)과 (2)는 위 알고리즘의 답이 맞다는 것이 자명하다. (3)의 경우는 u~y 경로와 u~v 경로가 거리가 같은 경우 이외에는 없어야 한다. x,y,u,..

이전 1 2 다음

티스토리툴바