본문 바로가기

알고리즘

 (13)
[알고리즘] 경우의 수 1. 곱의 법칙 (Multiplication Rule)정의: 두 개 이상의 사건이 순서대로 발생할 때, 각 사건이 일어날 수 있는 경우의 수를 곱한 값이 전체 경우의 수가 됩니다.수식:만약 사건1이 일어날 수 있는 경우의 수가 N가지이고, 사건2가 일어날 수 있는 경우의 수가 M가지라면, 두 사건이 연속해서 발생하는 경우의 수는N × M 가지입니다.예시: 음식과 음료 선택음식 선택: 삼겹살, 소고기, 치킨 (총 3가지)음료 선택: 콜라, 오렌지주스 (총 2가지)전체 경우의 수 = 3 × 2 = 6가지삼겹살 + 콜라삼겹살 + 오렌지주스소고기 + 콜라소고기 + 오렌지주스치킨 + 콜라치킨 + 오렌지주스 2. 곱의 법칙 확장 (Extension of Multiplication Rule)위 예시에서는 두 가지 사..
[알고리즘] 병합 정렬 MergeSort (Java 예제) 정렬 알고리즘이란?정렬 알고리즘은 배열의 원소들을 조건에 맞게 순서대로 정렬하는 알고리즘입니다. 원소들이 어떤 순서로 들어오는지에 따라 적절한 정렬 알고리즘을 선택할 수 있습니다.선택 기준시간 복잡도: 알고리즘이 실행되는 데 소요되는 시간공간 복잡도: 알고리즘이 사용하는 메모리의 양안전성 (Stability): 동일한 값의 원소들의 순서가 유지되는지 여부정렬 알고리즘 종류와 시간 복잡도정렬 알고리즘 종류최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도BubbleSort (버블 정렬)O(n)O(n^2)O(n^2)SelectionSort (선택 정렬)O(n^2)O(n^2)O(n^2)InsertionSort (삽입 정렬)O(n)O(n^2)O(n^2)MergeSort (병합 정렬)O(n log n)O(n log..
[알고리즘] 자릿수 더하기 (Java 예제) 1. 자바로 정수 자릿수 더하기나누기 연산자(/)/ 연산자는 정수 나누기를 수행하여 나머지를 제외한 값을 반환합니다. 예: 2345 / 10 = 234나머지 연산자 (%)나누었을 때 나누어 떨어지지 않는 값을 반환합니다.예: 2345 % 10 = 5 (2345를 10으로 나누었을 때의 나머지)예제 코드:class Solution { public int solution(int n) { int result = 0; // n이 0이 될 때까지 반복하기 while (n > 0) { // result에 n % 10을 더하기 result += n % 10; // 예) 2345 % 10 = 5 // n..
[알고리즘] 비트 연산자 정리 (Java 예제 포함) 논리 연산자논리 연산자는 false(0) 또는 true(1) 값을 다루는 연산자로, 기본적인 연산에는 AND, OR, XOR가 있습니다.1. AND 연산 (a AND b)정의: a와 b가 모두 1일 때만 1을 반환하며, 나머지 경우는 0을 반환합니다.진리표:ABA AND B0000101001112. OR 연산 (a OR b)정의: a와 b 중 하나라도 1일 때 1을 반환하며, 둘 다 0일 때만 0을 반환합니다.진리표:ABA OR B0000111011113. XOR 연산 (a XOR b)정의: a와 b 중 하나만 1일 때 1을 반환하며, 둘 다 같을 때는 0을 반환합니다.진리표:ABA XOR B000011101110 비트 연산자비트 연산자는 컴퓨터 내부에서 이루어지는 연산 중 하나로, AND, OR, XO..
[알고리즘] 진법 변환 (Java) 진법이란?진법은 숫자를 표현하는 체계로, 특정 숫자를 구성하는 각 자릿수의 가치를 나타내는 방법입니다. 우리가 일상적으로 사용하는 10진법은 0부터 9까지의 숫자를 사용하며, 각 자리의 위치에 따라 값이 10의 제곱으로 증가합니다.예를 들어, 숫자 2901을 생각해보면:1000의 자리: 2 × 1000 = 2000100의 자리: 9 × 100 = 90010의 자리: 0 × 10 = 01의 자리: 1 × 1 = 1이들을 모두 더하면 2901이 됩니다. 다른 진법도 비슷한 방식으로 숫자의 값을 계산합니다.10진법 -> 2진법 변환2진법은 0과 1 두 개의 숫자만을 사용합니다. 10진수를 2진수로 변환하는 방법은 매우 간단합니다: 주어진 수를 2로 나누고 나머지를 기록한 다음, 이 나머지를 역순으로 읽으면 됩..
[알고리즘] 동적계획법(Dynamic Programming : DP) 동적 계획법(Dynamic Programming)이란?동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 그 결과를 저장하고, 이를 바탕으로 전체 문제를 해결하는 알고리즘 기법입니다. 하위 문제들이 반복될 때, 이를 재계산하지 않고 저장해둔 결과를 재사용함으로써 효율적으로 문제를 해결합니다.동적 계획법의 특징중복되는 하위 문제: DP는 하위 문제들이 반복적으로 나타날 때 유용합니다. 예를 들어, 피보나치 수열을 계산할 때, 여러 번 동일한 계산을 해야 하는 경우가 많습니다. 이 때, 계산 결과를 저장해 중복 계산을 피할 수 있습니다.최적 부분 구조: 문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로부터 결정되는 구조입니다. 즉, 큰 문제를 작은..
[알고리즘] 소인수분해 (Java) 소인수분해란?소인수분해는 어떤 수 n을 더 이상 나눌 수 없는 소수(소인수)들의 곱으로 표현하는 것을 의미합니다. 예를 들어, 12는 더 이상 나눌 수 없는 소수인 2와 3의 곱으로 분해할 수 있습니다.소인수란?소인수란 어떤 수를 나누어떨어지게 할 수 있는 소수를 말합니다. 다시 말해, 소인수는 자신보다 작은 두 개의 자연수의 곱으로 나눌 수 없는 수입니다. 예를 들어, 2, 3, 5, 7 등이 소수이며, 어떤 자연수를 소수로 나누어 나머지가 0이 된다면 그 소수는 해당 수의 소인수입니다.소인수분해 예시: 1212를 소인수로 분해하는 과정은 다음과 같습니다:나눌 수 있는 가장 작은 소수인 2로 12를 나누면 6이 됩니다.다시 2로 6을 나누면 3이 됩니다.마지막으로 3을 나누면 1이 됩니다.즉, 12 =..
[알고리즘] 효율적으로 소수를 구하는 방법 (Java 예제 포함) 소수란?소수는 1과 자기 자신 외에는 약수가 없는 자연수입니다. 즉, 1과 자기 자신만으로 나누어떨어지는 숫자를 말합니다.예시2, 3, 5, 7, 11 등은 소수입니다.4, 6, 8, 9, 10 등은 소수가 아닙니다. (다양한 약수를 가지고 있기 때문입니다.)약수란?약수는 어떤 수를 나누어떨어지게 하는 수를 의미합니다. 즉, 주어진 수를 나누었을 때 나머지가 0이 되는 수입니다.예시12의 약수: 1, 2, 3, 4, 6, 12소수를 구하는 알고리즘소수를 판별하기 위해서는 주어진 수가 약수를 몇 개 가지고 있는지 확인해야 합니다. 소수의 경우 약수가 1과 자기 자신만 있어야 합니다.기본적인 소수 판별다음 코드는 1부터 n까지의 모든 약수를 찾는 방법을 사용한 소수 판별 방법입니다.public class M..

티스토리툴바