Daehyunii's Dev-blog

지금까지 공부했던 정렬들은 일반적인 정렬 알고리즘이었다. 이제는 보다 효율적인 정렬 알고리즘들에 대한 설명이다. 합병 정렬은 정확하게 말하면 분해와 합병을 하는 과정으로 정렬이 이뤄진다. 합병 정렬은 0개의 요소 또는 1개의 요소는 이미 정렬이 되어있다는 것을 활용하는 정렬 알고리즘이다. 즉 정렬되어 있지 않은 배열을 요소가 1개 또는 0개가 될 때까지 배열을 분할한 후 다시 정렬하면서 합병하는 것이다.(1개 또는 0개의 요소를 가지는 배열은 이미 정렬이 되어 있는 것이기 때문이다.) 우선 합병 정렬 알고리즘을 구현하기 위해서는 정렬되어 있는 두 배열을 합병하는 방법을 알아야 한다. 10.1 정렬된 두 배열 합병 의사코드 1. 우선 배열 두 개를 인수로 받는 함수를 정의하고, 마지막에 반환할 빈 배열을 ..

9.1 삽입 정렬 소개 삽입 정렬이란, 배열의 왼쪽 끝의 숫자를 정렬이 끝났다고 간주한다. 그리고 아직 작업하지 않은 숫자 중에서 왼쪽 끝에 있는 숫자를 꺼내서 왼쪽에 있는 작업이 끝난 숫자와 비교한다. 왼쪽의 숫자가 크다면 두 개의 숫자를 바꾼다. 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도달할 때까지 반복하여 정렬하는 방법이다. 말 그대로 삽입 정렬은 가장 왼편의 값을 정렬이 완료되어 있는 값으로 보고 나머지 요소들을 하나씩 꺼내와 정렬되어 있다고 가정한 왼편의 요소들과 비교하여 정렬되어야 하는 위치에 삽입하는 방식이다. 의사코드 1. 배열의 두 번째 요소를 선택하여 반복을 시작한다.(왜냐하면 가장 앞에 있는 요소는 정렬이 완료되었다고 간주하기 때문이다.) 2. 그 다음 두 번째 요소를 ..

8.1 선택 정렬 소개 선택 정렬은 버블 정렬과 비슷하지만 약간의 정렬 방식에 차이점이 있다. 많은 스왑을 통해서 가장 큰 값을 맨 뒤에 위치시키는 대신, 한 번에 모든 요소를 비교하여 가장 작은 값을 맨 앞에 위치시킨다. 그리고 그 요소를 제외한 나머지 요소들을 다 비교하여 가장 그 중 가장 작은 값을 첫 번째에 정렬된 요소 다음에 위치시킨다. 즉 배열내의 요소들 중 최솟값을 찾아 마지막에 바꾸어 맨 앞에 정렬시킨다. 우선 비교를 해야 하기 때문에 비교해야 할 요소들 중 가장 앞에 있는 값을 최솟값으로 잡고 그 다음 요소들과의 비교를 통해 최솟값을 찾는다. 이렇게 찾은 최솟값은 배열의 맨 앞에 정렬시키고, 그 다음 루프에서는 제외시키고 나머지를 비교한다. 이 과정을 반복하여 정렬하는 방식이 선택 정렬이..

지금 부터는 정렬에 대해서 공부하려고 한다. 정렬이란 말 그대로 데이터를 일정한 기준을 가지고 재배열하는 과정을 말한다. 정렬을 하는 방식에는 많은 방법이 존재하고 각각의 정렬 알고리즘마다 장/단점을 지니고 있다. 또한 정렬을 할 수 있는 많은 메서드들이 존재한다. 그러한 메서드들을 잘 활용하는것도 중요하겠지만, 그 동작 원리를 아는것 또한 굉장히 중요한 일이다. 대표적이고 일반적인 정렬 방식이 버블 정렬, 선택 정렬, 삽입 정렬이 있고 그 뒤로 효율성을 개선시킨 정렬 방식들이 있다. 버블 정렬, 선택 정렬, 삽입 정렬은 효율성이 떨어져 잘 사용되지는 않지만 특정 상황에서는 유용한 정렬방식일 수 있다. 7.1 버블 정렬 : 개요 버블 정렬은 흔히 사용되지는 않는다. 다른 정렬 알고리즘에 비해 비효율적이기..

