본문 바로가기

Time waits for no one 😎
FE 개발자 지망생의 기술 블로그입니다.
[Github - https://github.com/inthhh]

블로그 내 검색

📚 전공 공부/문제해결기법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(.. 2023. 6. 16.

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

[문제해결기법] 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) -=.. 2023. 6. 16.

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

[문제해결기법] 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; }.. 2023. 4. 19.

[문제해결기법] 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.. 2023. 4. 18.

이전 1 2 다음

728x90

티스토리툴바