코딩하는 해달이

1. 삽입 정렬이란?삽입 정렬(Insertion Sort)은 간단하고 직관적인 정렬 알고리즘입니다. 이 알고리즘은 데이터가 거의 정렬된 상태일 때 매우 효율적이며, 작은 데이터셋을 정렬할 때 유용합니다. 삽입 정렬은 리스트를 순차적으로 탐색하면서 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 하나씩 꺼내어 적절한 위치에 삽입하여 정렬된 부분을 확장해 나갑니다. 이러한 방식 덕분에 데이터의 안정성을 유지할 수 있는 안정 정렬(stable sort)입니다.2. 삽입 정렬 과정3. 작업 순서리스트의 첫 번째 요소는 이미 정렬된 것으로 간주합니다.두 번째 요소부터 시작하여 리스트의 끝까지 순회합니다.현재 요소를 이전의 정렬된 요소들과 비교하여 알맞은 위치를 찾습니다.요소를 해당 위치..

선택 정렬이란?선택 정렬은 제자리 정렬(In- place sorting) 알고리즘의 하나로 원소를 넣을 위치는 이미 정해져있으며, 어떤 원소를 넣을지 선택하는 알고리즘입니다.선택 정렬 과정작업 순서리스트를 순회하며 가장 작은 요소 찾기가장 작은 요소와 첫 번째 요소 교환리스트의 다음 위치로 이동반복시간 복잡도최악, 평균, 최선 모든 경우에 O(n^2)의 시간 복잡도를 가집니다.공간 복잡도O(1): 제자리 정렬 알고리즘으로 추가적인 메모리 사용이 거의 없습니다.장점구현이 간단하고 이해하기 쉽습니다.단점시간 복잡도가 O(n^2)이기 때문에, 데이터의 크기가 큰 경우 비효율적입니다.코드 public void selectionSort(int[] array) { int n = array.leng..

버블 정렬이란?버블 정렬은 무작위로 배치되어있는 요소들을 일정한 기준에 맞추어 정렬하는데 그 방법이 인접한 두 요소를 비교하여 의도한 순서가 될 때까지 교체하는 알고리즘입니다.버블 정렬 과정작업 순서첫 번째 인덱스부터 시작해서 두 요소를 비교한다.첫 번째 요소가 두 번째 요소보다 크면 서로 교체한다.이제 두 번째 요소와 세 번째 요소를 비교하여 교체가 필요한 경우 교체한다.마지막 요소까지 반복한다.시간 복잡도사이클을 돌 때마다 n, n-1, n-2, .... , 2, 1번 실행되게 되므로 시간 복잡도는 O(n^2)이다.코드이를 코드로 나타내면 다음과 같다.public void bubbleSort(int[] array) { int n = array.length; // 배열의 모든 ..

위상 정렬위상 정렬은 주로 작업 순서를 정하거나 의존성 관계를 해결할 때 사용하는 알고리즘으로 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘이다.특징비순환 방향 그래프에서만 적용이 가능하다.정렬 결과가 여러가지 일 수 있다.사이클이 있는 그래프에서는 위상 정렬이 불가능하다.  - 사이클 : 한 정점에서 출발하여 간선과 정점을 지나 다시 출발했던 정점으로 돌아오는 것알고리즘 구현 방법DFS(깊이 우선 탐색) 기반 방법 : 그래프를 DFS로 탐색하며 탐색이 끝나느 정점부터 스택에 삽입, 스택에서 꺼내는 순서가 정렬의 결과진입차수 기반 방법 : 진입차수가 0인 정점을 큐에 넣고 하나씩 꺼내면서 간선을 제거, 큐에서 꺼내는 순서가 정렬의 결과시간 복잡도O(V + E) (V : 정점의 수,..

원을 기준으로 임의의 점이 위치하고 있는 곳을 알아보자 원을 기준으로 점이 존재할 수 있는 위치는 크게 세가지로 나뉜다 점이 원의 내부에 존재 할 경우 점이 원의 외부에 존재 할 경우 점이 원과 접할 경우 먼저 설명을 쉽게하기위해 키워드를 정해놓겠다. 원의 중심 : O 원의 반지름 : R 임의의 점 : A 점이 원의 내부에 존재 할 경우는 선분 OA의 길이가 R보다 작은 경우이다. 점이 원의 외부에 존재 할 경우는 반대로 선분 OA의 길이가 R보다 큰 경우이다. 점이 원과 접할 경우는 선분 OA의 길이와 R의 길이가 같은 경우이다. 아래의 예시를 보자 반지름 R을 8이라 가정했을 때, C의 길이를 구하기위해 피타고라스 정리를 이용해서 C^2의 길이를 구한 후 R^2과 비교하여 점의 위치를 계산했다.

자료구조 수업때 과제를 하며 공부한 기록을 남긴다. [과제 2] 1.1원 다항식을 정의할 수 있다. 다항식의 이름은 x를 제외한 영문 소문자이다(예: f, g등) 2.변수는 항상 x이다. 3.각 항의 지수는 음이 아닌 정수이고, 계수는 정수이다. 4.=,+,-등의 앞뒤로 하나 이상의 공백이 있을 수도 있고 없을 수도 있다. 5. 항들이 반드시 차수에 대한 내림차순으로 입력되는 것은 아니며, 동일 차수의 항이 여럿 있을 수도 있다. 6. 함수는 항상 차수에 대한 내림차순으로 정렬되어 저장되고 출력되어야 한다. 7. 동일 이름의 함수를 새로 정의할 수도 있다. 이 경우 기존의 함수는 지워진다. ========================================================= -다항식의 ..

자료구조 수업때 과제를 하며 공부한 기록을 남긴다. [과제 1] 1.배열 활용하기 공백문자들이 문장의 앞, 중간, 뒤에 포함되어있는 스트링이 입력될 때 스트링의 문자 개 수 를 계산하여 다음과 같이 출력하라. (단, 단어 사이에 두개이상의 연속된 공백 문자들은 하나의 공백 문자로 대체) *출력결과 > hello hello: 5 > welcome to the class welcome to the class: 20 > programming is fun, right? programming is fun, right? 언어는 자신이 원하는 언어로 작성해도 좋습니다. ================================================================================= 나..

연결리스트를 배우면서 연결리스트로 구현한 스택에 대해서도 배워서, 직접 연결리스트로 스택을 구현해보려고 하던 중에 그냥 스택에 대해서도 블로그에 써 놓는게 더 도움이 될 것 같아서 스택부터 정리한 후 아래에 연결리스트로 스택을 구현해 보아야겠다. 스택이란? 스택은 기본적으로 후입선출(Last In First Out)을 기반으로 한 선형 구조이다. 이런 구조는 한쪽 끝에서만 자료의 출입이 이루어지기 때문에 기본적으로 push() 와 pop()연산이 필수적으로 필요하다. 여기서 push()는 '데이터를 밀어 넣는다'는 개념으로 데이터를 추가하는 입력 연산이고, pop()은 자료가 튀어나오는 것을 의미하여 출력 연산을 지칭한다. 그 외에도 조회 연산인 peek가 있는데 이 연산은 가장 마지막으로 들어간 데이터..