'자바' 태그의 글 목록

remote visual vm (0)	2016.12.18
RxJava (0)	2016.02.23
BigInteger 최대공약수 gcd 최소공배수 lcm 구하기 (0)	2016.02.22
java 로 클립보드 사용하기 (0)	2015.10.30
java 로 동영상 처리 (0)	2015.10.28

java 로 KMP 알고리즘

[프로그래밍] 2017. 12. 21. 21:43

import java.util.ArrayList;
import java.util.List;

public class KMP {

private String string;

private String pattern;

/**
     * 길이가 N 인 문자열 S(string) 에서 길이가 M 인 문자열 P(pattern) 를 탐색한다.<br/>
     * 시간복잡도는 O(N+M) 이다.<br/>
     *
     * @param string  원본 문자열
     * @param pattern 찾을 문자열
     */
    public KMP(String string, String pattern) {
        this.string = string;
        this.pattern = pattern;
    }

public void setString(String string) {
        this.string = string;
    }

public void setPattern(String pattern) {
        this.pattern = pattern;
    }

/**
     * @return 문자열이 일치하는 index 의 배열
     */
    public List<Integer> search() {
        List<Integer> searchIndex = new ArrayList<>();

char[] s = string.toCharArray();
        char[] p = pattern.toCharArray();
        int[] pi = getPI();
        int n = string.length();
        int m = pattern.length();
        int j = 0;

for (int i = 0; i < n; i++) {
            while (j > 0 && s[i] != p[j]) {// j > 0 : 한 글자 라도 일치한 것이 있는지
                j = pi[j - 1];
            }
            if (s[i] == p[j]) {
                if (j == m - 1) {
                    searchIndex.add(i - m + 1);
                    j = pi[j];
                } else {
                    j++;
                }
            }
        }

return searchIndex;
    }

/**
     * 탐색 실패 시 i번째까지 일치 할 경우 몇글자를 건너뛰어야 하는지 알려주는 pi 배열을 구한다.<br/>
     * pi 배열을 구할 때도 search 방식을 적용하여 O(M) 의 시간복잡도를 갖는다.<br/>
     *
     * @return pi 배열
     */
    public int[] getPI() {
        int m = pattern.length();
        int j = 0;
        char[] p = pattern.toCharArray();
        int[] pi = new int[m];

for (int i = 1; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = pi[j - 1];
            }
            if (p[i] == p[j]) {
                pi[i] = ++j;
            }
        }

return pi;
    }
}

저작자표시 변경금지

'[프로그래밍]' 카테고리의 다른 글

오늘부터의 목표 (0)	2022.07.18
Apache Ratis 소개 (3)	2018.03.21
dfs 알고리즘을 java 로 구현하기 (0)	2017.02.16
[IntelliJ] SVN 커밋 시 'is out of date' 에러 문제 (0)	2015.10.23
rsync 로 CRAN mirroring (0)	2015.10.06

Posted by FeliZ_하늘..

,

dfs 알고리즘을 java 로 구현하기

[프로그래밍] 2017. 2. 16. 00:33

dfs 알고리즘

import java.util.Scanner;

/**
 * dfs algorithm.
 *
 * @author hskimsky
 */
