sncap Style

이전에도 비슷한 문제가 있었던것 같은데. Inversion Count 수 구하기... Swap의 개수를 구하는 문제와 동일한 형태로. 기본 코드는 아래와 같다. static int getInversionCnt(int[] A, int n) { int inv_cnt = 0; for(int i=0; i

void update(int node, int start, int end, int index, int val) { if (index end) return; if (start == end) { tree[node] = val; return; } update(tree, node * 2, start, (start + end) / 2, index, val); update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, val); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } int query(int node, int start, int end, int i, int j) { if (jend) return 0; if (i..

우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고, 이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 1. 배열+sort 2. k번째 원소 세그먼트트리 3. k번째 원소 BIT 4. BIT + 파라메트릭서치 + 바이너리서치 5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치 6. 2D 세그먼트트리 어렵다.. 이름만 들어도 어렵네 @,.@ 5번은 BOJ 7469번 가 대표적인 문제이다. http://blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221341875102 1번은 일단 단순히 M개의 원소를 벡터에 넣고 정렬하여 A[k-1]로 구하는 방법으로 딱, ..

LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다. 즉, Tree에서 두점 간의 거리를 구하는 방식으로 사용됨. 트리에서 LCA(1,N)을 구하는 쿼리는 O(N)의 시간복잡도를 가지게 됩니다. 하지만 LCA2와 같은 문제에서 O(N)에 쿼리를 처리한다면 우리는 O(N*M)의 시간복잡도를 가지고 시간초과를 보게 될 것입니다. 쿼리의 개수인 M을 조절해 줄 수는 없으니 적어도 LCA를 O(logN)의 시간복잡도에 구해줄 무언가가 필요합니다 우리는 O(N)의 방식으로 LCA를 구하는 방법을 약간 변형 시켜서 O(logN)의 시간복잡도에 LCA를 구해보겠습니다. 우선 전처리가 필요한데요. O(N)의 방..

이차원 평면으로 직선의 연립방정식으로 교차점을 구하는 방식은 예외처리를 따로 해주어야 하고, 복잡함. Cramer's rule(크라메르 공식)을 활용하여 해결 시도함. 만약, 선형 방정식의 해가 존재하지 않는다면 두 직선은 평행한 것이다. 당신은 2개의 직선을 나타내는 4개의 점을 입력받아 두 직선의 교점을 구할 수 있음. ▣ 2개의 연립방정식을 이용한 풀이 ax + by = e cx + dy = f 이것의 유일한 해, x, y는 ? 이를 코드화 하면.. 위 4개의 점에 대해서. L1 은 (x1,y1) (x2,y2) , L2 는 (x3,y3) (x4, y4) 라고 한다면. 두 직선의 교점인 x, y라고 정의함. Ax + By = E (L1) Cx + Dy = F (L2) L1 직선은 A = y2 - y1..

기본적인 BIT(Binary Index Tree : 펜윜트리) 는 빠르게 값을 변경하고, 누적합을 찾을때 사용되는 알고리즘 이다. 하지만, 순차 광역 .. 예를 들어 [a~b] 까지 값을 v 만큼 더해준다... 이런건 어떻게 할까? 이 알고리즘이 바로 Binary Indexed Tree Range Update 임. [참조 : 기타 Index tree 관련 설명은 아래 참조 ] https://medium.com/@harekrishnamahto18/range-sum-and-update-in-arrays-competitive-programming-82ae5039a16f Range Update에 대한 부분은 아래 상세 내용 참조 https://kartikkukreja.wordpress.com/2013/12/02..

[Lower Bound] static int lower_bound(ArrayList arr, int target) { int mid, start, end; start = 0; end = arr.size()-1; while (end > start) { mid = (start + end) / 2; if (arr.get(mid) >= target) end = mid; else { start = mid + 1; } } return end; } [Upper Bound] static int upper_bound(ArrayList arr, int target) { int mid, start, end; start = 0; end = arr.size()-1; while (end > start) { mid = (start..

프로그래밍 면접 질문Arden에 의해 2012 년 1 월 9 일 에 게시 됨원래 게시물에 대한 포인터가있는 모든 프로그래밍 인터뷰 질문 기사의 전체 목록입니다. 총 28 개 질문이 있고 28 개가 완벽한 숫자 이므로 (도널드 크 누스 (Donald Knuth)도 언급했듯이 ) 그 질문은 멈출 수있는 좋은 장소라고 판단했습니다.1. 배열 쌍 합 정수 배열이 주어지면 특정 값 k까지 합한 모든 쌍을 출력합니다.2. 행렬 영역 합 (Matrix Region Sum) 행렬 내의 직사각형 영역의 정수와 좌표의 행렬이 주어진다면, 그 사각형 내부에있는 수의 합을 구하십시오. 우리의 프로그램은 동일한 행렬로부터 다른 직사각형 영역으로 여러 번 호출 될 것입니다.3. 최대 연속 합계 정수 배열 (양수 및 음수)이 가장..

static int solution(int n, int[][] data) { // 좌표 압축 ArrayList xList = new ArrayList(); ArrayList yList = new ArrayList(); for (int i = 0; i < n; i++) { xList.add(data[i][0]); yList.add(data[i][1]); } ArrayList uniqueXList = new ArrayList(new HashSet(xList)); ArrayList uniqueYList = new ArrayList(new HashSet(yList)); Collections.sort(uniqueXList); Collections.sort(uniqueYList); // 구간합 배열 int[][] ..

절단점 찾는 알고리즘과 싸이클 찾은 알고리즘은 둘다 DFS방식을 이용하지만, 미묘하게 다르다..뭐가 다를까?. 절단선 = 단절선. (Bridge : 단절선) int dfs(int A, int parent) : A와 A의 자식 노드가 A에서 parent노드로 가는 간선을 사용하지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다. static int dfs(int s, int p, int d) { // start, parent, depth D[s]=d; int ck = d; for (Object des : list[s]) { Node nd = (Node)des; if(nd.e==p) continue; if(D[nd.e]==0) { int re = dfs(nd.e, s, d+1);..