알고리즘/기본코드
-
Union-Find 연산의 성능 개선 어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다. 이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자. 기본 코드는 다음과 같다. package ch07_unionfind; import java.util.Arrays; public class P01_UnionFindTree { static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; static int[] repres = new int[src.length + 1]; // 각각의 멤버를 대표자로 하는 집합 생성 s..
Union-Find 연산의 성능 개선Union-Find 연산의 성능 개선 어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다. 이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자. 기본 코드는 다음과 같다. package ch07_unionfind; import java.util.Arrays; public class P01_UnionFindTree { static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; static int[] repres = new int[src.length + 1]; // 각각의 멤버를 대표자로 하는 집합 생성 s..
2020.10.10 -
LinkedList vs ArrayList Java에서 순서 있는 목록을 관리하는 인터페이스는 java.util.List 인터페이스이다. List의 특징은 순서가 있는 데이터의 집합으로 순서가 있기 때문에 데이터의 중복이 허용된다. List는 인터페이스이기 때문에 직접 객체를 생성할 수 없고 구현체 class가 필요하다. 이 구현체의 가장 대표적인 클래스가 java.util.ArrayList와 java.util.LinkedList이다. 먼저 각각의 특성에 대해 살펴보자. ArrayList ArrayList는 배열에서 출발한 List ArrayList는 이름에서 풍기듯이 내부적으로 배열을 만들고 데이터를 관리한다. transient Object[] elementData; // non-private to s..
LinkedList vs ArrayListLinkedList vs ArrayList Java에서 순서 있는 목록을 관리하는 인터페이스는 java.util.List 인터페이스이다. List의 특징은 순서가 있는 데이터의 집합으로 순서가 있기 때문에 데이터의 중복이 허용된다. List는 인터페이스이기 때문에 직접 객체를 생성할 수 없고 구현체 class가 필요하다. 이 구현체의 가장 대표적인 클래스가 java.util.ArrayList와 java.util.LinkedList이다. 먼저 각각의 특성에 대해 살펴보자. ArrayList ArrayList는 배열에서 출발한 List ArrayList는 이름에서 풍기듯이 내부적으로 배열을 만들고 데이터를 관리한다. transient Object[] elementData; // non-private to s..
2020.08.02 -
* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다. 다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는 KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다. Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다. KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치..
문자열 패턴 매칭 3 - KMP* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다. 다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는 KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다. Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다. KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치..
2020.02.28 -
Michael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다. 매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다. 해쉬값의 생성 해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 패턴의 해쉬값은 당연히 고정되어있다. 비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다. 이를 위해 패턴은 통상 아래 수식으로 계산된다. ..
문자열 패턴 매칭 2 - Rabin KarpMichael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다. 매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다. 해쉬값의 생성 해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 패턴의 해쉬값은 당연히 고정되어있다. 비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다. 이를 위해 패턴은 통상 아래 수식으로 계산된다. ..
2020.02.28 -
워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
문자열 패턴 매칭 1 - Brute Force워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
2020.02.28