public class Dfs {

private static int numberOfVertex;

private static int numberOfEdge;

private static int[][] adjacencyMatrix;// 인접행렬

private static boolean[] search;

/*

/-2
    1  |
     \-3-4-5
    input number of vertex: 5
    input number of edge  : 5
    input vertex of start : 1
    input vertex of end   : 2
    input vertex of start : 1
    input vertex of end   : 3
    input vertex of start : 2
    input vertex of end   : 3
    input vertex of start : 3
    input vertex of end   : 4
    input vertex of start : 4
    input vertex of end   : 5
    print adjacency matrix
    1: 01100
    2: 10100
    3: 11010
    4: 00101
    5: 00010
    search 1: 1 0 0 0 0
    search 2: 1 1 0 0 0
    search 3: 1 1 1 0 0
    search 4: 1 1 1 1 0
    search 5: 1 1 1 1 1

/-4-\
      /-2     \
     /   \-5-\ \
    1         --8
     \   /-6-/ /
      \-3     /
         \-7-/
    input number of vertex: 8
    input number of edge  : 10
    input vertex of start : 1
    input vertex of end   : 2
    input vertex of start : 1
    input vertex of end   : 3
    input vertex of start : 2
    input vertex of end   : 4
    input vertex of start : 2
    input vertex of end   : 5
    input vertex of start : 3
    input vertex of end   : 6
    input vertex of start : 3
    input vertex of end   : 7
    input vertex of start : 4
    input vertex of end   : 8
    input vertex of start : 5
    input vertex of end   : 8
    input vertex of start : 6
    input vertex of end   : 8
    input vertex of start : 7
    input vertex of end   : 8
    print adjacency matrix
    1: 01100000
    2: 10011000
    3: 10000110
    4: 01000001
    5: 01000001
    6: 00100001
    7: 00100001
    8: 00011110
    search 1: 1 0 0 0 0 0 0 0
    search 2: 1 1 0 0 0 0 0 0
    search 4: 1 1 0 1 0 0 0 0
    search 8: 1 1 0 1 0 0 0 1
    search 5: 1 1 0 1 1 0 0 1
    search 6: 1 1 0 1 1 1 0 1
    search 3: 1 1 1 1 1 1 0 1
    search 7: 1 1 1 1 1 1 1 1
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("input number of vertex: ");
        numberOfVertex = scanner.nextInt();
        System.out.print("input number of edge  : ");
        numberOfEdge = scanner.nextInt();

adjacencyMatrix = new int[numberOfVertex][numberOfVertex];
        search = new boolean[numberOfVertex];

for (int i = 0; i < numberOfEdge; i++) {
            System.out.print("input vertex of start : ");
            int startVertex = scanner.nextInt() - 1;
            System.out.print("input vertex of end   : ");
            int endVertex = scanner.nextInt() - 1;
            adjacencyMatrix[startVertex][endVertex] = 1;
            adjacencyMatrix[endVertex][startVertex] = 1;
        }

System.out.println("print adjacency matrix");
        for (int i = 0; i < numberOfVertex; i++) {
            System.out.print((i + 1) + ": ");
            for (int j = 0; j < numberOfVertex; j++) {
                System.out.print(adjacencyMatrix[i][j]);
            }
            System.out.println();
        }

int searchStartVertex = 1;
        dfs(searchStartVertex);
    }

public static void dfs(int vertex) {
        search[vertex - 1] = true;
        System.out.print("search " + vertex + ": ");
        for (int i = 0; i < search.length; i++) {
            System.out.print((search[i] ? 1 : 0) + " ");
        }
        System.out.println();

for (int endVertex = 1; endVertex <= adjacencyMatrix[vertex - 1].length; endVertex++) {
            int edge = adjacencyMatrix[vertex - 1][endVertex - 1];
            if (edge == 1 && !search[endVertex - 1]) {
                dfs(endVertex);
            }
        }
    }
}

저작자표시 변경금지

'[프로그래밍]' 카테고리의 다른 글

Apache Ratis 소개 (3)	2018.03.21
java 로 KMP 알고리즘 (0)	2017.12.21
[IntelliJ] SVN 커밋 시 'is out of date' 에러 문제 (0)	2015.10.23
rsync 로 CRAN mirroring (0)	2015.10.06
GIS shp 파일 변환 (0)	2015.07.28

Posted by FeliZ_하늘..

,

현재값과 다음값 비교 자바 버전 compare current value & next value java version

[BigData]/[Apache Spark] 2015. 11. 13. 10:40

// 인덱스 부여
JavaPairRDD<String, Long> lineIndexRDD = jsc.textFile(path).persist(storageLevel).zipWithIndex();

// key, value pair 로 변환 (key: index, value: line) index 는 0 부터 시작
JavaPairRDD<Long, String> currLine = lineIndexRDD.mapToPair(new PairFunction<Tuple2<String, Long>, Long, String>() {
    @Override
    public Tuple2<Long, String> call(Tuple2<String, Long> lineIndex) throws Exception {
        return new Tuple2<>(lineIndex._2(), lineIndex._1());
    }
});

// 다음값 추출
JavaPairRDD<Long, String> nextLine = lineIndexRDD.filter(new Function<Tuple2<String, Long>, Boolean>() {
    @Override
    public Boolean call(Tuple2<String, Long> v1) throws Exception {
        return v1._2() > 0;
    }
}).mapToPair(new PairFunction<Tuple2<String, Long>, Long, String>() {
    @Override
    public Tuple2<Long, String> call(Tuple2<String, Long> lineIndex) throws Exception {
        return new Tuple2<>(lineIndex._2() - 1, lineIndex._1());
    }
});

// 부여한 index 로 join
JavaRDD<String> compareResult = currLine.join(nextLine).map(new Function<Tuple2<Long, Tuple2<String, String>>, String>() {
    @Override
    public String call(Tuple2<Long, Tuple2<String, String>> indexCurrNext) throws Exception {
        String curr = indexCurrNext._2()._1();
        String next = indexCurrNext._2()._2();

// your compare logic
        return "";
    }
});

제외되는 값 없이 비교하기 (비교 대상이 없는 경우 다음 값 반환)

// 인덱스 부여
JavaPairRDD<String, Long> lineIndexRDD = jsc.textFile("").persist(null).zipWithIndex();

// key, value pair 로 변환 (key: index, value: line) index 는 0 부터 시작
JavaPairRDD<Long, String> currLine = lineIndexRDD.mapToPair(new PairFunction<Tuple2<String, Long>, Long, String>() {
    @Override
    public Tuple2<Long, String> call(Tuple2<String, Long> lineIndex) throws Exception {
        return new Tuple2<>(lineIndex._2(), lineIndex._1());
    }
});

// 다음값 추출
JavaPairRDD<Long, String> nextLine = lineIndexRDD.mapToPair(new PairFunction<Tuple2<String, Long>, Long, String>() {
    @Override
    public Tuple2<Long, String> call(Tuple2<String, Long> lineIndex) throws Exception {
        return new Tuple2<>(lineIndex._2() + 1, lineIndex._1());
    }
});

// 부여한 index 로 join
JavaRDD<String> compareResult = currLine.leftOuterJoin(nextLine).map(new Function<Tuple2<Long, Tuple2<String, Optional<String>>>, String>() {
    @Override
    public String call(Tuple2<Long, Tuple2<String, Optional<String>>> indexCurrNext) throws Exception {
        String next = indexCurrNext._2()._1();
        Optional<String> currOptional = indexCurrNext._2()._2();
        String curr = null;
        if (currOptional.isPresent()) {
            curr = currOptional.get();
        } else {
            return next;
        }

// your compare logic
        return next;
    }
});

저작자표시 변경금지

'[BigData] > [Apache Spark]' 카테고리의 다른 글

Databricks Data Engineer Professional Exam 후기 (2)	2023.06.18
spark rest 호출 (0)	2016.02.18
용어정리 (0)	2016.02.06
spark 피어슨 상관계수 계산 (0)	2015.11.09
Apache Spark 1.5.0 설치 (0)	2015.09.21

Posted by FeliZ_하늘..

,

java 로 클립보드 사용하기

[Java] 2015. 10. 30. 13:24

http://www.javapractices.com/topic/TopicAction.do?Id=82

저작자표시 변경금지

'[Java]' 카테고리의 다른 글

RxJava (0)	2016.02.23
BigInteger 최대공약수 gcd 최소공배수 lcm 구하기 (0)	2016.02.22
java 로 동영상 처리 (0)	2015.10.28
java 에서 외부 프로세스 실행하기 (0)	2015.09.08
java 로 ssh 연결 (0)	2015.04.17

Posted by FeliZ_하늘..

,

Java Code Conventions

[Java] 2015. 2. 10. 10:48

http://kwangshin.pe.kr/blog/java-code-conventions-%EC%9E%90%EB%B0%94-%EC%BD%94%EB%94%A9-%EA%B7%9C%EC%B9%99/

저작자표시 변경금지

'[Java]' 카테고리의 다른 글

java 로 ssh 연결 (0)	2015.04.17
추가 변수 없이 두 변수를 swap 하기 (0)	2015.04.14
Maven (0)	2015.01.23
jdbc 드라이버로 hikari library 를 사용하기 (0)	2015.01.03
browser 가 아닌 java 로 http 통신하기 (0)	2015.01.03

Posted by FeliZ_하늘..

,

Apache HttpClient 로 PutMethod 사용하기

[Web] 2015. 1. 30. 22:19

긴 말 필요없이 바로 소스

public static void main(String[] args) throws IOException {
	PutMethod putMethod = new PutMethod("http://123.123.123.123:8080/put.json");
	putMethod.addRequestHeader("customHeader", "customHeaderValue");
	putMethod.addRequestHeader("Accept", "application/json; charset=utf-8");

NameValuePair nameValuePair1 = new NameValuePair();
	nameValuePair1.setName("customKey1");
	nameValuePair1.setValue("customValue1");
	NameValuePair nameValuePair2 = new NameValuePair();
	nameValuePair2.setName("customKey2");
	nameValuePair2.setValue("customValue2");
	NameValuePair nameValuePair3 = new NameValuePair();
	nameValuePair3.setName("customKey3");
	nameValuePair3.setValue("customValue3");
	NameValuePair[] nameValuePairs = {nameValuePair1, nameValuePair2, nameValuePair3};
	putMethod.setQueryString(nameValuePairs);

HttpClient httpClient = new HttpClient();
	System.out.println("statusCode = " + httpClient.executeMethod(putMethod));
	System.out.println("responseBody = " + new String(putMethod.getResponseBody(), "UTF-8"));
}

저작자표시 변경금지

'[Web]' 카테고리의 다른 글

fiddler 로 디버깅하기 (0)	2015.08.14
Berryz WebShare (0)	2015.03.09
Tomcat 다중 서브 도메인 session 설정 (0)	2015.01.27
아파치2 톰캣7 로드밸런싱, 세션 클러스터링 설정하기 (1)	2015.01.19
Multicast Address 멀티캐스트 주소, 멀티캐스트 IP 주소, 멀티캐스트 Ethernet 주소 (0)	2015.01.19

Posted by FeliZ_하늘..

,

왕초보 프로그래머 Sky

'자바'에 해당되는 글 7건

java 에서 숫자의 자릿수 알아내기

'[Java]' 카테고리의 다른 글

java 로 KMP 알고리즘

'[프로그래밍]' 카테고리의 다른 글

dfs 알고리즘을 java 로 구현하기

'[프로그래밍]' 카테고리의 다른 글

현재값과 다음값 비교 자바 버전 compare current value & next value java version

'[BigData] > [Apache Spark]' 카테고리의 다른 글

java 로 클립보드 사용하기

'[Java]' 카테고리의 다른 글

Java Code Conventions

'[Java]' 카테고리의 다른 글

Apache HttpClient 로 PutMethod 사용하기

'[Web]' 카테고리의 다른 글

카테고리

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크

티스토리툴바