🍒What I did today(GCD/LCM(최대공약수, 최소공배수), 순열/조합, 멱집합, 정규표현식)

Daily/TIL(Today I Leared)

Judaeng 2021. 3. 10. 01:42

✅Algorithm with Math

알고리즘 문제에서 자주 다루는 최소한의 수학만 익혀서 적재적소에 활용할 수 있는 능력을 기르는 시간이었다.

수학적 사고를 통해 컴퓨팅 사고를 할 수 있어야 한다는 것을 이해하려고 했다.

다양한 수학 개념이 있지만 알고리즘 문제, 코딩 테스트에서 자주 등장하는 주요 개념들이 3가지 있다고 한다.

그게 GCD/LCM(최대 공약수, 최소 공배수), 순열/조합, 멱집합이었다.

자세하게 다루면 좋겠지만, 오늘은 조금 이해하고 설명은 못하는 느낌인 것 같다.

정리하고 싶지만 시간에 쫓기고 있어서 못하고 있다💧

✅정규 표현식

정규표현식을 한 문장으로 정의하자면 문자열에서 특정한 문자를 찾아내는 도구라고 한다. 또는 복잡한 문자열을 처리할 때 사용하는 기법!

오늘 배우기도 했지만 전에 알고리즘 문제에서도 나왔고? 코플릿을 풀면서도 나온 부분이기 때문에 낯설지는 않았다.

하지만 나는 정규표현식과 안 친해서 잘 사용을 계속 못해왔다.

지금도 잘 못하지만 주말이나(?) solo study 시간이 오면 정리를 해봐야 될 것 같다. 이 부분도...

대충 정규표현식에는 두 가지 방법이 있다는 것만 기억한다.

리터럴 패턴, 생성자 함수 호출 패턴 이렇게 알고만 있는 것 같다.

이해는 시간이 남을 때 비슷한 예제와 같이 블로그에 정리해봐야 될 것 같다.

🍒Remember

✅이분 탐색

탐색 기법 중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식이다.

원래의 전부를 탐색하는 탐색 속도에 비해 빠르다.

이분 탐색을 하는 방법은 left, right, mid 값으로 탐색하는 것이다.

mid의 값은 (left + right) / 2로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교한다.

대충 순서 정리를 해봤다.

(left는 탐색 범위의 첫 인덱스, right: 탐색 범위의 마지막 인덱스)

(탐색을 원하는 구간[a, b]에 대해 a를 left, b를 right라고 했다.)

1. 이분 탐색을 하고자 할 때 이미 정렬이 되어 있어야 한다.

2. left, right로 미드값을 잡아준다.

3. mid 값과 구하고자 하는 값을 비교한다.

4. 비교할 시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1을 만들어주고 낮으면 right를 mid-1로 만들어준다.

5. left > right 가 될 때까지 1~3번을 반복해서 구하고자 하는 값을 찾는다.

이렇게 검색을 하면 전체를 검색하는 경우인 시간 복잡도가 O(n)과 비해서 O(log(n))으로 적다.

이진 탐색? 이분 탐색? 같은 의미인가?

헷갈리는 부분이라고 생각해서 정리해본다.

Binary Search 알고리즘은 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다고 한다! (결국 같다!)

이분 탐색은 분할 정복 기법(devide and conquer)을 응용한 것으로서 배열이 정렬되어 있을 때만 사용이 가능하다.

✅정규표현식

✅GCD/LCM, 순열/조합, 멱집합 문제 풀어보면서 이해해보기

오늘도 멘붕🤮