알고리즘/알고리즘 Tip!
-
알고리즘 문제풀때 정규식(Regex)을 쓰는것이 좋을까??알고리즘/알고리즘 Tip! 2020. 4. 20. 23:10
정규 표현식은 특정한 규칙을 가진 문자열의 집합을 표현하기 위해 쓰이는 형식 언어입니다. 하지만, 알고리즘 성능에는 그다지 좋지가 않습니다. 그 이유는 "백트래킹" 때문입니다. 정규식은 왼쪽에서 오른쪽으로 탐색을 하는데 100% 매칭 되지 않으면 다시 뒤로 되돌아가면서 매칭을 시도합니다. 이를 백트래킹이라고 합니다. 자바 같은 경우에는 심지어 컴파일 작업을 거쳐야지만 사용이 가능합니다. Pattern.compile("ABC").matcher(s).find() s.contains("ABC") 다음 두 코드 중 어느 게 더 빠를까요?? 전자는 컴파일하고 (상대적으로) 복잡한 정규 표현식을 반복하므로 단순히 일련의 문자를 찾는 후자가 조금 더 빠릅니다. 그러면 정규식을 안 쓰는 게 좋지 않는가?? 속도만을 생..
-
[JAVA] 큐 구현은 어느것이 적당할까? LinkedList vs ArrayDeque알고리즘/알고리즘 Tip! 2020. 4. 20. 12:42
보통 배열의 경우 고정된 크기가 주어지기 때문에 검색이 빠르지만 삽입 삭제시 배열 크기 재 조정때문에 추가 비용 및 연산이 발생합니다. 그리고 공간 비효율성과 배열의 재배치가 일어납니다. 그렇다면 큐는 배열보다는 리스트로 구현하는게 낫지 않을까 하는 생각이 들 수 있습니다. 그러나 Queue를 구현할때 ArrayDeque로 구현하는 것이 LinkedList로 구현하는 것보다 빠르다고 Java API document는 설명하고 있습니다. 왜 ArrayDeque가 LinkedList보다 빠른걸까요?? 그 이유는 다음과 같이 2개 입니다. 출처 : http://javaqueue2010.blogspot.com/ ArrayDeque는 Array에 의해 지원되며 Array는 LinkedList보다 cache-loc..
-
[JAVA] 스택(Stack) vs 덱(Deque)알고리즘/알고리즘 Tip! 2020. 4. 19. 19:06
Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공합니다. Stack st = new Stack(); 더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용하면 됩니다. Deque st = new ArrayDeque(); 단, ArrayDeque 클래스는 Stack 클래스와는 달리 search() 메소드는 지원하지 않습니다. Java SE 6부터 지원되는 ArrayDeque 클래스는 스택과 큐 메모리 구조를 모두 구현하는데 가장 적합한 클래스입니다. 위의 내용은 자바 도큐먼트 사이트에서 직접 명시된 내용입니다. 왜 이런 구조로 되어있는 것일까요?? 그에 대한 분석이 2013년에 Badd..