Unfazed❗️🎯

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘이다. 매 반복마다 검색 범위를 반으로 줄이는 과정에서 중간 인덱스(mid)를 계산을 단순하게 (left + right) / 2를 사용하면 오버플로우의 위험이 존재한다.결론만 먼저 말하면, int mid = left + (right - left) / 2; 방식을 권장한다.1. 기본적인 중간 인덱스 mid 계산 방식이진 탐색에서는 검색 범위의 양 끝 인덱스인 left와 right를 기반으로 중간 인덱스를 계산한다.int mid = (left + right) / 2; 이 방식은 간단하지만, left와 right가 매우 큰 값일 경우 오버플로우가 발생할 수 있다.2. 오버플로우오버플로우는 프로그래밍 언어에서 변수에 할당된 메모리 범위를 초과하여 ..

두 값의 차이의 절대값이 서로 같은 경우 수학에서는 |a - b| = |c - d| 와 같이 표현한다.해당 개념을 잘 숙지하고 있으면 아래와 같이 다양한 상황에서 이 개념을 활용할 수 있다. 1. 기하학적 관계 파악예: N-Queen 문제에서 대각선 관계 확인응용: 격자 기반 게임, 경로 찾기 알고리즘위의 그림과 같이 행간 차이와 열간 차이가 동일한 경우 점 A, 점 B는 동일 대각선상에 놓인다는 것을 알 수 있다.해당 경우를 N-queen 문제에서 대각선상에 말이 놓이는 경우의 예외를 처리할 때 사용할 수 있다.ex ) if(Math.abs(x2 - x1) == Math.abs(y2 - y1))  A* 알고리즘에서 대각선 이동 비용 계산로봇 내비게이션에서 장애물 회피 경로 계산 double calcul..

2의 제곱수인지 판별하기 public class PowerOfTwoChecker { public static boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } public static void main(String[] args) { System.out.println(isPowerOfTwo(1)); // true System.out.println(isPowerOfTwo(2)); // true System.out.println(isPowerOfTwo(16)); // true System.out.println(isPowerOfTwo(18)); // false } } 2의 제곱수는 이진수로 표현했을 때, 1 뒤에 0만 여러 개 있는 형태를 ..

디지털 루트를 계산할 때 % 9 연산을 사용하는 것은 숫자의 '모듈로 9'에 대한 성질과 관련이 있다.숫자의 '각 자리수의 합'과 '모듈로 9' 연산 간의 관계를 살펴보자.모듈로 연산은 덧셈과 곱셈에 대해 분배 법칙을 만족한다. 즉, (a + b) % n = ((a % n) + (b % n)) % n과 (a * b) % n = ((a % n) * (b % n)) % n이다.각 자리수의 합 = 해당 숫자 모듈로 9어떤 숫자를 10진법으로 표현했을 때, 해당 수의 디지털 루트는 해당 수를 9로 나눈 나머지와 같다. 예를 들어, 숫자 467은 4 * 100 + 6 * 10 + 7과 같이 표현할 수 있다. 이 때, 100과 10은 (mod 9) 연산에 의해 1이 되므로  (즉, 100 % 9 = 10 % 9 =..

알아두면 코딩 테스트에서 쉽게 풀리는 문제들이 있어 정리해보았다. 매우 큰 숫자나 특정 형태의 데이터에 대해 배수 판별을 해야 할 경우, 단순히 % 연산자를 사용하는 것보다 배수 판별법이 더 효율적일 수 있다. 또, 문자열을 처리할 때, 숫자로 직접 변환하지 않고 배수 판별을 수행할 수 있다. 예를 들어, 긴 숫자가 문자열로 주어졌을 때, 각 문자를 배수판정법을 이용해 개별적으로 처리하여 배수 여부를 판별할 수 있다. 2의 배수 규칙: 숫자의 맨 끝자리가 0, 2, 4, 6, 8 중 하나 예시: 14, 28, 142 3의 배수 규칙: 숫자의 각 자릿수를 모두 더한 값이 3의 배수 예시: 123 (1+2+3 = 6, 6은 3의 배수) 코드 예시 public class MultipleOfThreeString..

부분 수열(Subsequence)은 어떤 주어진 수열에서 순서를 유지하면서 일부 또는 전체 원소를 선택하여 만들 수 있는 새로운 수열이다. 중요한 점은 선택된 원소들이 원래 수열에서의 순서를 유지해야 한다는 것이다. 수열이 A,B,C,D라고 할 때, 가능한 부분 수열 중 예시는 다음과 같다. A,B (첫 번째와 두 번째 원소 선택) B,D (두 번째와 네 번째 원소 선택) A,C,D (첫 번째, 세 번째, 네 번째 원소 선택) C (세 번째 원소만 선택) A,B,C,D (모든 원소 선택, 이 경우 원래 수열과 동일) [] (아무 원소도 선택하지 않음, 빈 부분 수열) 원소를 선택할 때, 원래 수열에서의 순서를 변경하거나 원소를 반복해서 사용할 수 없다. 예를 들어, B,A나 C,C는 유효한 부분 수열이 ..

덧셈 (A+B)%C=(A%C+B%C)%C ex) (20+6)%3=26%3=2 (20%3+6%3)%3=(2+0)%3=2 뻴셈 (A-B)%C=(A%C-B%C)%C ex) (20-6)%3=14%3=2 (20%3-6%3)%3=(2-0)%3=2 곱셈 (A*B)%C=(A%C)*(B%C)%C ex) (20*6)%3=120%3=0 (20%3)*(6%3)%3=(2*0)%3=0 나눗셈 (A/B)%C != (A%C)/(B%C)%C => 성립하지 않음 ex) (20/6)%3=3%3=0 (20%3)/(6%3)%3=(2/0)%3=>분모 0 X MOD 연산은 덧셈, 뻴셈, 곱셈에 대해서 분배 법칙이 성립한다. =>즉, 정답을 구한 뒤 % 연산을 하는 것이 아닌, 각 단계마다 %연산을 하면서 문제를 풀도록 하자. 백준 11051번 ..