6.1 선형 검색(선형 탐색) 오늘 공부한 내용은 검색 알고리즘에 대해서 공부했다. 검색 알고리즘이란 예를 들어 회원가입시 아이디가 중복되는 경우 중복된 아이디가 있는지 없는지 확인을 해야하는 경우 등 이러한 문제를 해결하기 위한 일련의 과정이 바로 검색 알고리즘이다. 우선 자바스크립트는 다양한 검색 관련 메서드들을 제공하고 있다. 1. indexOf : 메서드를 통해 배열내에 해당 요소가 있다면 해당 요소의 인덱스 번호를 반환해주고, 없다면 -1을 반환한다. 2. includes : 배열 내에 특정 요소가 포함되어 있는지 확인하여 불리언값을 반환한다. 3. find : 자신을 호출한 배열의 요소를 순회하면서 인수로 전달된 콜백 함수를 호출하여 반환값이 true인 첫 번째 요소를 반환한다. 4. find..

5.1 재귀함수를 사용하는 이유 우선 재귀라는것이 무엇일까? 모던 자바스크립트에서도 공부했듯이 재귀는 자기 자신을 호출하는 함수를 의미한다. 그렇다면 재귀를 왜 알아야 할까? 코드를 작성하는데 모든 곳에서 활용될 수 있기 때문이다. 우선 재귀를 이해하기 위해서는 '실행컨텍스트 스택'을 이해할 필요가 있다. 실행 컨텍스트는 이미 모던 자바스크립트에서 공부한적이 있다. 2022.07.20 - [언어 공부 및 정리/자바스크립트[모던자바스크립트]] - 23장 실행 컨텍스트 23장 실행 컨텍스트 실행 컨텍스트는 자바스크립트의 동작 원리를 담고 있는 핵심 개념이다. 이 개념을 명확하게 이해하면 자바스크립트가 스코프 기반으로 식별자와 식별자에 바인딩된 값을 관리하는 방식과 호 pinetree93.tistory.com..

4.1 대표적인 패턴들 문제 해결 접근법에 이어지는 내용으로 이제는 때때로 유용하게 사용할 수 있는 몇 가지 일반적인 패턴을 살펴보려 한다. 굉장히 많은 패턴들이 존재하지만 대표적인 패턴들만 살펴보자.(공식적인 이름이 붙은 패턴들도 있지만, 그렇지 않은 패턴들도 존재한다.) 1. Frequency Counter 빈도수 세기 패턴 (강사님이 직접 붙인 이름이다) 2. Multiple Pointers 다중 포인터 패턴 (강사님이 직접 붙인 이름이다) 3. Sliding Window 기준점 간 이동 배열 패턴 4. Divide and Conquer 분할과 정복 패턴 (공식적인 이름이다. 실제 자주 사용됨) 5. Greedy Algorithms 탐욕 알고리즘 패턴 (실제 자주 사용됨) 이 처럼 문제 해결에 유용..

3.1 알고리즘 정의 알고리즘이란? 특정 작업을 달성하기 위한 과정이나 일련의 단계를 의미한다. 그러므로 그 방법에는 다양한 방법이 존재한다. 알고리즘을 왜 알아야 할까? 바로 정의대로 문제를 해결할 방법을 마련할 수 있도록 결정하기 위해서다. 그렇다면 문제를 잘 해결하기 위해서는 어떻게 해야 할까?? 문제를 잘 해결하기 위해서는 모든 사람이 직관적으로 문제를 보자마자 원인을 파악하고, 가장 좋은 해결책을 생각해 낼 수 있다면 가장 좋을것이다. 그리고 그런 사람이 있다면 정말 부러울 것이다. 하지만 일반적으로는 쉽지 않기 때문에 일련의 전략을 구사하여 접근하는것이 좋은 방법일 수 있다. 다음은 문제를 잘 해결해 나가기 위한 전략적 접근 방법이다. 1단계 : 문제의 이해 2단계 : 구체적 예제 찾기 3단계..