알고리즘 (14) 썸네일형 리스트형 [알고리즘] 위상 정렬 위상 정렬(Topological Sort)이란?방향성이 있는 그래프(Directed Acyclic Graph, DAG)에서 선행 관계를 유지하면서 모든 노드를 순서대로 나열하는 방법즉, 어떤 일을 수행하는 순서가 있을 때 그 순서를 결정하는 알고리즘 예시 : 특정 작업이 끝나야만 다른 작업이 가능할 때 위상 정렬을 알기 전 알아야 할 지식진입 차수(indegree) : 특정 노드로 들어오는 간선의 개수진출 차수(outdegree) : 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 과정위상 정렬 알고리즘은 큐를 사용하여 구현을 합니다.진입 차수가 0인 노드를 큐에 넣습니다.큐가 빌 때까지 다음 과정을 반복합니다.큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거새롭게 진입 .. [알고리즘] 경우의 수 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 =.. 이전 1 2 다음
