알고리즘
-
알고리즘 문제풀때 정규식(Regex)을 쓰는것이 좋을까??알고리즘/알고리즘 Tip! 2020. 4. 20. 23:10
정규 표현식은 특정한 규칙을 가진 문자열의 집합을 표현하기 위해 쓰이는 형식 언어입니다. 하지만, 알고리즘 성능에는 그다지 좋지가 않습니다. 그 이유는 "백트래킹" 때문입니다. 정규식은 왼쪽에서 오른쪽으로 탐색을 하는데 100% 매칭 되지 않으면 다시 뒤로 되돌아가면서 매칭을 시도합니다. 이를 백트래킹이라고 합니다. 자바 같은 경우에는 심지어 컴파일 작업을 거쳐야지만 사용이 가능합니다. Pattern.compile("ABC").matcher(s).find() s.contains("ABC") 다음 두 코드 중 어느 게 더 빠를까요?? 전자는 컴파일하고 (상대적으로) 복잡한 정규 표현식을 반복하므로 단순히 일련의 문자를 찾는 후자가 조금 더 빠릅니다. 그러면 정규식을 안 쓰는 게 좋지 않는가?? 속도만을 생..
-
코딩테스트 연습 / 연습문제 / 최대공약수와 최소공배수 / JAVA알고리즘/프로그래머스 2020. 4. 15. 12:18
문제 설명 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다. 제한 사항 두 수는 1이상 1000000이하의 자연수입니다. 입출력 예 n m return 3 12 [3, 12] 2 5 [1, 10] 입출력 예 설명 위의 설명과 같습니다. 자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다. 나의 풀이 class Solution { public int[] solution(int n, int m) { int[] an..