🧠 Computer Science

완전탐색❓완전탐색은 알고리즘 패러다임중 하나로 가능한 모든 해를 찾아내어 그 중 조건을 만족하는 최적해를 찾아내는  방법이다. 완전탐색은 모든 가능성을 확인하기때문에 가장 정확하고 최적의 해를 구할 수 있지만, 시간복잡도가 매우 높아질 수 있다. 예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능) 모든 문제에 대해 완전탐색을 적용시키면 항상 답은 구해지겠지만 코딩테스트가 제한하는 시간안에 문제를 해결하지 못 할 가능성이 크다. 그렇기에 완전탐색을 사용해야 할 시점은 다음과 같다. 1. 주어진 입력의 범위가 작아 가..

ArrayList 란?리스트는 배열의 특별한 유형이라고 할 수 있다. 그 중 ArrayList는 배열의 상위호환 버전 정도로 이해하면 된다. 기존의 배열만으로는 자료를 담고 관리하는데 약간 불편함이 있어서 나온 것이 ArrayList 이다. 배열은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조이다.    배열의 이러한 특성은 특정 상황에서 큰 장점이 된다. 예를 들어, 데이터의 크기가 미리 알려져 있고 변하지 않는 경우, 또는 빠른 랜덤 접근이 필요한 경우에 배열은 매우 효과적이다. 그러나 배열의 크기를 변경하기 어렵다는 점은 동적인 데이터 처리에 제한이 될 수 있다.    리스트는 데이터 요소들을 논리적 순서에 따라 저장하여 배열보다 더 유연한 자료구조이다.     ArrayLi..

개요배열(Array)은 컴퓨터 과학에서 가장 기본적이고 널리 사용되는 선형 데이터 구조이다. 데이터 구조가 선형이라는 것은 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있음을 뜻한다.  이 구조는 데이터를 순차적으로 저장하고 접근하는 방식을 제공하며, 많은 알고리즘과 프로그램의 기반이 된다. 배열은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조이다. 배열의 주요 특징은 다음과 같다.   고정된 크기: 배열은 생성 시 크기가 정해지며, 이후 변경이 어렵다. 인덱스 기반 접근: 각 요소는 0부터 시작하는 인덱스를 통해 직접 접근할 수 있다. 빠른 접근 속도: 인덱스를 통한 요소 접근은 O(1)의 시간 복잡도를 가진다. 메모리 효율성: 연속된 메모리 공간을 사..

퀵 정렬이란?퀵 정렬이란 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다. JAVA의 Arrays.sort()도 내부적으로 피벗을 하나가 아닌 두 개 사용하여 배열을 세 부분으로 나눈 Dual-Pivot QuickSort를 사용한다. 퀵 정렬은 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇 설정을 무엇으로 하느냐에 따라 효율이 크게 달라진다. 분할 방법은 Hoare(호어), Lomuto(로무토) 방법이 존재하고, Pivot 설정은 랜덤 피봇, 중앙값 피봇, 이중 피봇, 하이브리드 피봇 등 다양한 방식이 있지만 가장 단순한 형태는 인덱스를 배열의 한 부분으로 고정시킨 고정값 피봇이다.(보통 첫 번째 값, 마지막 값, 혹은 가운데 인덱스를 고정) [이것이 코..

삽입 정렬이란?삽입 정렬은 숫자 카드를 정렬하는 방법과 유사하다. 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교해 삽입할 위치를 지정한 후, 원소를 뒤(오른쪽)로 옮기고 지정된 자리에 자료를 삽입한다. 삽입 정렬 장점과 단점삽입 정렬 장점구현이 쉽고, 이해하기 쉽다.적은 데이터나 거의 정렬된 데이터에 대해 효율적이다.삽입 정렬 단점데이터의 양이 많아질수록 비효율적이다.최악의 경우 시간 복잡도가 O(n²)이다. 시간 복잡도알고리즘BestAvgWorstRun-time(정수 60,000개) 단위: sec삽입정렬O(n)O(n²)O(n²)7.438선택정렬O(n²)O(n²)O(n²)10.842버블정렬O(n²)O(n²)O(n²)22.894셸 정렬O(n)O(n¹·⁵)O(n²)0.056퀵 정렬O(nlogn)O(..

선택 정렬이란?선택 정렬은 정렬되지 않은 데이터들에 대해 `가장 작은 데이터를 찾아` 가장 앞의 데이터와 교환해나가는 방식이다. 최솟값의 자리를 변수에 저장해놓고 그 자리의 값과 나머지 값들을 비교하며 최종 최솟값을 찾는 반복문이 끝나면 그때 스왑해준다. 선택 정렬 장점과 단점장점구현이 쉽다.내림차순으로 정렬되어있는 요소를 오름차순으로 재정렬할 때 효율이 좋다.비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 자료상태라면 효율적이다.(버블정렬과 비교했을 때, 똑같은 O(n2) 의 시간복잡도를 갖지만, 시간을 측정해보면 버블정렬보다 시간이 짧게 소요됨.)단점서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않다.(중복된 값이 2개 있을 때 요소의 순서가 바뀔 수 있음.)이미 정렬된..