이진 탐색 및 파라메트릭 서치의 이해 및 적용

코딩 테스트를 공부하면서 이진 탐색를 알고리즘을 학습했다. 먼저 해당 유형을 접해보면서 익숙해지는 과정을 진행했다. 백준 문제를 풀면서 파라메트릭 서치 방법을 접할 수 있었고, 어떤 방식으로 이진 탐색과 파라메트릭 서치의 차이점과 예제를 통해 파라메트릭 서치를 문제에 적용해보며 파라메트릭 서치가 무엇인지를 정리하고 공유하고자 한다. # 이진 탐색 - Binary Search 임의의 배열에서 특정 원소를 탐색하기 위해선 배열의 모든 원소를 하나씩 들여다보면 된다. 반복문을 통해 배열의 모든 원소를 하나씩 확인하는 방법을 완전 탐색(BruteForce Search)라고 부른다. 완전 탐색은 O(N)의 시간 복잡도를 갖는다. 단순하게 배열의 길이만큼 연산 횟수가 선형적으로 늘어난다. 10,000,000개의 원..

• format_list_bulleted Dev/Algorithm
• · 2023. 12. 18.
• textsms

모듈러 분배 법칙의 이해 - 나머지 연산 분배 법칙

사칙 연산과 마찬가지로, 정수의 나머지에 대해서도 연산 개념이 존재한다. 코딩 테스트에서 명시적으로 나머지 연산의 결과를 요구할 때가 있다. 또는 풀이 과정에서 나머지 연산 중 수가 너무 크다면(int 형을 벗어나게 된다면), 모듈러 분배 법칙을 적용해야할 수 있다. 최근에 풀었던 문제 중, 명시적으로 다음과 같은 구문이 있었다. - 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 이런 경우, 수가 일반적인 범위(integer)를 벗어난다는 것을 명시적으로 알려주었기 때문에 추가적인 처리를 해주어야한다. 본인은 python을 사용하여 문제를 해결하여 Big Integer에 대한 문제를 고민하지 않아도 되지만, 나머지 연산 자체가 부하가 큰 ..

• format_list_bulleted Dev/Algorithm
• · 2023. 11. 22.
• textsms

기초 정렬 알고리즘 - 삽입(Insertion),선택(Selection), 버블(Bubble) - Python 예제

Python List 기본 정렬 방법 1차원 배열(List of Python)에선 정렬이 필요한 경우가 많다. 정렬은 오름차순 정렬과 내림차순 정렬이 존재하고, Python의 경우 내장 함수와 List 클래스의 메소드로 List의 정렬을 기본적으로 제공한다. 아래는 Python에서 List를 각각 오름차순, 내림차순 정렬하는 코드의 예시이다. TestList=[5, 15, 2, 6, 12, -15, 4, 9, 11] TestList.sort() # inplace Sort - Method of List TestList.sort(reverse = True) # inplace Sort - Method of List sorted(TestList) # Function of Python sorted(TestList..

• format_list_bulleted Dev/Algorithm
• · 2023. 7. 1.
• textsms

소수(Prime Number) 판별 및 개수 세기 - 에라토스테네스의 체(Sieve of Eratosthenes) - Python 예제

소수(Prime Number)란? 소수는 자기 자신과 1로만 나누어 떨어지는 자연수이다. 2, 3, 5, 7, 11, 13, 17 , , , 소수 판별법 1 - O(N) 방식 만약 한 숫자에 대해서 소수인지 아닌지를 판별하기 위한 가장 기본적인(느린) 방법으론 2 ~ 해당 숫자인 숫자들의 나머지 연산 결과가 0인지 아닌지를 조건문을 통해 판별하면 된다. 이런 방식을 사용할 경우, 시간 복잡도는 O(N)을 갖게된다. 7에 대해서 소수 판별을 적용하면 7 % 2 = 1, 7 % 3 = 1, 7 % 4 = 3, 7 % 5 = 2, 7 % 6 = 1 따라서, 7은 1과 7을 통해서만 나누어 떨어지므로 소수이다. 이를 Python 예시로 확인하면 다음과 같다. def isPrime_BigON(N): isPrime..

• format_list_bulleted Dev/Algorithm
• · 2023. 6. 27.
• textsms

최대공약수(GCD), 최소공배수(LCM) - 유클리드 호제법(Euclidean algorithm) - Python 예제

최대공약수 - Greatest Common Divisor 최대 공약수는 두 수를 모두 나눌 수 있는 수 중에 가장 큰 수이다. ex) GCD of 15 and 7 is 1 ex) GCD of 25 and 15 is 5 최소공배수 - Least Common Multiple 최소 공배수는 두 수의 공통된 배수 중 가장 작은 수이다. ex) LCM of 15 and 7 is 105 ex) LCM of 25 and 15 is 75 최대공약수(GCD)와 최소공배수(LCM)의 관계 최대 공약수와 최소 공배수는 아래의 관계를 가진다. A * B / GCD of A and B = LCM of A and B 이를 위의 예시에 적용하여 풀면 아래와 같다 7 * 15 / 1 = 105 is LCM of 7 and 15 25..

• format_list_bulleted Dev/Algorithm
• · 2023. 6. 26.
• textsms