본문 바로가기

Java

(20)

페이징 처리 전체 DB의 수를 가져오는 함수 select count(*) from guestbook; 효율적인 처리를 위해서 limit 과 offset을 이용해서 필요한 페이지 만큼을 불러오겠다. select * from guestbook limit 2 offset 3; 위의 두가지 sql문법을 활용해서 효율적인 페이징 처리를 하려고한다. 기본적인 페이징 처리 원리 int totalCount = /*DB접속후 쿼리를 통해 얻은 값*/; int listCount = 10; int totalPage = (totalCount-1) / listCount + 1; if (totalCount % listCount > 0) { totalPage++; } listCount 한페이지에 불러올 리스트의 양이다. totalPage는 전..

트라이(Trie) : JAVA / 백준 5052 트라이 알고리즘 일반 적인 정수들은 O(1) 시간내에 비교가 가능합니다 . 1==1 ,123>4 처럼 단순연산으로 접근 할 수 있습니다. 하지만 String 같은경우에는 "ABC" == "ABCD" 를 고려하기 위해서는 최대 문자열의 길이 O(M) 시간이 걸립니다. (첫 번째 인덱스부터 계속 비교해 나가야 되기 때문입니다.) 따라서 기존 이진 트리로 정수형 데이터를 찾는데 걸리는 시간이 O(logN) 이라고한다면 문자열의 경우에는 O(MlongN) 시간이 걸리게 됩니다. 하지만 트라이 알고리즘을 사용한다면 O(M) 시간내에 자료를 찾을 수 가 있습니다. 문자열 집합 S={"BE","BET","BUS","TEA","TEN"} 을 트라이 자료구조로 표현하면 다음과 같습니다. 여기서 주황색으로 표시된 Node..

이분 매칭 알고리즘 ( JAVA),열혈강호1,2,3 문제 이분 매칭 알고리즘이란 용량이 1인 이분 그래프에서 최대로 매칭 할수 있는 수를 구하는 알고리즘이다. 기본적으로 DFS알고리즘을 사용한다. 알고리즘 매커니즘 기본 적으로 1~N 노드 까지 DFS 탐색을한다. 이때 각각의 노드마다 Dfs탐색을 한다. 1. 현재 here 노드에서 연결된 there 노드가 방문하지않았으면 there은 here과 이어젔다고 표시한후 true를 반환 2. 만약 there이 누군가와 연결되었다면 there과 연결한 간선을 다시 Dfs탐색하여 다른것과 매칭 할수 있는지 탐색 만약 할수 있다면 here과 there을 이어준다. 그리고 true를 반환한다. 3. 위에 1, 2 번으로 이을수 없다면 false를 반환한다. 4. 1 2 3 을 1~N 번 노드 까지 반복한다. 그때마다 Dfs..

네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA network flow는 실세계에서 적용이 가능한 유명한 알고리즘이다. network flow를 이해하기 위해서는 먼저 몇가지 용어 정리가 필요하다. A -> B 로가는 네트워크에 대해서 최대 x라는 트래픽으로 보낼 수 있다면 capactiy(a,b) = x 가된다. 즉 a->b로 보낼 수 있는 최대 용량은 x라는 뜻이다. 만약 a->b에서 실제 y라는 트래픽이 발생한다면 flow(a,b) = y 가된다. 즉 a->b로가는 유량은 y라고 한다. 여기서 몇가지 속성을 알아보자 1. 용량 제한 속성 flow(u,v) 0 을 만족하는 u v 간선을 경로라고 생각하고 BFS 너비우선 탐색으로 경로를 탐색한다. 3. 만약 경로가 없으면 알고리즘은 종료한다. 4. 만약 경로가 존재한다면 경로에서 가장작은 flow ..

JAVA : nextPermutation 다음순열 nextPermutation 구현의 아이디어 nextPermuation이란 [1,2,3,4,5] ->[1,2,3,5,4] ->[1,2,4,3,5] 처럼 현재의 상태에서 다음 순열을 찾는 알고리즘이다. 물론 조합 알고리즘을 이용해서 각각의 인덱스의 조합을 이용해서 찾아도 되지만 더빠른 넥스트 퍼뮤테이션을 사용해야 할때가 있다. 기본 순열 1 3 5 4 2 에 대해서 예를 들어보자! 아래와 같은 순열이 이어저있을 때 nextPermutation은 다음과 같은 4가지 조건을 확인 하면된다. 모든 탐색은 오른쪽에서 왼쪽으로 시작한다. 1. arr[i-1] < arr[i] 이 오른쪽에서 왼쪽으로 탐색하면서 제일처음 나오는 값을 찾는다. 2. 이제 i-1를 비교하면서 arr[i-1] < arr[j] 를 만족하는 값..

유니온 파인드 : JAVA 정의 어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다. graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다. 이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다. 이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다. 소스코드..

JAVA : Log 함수를 이용한 자리수 구하기 Math.log10 함수를 이용한 자리수 구하기. 1 2 3 public static void main(String args[]) { System.out.println((int)Math.log10(213)+1); } http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter Log10 값은 승수를 구해준다. 1은 10^0 10 은 10^1 100은 10^2 50은 1.69 정도 나온다.. 따라서 Math.log10을 이용한 값에서 (int)형으로 변환해서 소수를 제거후 +1 해주면 빠르게 자리수를 구할수 있다.

백준 : 17822 JAVA https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 글에 대한 설명이 턱없이 부족하다. 문제를 풀면서 테스트 케이스를 돌려보면서 확인해야한다. 1. 원판은 시작할때는 인접한 것을 c..

이전 1 2 3 다음

티스토리툴바