코딩처럼

삽입 정렬(Insertion Sort)은 비교 기반의 정렬 알고리즘으로, 배열의 각 요소를 순차적으로 선택하여 적절한 위치에 삽입하면서 배열을 정렬하는 방식이다. 이 알고리즘은 현재 배열의 일부분을 이미 정렬된 상태로 유지하면서, 새로운 요소를 삽입하는 방식으로 작동한다. 거의 정렬된 데이터에서 매우 효율적으로 동작하며, 구현이 간단하고 직관적인 특징이 있다.동작 방식 초기 상태: 첫 번째 요소는 이미 정렬된 것으로 가정한다.두 번째 요소부터 시작: 배열의 두 번째 요소를 선택한다.왼쪽에 있는 정렬된 부분과 비교: 선택한 요소를 왼쪽의 정렬된 부분에 삽입할 적절한 위치를 찾기 위해 비교한다.삽입: 비교하여 자신보다 큰 값들은 한 칸씩 오른쪽으로 이동시키고, 자신의 자리를 찾으면 그 위치에 삽입한다.반복:..

시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 척도이다. 주어진 입력 크기 n에 따라 알고리즘이 실행되는 데 걸리는 시간을 수학적으로 표현한 것이다. 이를 통해 알고리즘이 커지는 입력에 대해 얼마나 효율적인지 판단할 수 있다. 시간 복잡도 종류 O(1): 상수 시간 복잡도입력 크기에 상관없이 실행 시간이 일정하다.예: 배열에서 첫 번째 요소를 읽는 작업이 코드는 입력 크기에 상관없이 언제나 한 번만 실행되므로 시간 복잡도는 O(1)이다. n이 커져도 동일한 작업을 하며, 실행 시간이 변하지 않는다.public class ConstantTime { public static void main(String[] args) { int n = 100; System.out.print..

순열(permutation)요소 N개 중에 M개를 선택하여 순서에 상관있게 뽑는 경우의 수 카드 뽑기A, B, C, D, E로 이뤄진 5장의 카드순서를 생각하며 3장을 선택할 때 경우의 수모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지한다.첫 번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있다.첫번째 카드를 나열하고 난 다음, 두 번째 카드를 선택하는 방법에는 네 가지가 있다.두번째 카드를 나열하고 난 다음, 세 번째 카드를 선택하는 방법에는 세 가지가 있다.따라서 5 X 4 X 3 = 60 가지의 방법이 있다.이렇게 n개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 한다.순열은 순서를 지키며 나열해야 한다. 5장에서 3장을 선택하는 모든 순열의 수 = 5P3..

탐욕 알고리즘(Greedy Algorithm)이란?말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 탐욕 알고리즘으로 문제를 해결하는 방법선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가..

시간 복잡도문제를 해결하기 위해 알고리즘의 로직을 코드로 구현할 때 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미한다.  시간 복잡도 표기법Big - O (빅 - 오)Big - Ω (빅 - 오메가)Big - θ (빅 - 세타)위 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 이 중 Big - O 표기법이 가장 자주 사용된다. Big - O 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. O(1)Constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.입력값의 크기와 상관없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.public in..