1. 단일 연결 리스트 (Single Linked List) 연결 리스트란 데이터를 저장하는 자료구조로, 배열과 같이 순서에 따라 다수의 데이터를 담는다. 그러나 가장 큰 차이점이 있다면, 요소 각각의 인덱스가 존재하지 않는다. 튜플과 유사한 듯. 연결 리스트에서는 각각으 요소들을 노드(Node)라고 부른다. 각각의 노드는 문자열 혹은 숫자와 같은 하나의 데이터 엘리먼트를 저장한다. 추가로 다음 노드를 가리키는 정보(포인터, Pointer)를 저장하고 있어야 하며, 다음 노드가 더 이상 없을 경우 Null을 저장하게 된다. 연결 리스트에는 세 가지 속성이 존재하는데, 가장 앞단 노드인 헤드(Head), 말단 노드인 테일(Tail), 리스트의 길이(Length)를 통해 데이터를 관리한다. 인덱스가 존재하지..
앞서 학습한 버블정렬, 선택정렬, 삽입정렬, 합병정렬, 퀵정렬은 '비교 정렬' 그룹에 속함. 주어진 시간에 두 가지 요소를 비교하는 방식. 이러한 비교 정렬은 한계점이 존재하며, 최선의 경우 O(n log n)의 복잡도를 갖는다 (합병정렬, 퀵정렬) 기수정렬 (Radix Sort) 비교를 수행하지 않는 특별한 정렬 알고리즘으로, 숫자 크기에 대한 정보를 이진수로 인코딩하여 정렬한다. 작동방식 배열 요소의 0의 자리 수부터 분리한다. 모든 값들은 (0-9) 사이로 레이블링되고, 이를 0 레이블의 먼저 들어온 값부터 꺼내 배열한다. 자릿수를 좌측으로 옮겨가며 레이블링을 반복하면, 정렬이 완료된다. 헬퍼함수 1. getDigit(원하는 숫자 인덱스 찾기) : 원하는 숫자가 어느 자릿수 인덱스에 위치하는지 반환..
퀵 정렬 (Quick Sort) 기본적으로 배열 요소 갯수가 0이나 1개가 될 때까지 쪼개는 합병정렬과 유사하다. 여기서 피벗포인트라 부르는 단일 요소를 선택하여 수행하는 것이 차이점이다. 중앙점이 아닌, 이 피벗포인트를 기준으로 배열을 한 번 순회하여 기준보다 작은 수를 왼쪽 그룹으로, 큰 수를 오른쪽 그룹으로 이동시킨다. 로직을 이해하고 구현하는 데에 난이도가 좀 있는.. 알고리즘이다. 1. 피벗 헬퍼 앞선 합병정렬에서 합병로직을 먼저 구현했던 것처럼, 퀵정렬에서도 피벗 헬퍼를 통해 퀵정렬에 사용할 메서드를 모듈화해준다. 피벗 헬퍼는 주어진 배열 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치한다. 좌/우 배열 내의 정렬 여부는 당장 중요하지 않다. 피벗의 선택 기준 배열의 모든 요소 값들을 알..
앞서 배운 정렬 알고리즘들은.. (버블, 삽입, 선택) 작은 규모의 배열에서는 잘 작동하지만, 규모가 커질수록 잘 적용되지 않는다. 합병정렬 (Merge Sort) 0. 개요 배열을 더 작은 배열로 나누는 방식 (분할정복 알고리즘), 요소 배열이 0개나 1개가 될 때까지 반복 0개나 1개가 된 요소 배열 모음을 다시 병합함. 이 과정에서 정렬이 이루어짐. 예를 들어 8개의 원소를 가진 배열을 합병정렬하고자 한다면, 4 -> 2 -> 1개의 원소 그룹으로 나누고 1 -> 2 -> 4 -> 8개로 합치는 과정에서 정렬 1. 로직 구현 의사코드 정렬된 두 배열의 합병을 담당할 함수 구현. 입력 배열 두 개에 있는 모든 요소를 포함 초기값이 0인 I와 J 카운터를 두 배열에 각각 배치하여 While문을 통해 구..
선택정렬 큰 값을 배열 마지막 인덱스에 위치시키는 버블정렬과 달리, 작은 값을 한 번에 하나씩 위치시킨다. 기준 값과 나머지 원소들을 전부 순회하며 비교하여, 가장 작은 값과 자리를 바꾼다. 의사코드 최솟값 인덱스를 저장할 변수 필요. 초기값은 시작하는 기준 값과 동일하게 설정해주면 될 듯. 기준값부터 나머지 원소를 순회하며 최소값 인덱스를 갱신, 저장 기준값과 최소값 교환 원래 기준값 다음 인덱스부터 1,2,3 과정 반복 구현 function selectSort(arr) { for (var i = 0; i arr[minIdx]) { let tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } } return arr; } const arr = [4, 24,..
데이터를 정렬할 수 있는 방법은 무수히 많고, 각 알고리즘은 장단점을 갖고 있다. 같은 결과값을 갖더라도 결과를 내기까지의 과정이 제각기 다르다. 특정 상황에 유난히 잘 작동하는 정렬 방법이 존재하고, 이를 잘 활용하게 하기 위함 버블 정렬 자바스크립트 내장 정렬 메서드 array.sort() : num1 - num2 가 양수를 반환하면 num2가 앞에, 음수를 반환하면 num1이 앞에 온다. 숫자 뿐 아니라 문자열으 길이를 음수/양수로 구분하여 정렬할수도 있다. function numberCompare(num1,num2){ return num1 - num2; } [ 6, 4, 16,10 ].sort(numberCompare); 개념 현재 항목과 다음 항목을 한 번씩 비교하여 교환. 제일 끝에서부터 차례..
0. 검색 (Search) IndexOf 메서드 같은 배열 인덱싱, 문자열 파싱과 관련된 파트 내장함수의 처리 과정을 이해하고, 직접 구현하여 활용할 수 있게 하기 위함 1. 선형 검색 (Linear Search) 모든 개별 항목을 한 번씩 확인하는 방법 첫부분부터 끝부분으로 이동하며 탐색할수도, 역순으로 탐색할수도 있음 indexOf, includes, find, findIndex 메서드를 통해 선형 검색을 구현 기본적인 선형 검색 구현 function linearSearch(arr,value){ for (var i=0; i
0. 재귀 자기자신을 호출하는 절차 (함수) JSON()의 파싱이나, DOM getElementById 등의 내부 코드가 재귀로 구성되어 있음 물론 반복문만으로도 구현이 가능하지만, 재귀를 사용함으로써 직관적이고 간결하게 구현할 수 있음 1. 필수 요소 중단점 (Base Case) 재귀가 중단되는 시점, 즉 종료 조건과 마지막으로 반환할 Return을 지정해주어야 한다. 다른 입력값 (Different Input) 매번 같은 함수를 호출하면서 다른 출력을 반환할 수 있게 하기 위해선 입력값 또한 달라져야 한다. 2. 예시 예시 반복문을 이용한 팩토리얼 구현 function loopFactorial(num){ let total = 1; for(let i = num;i>0;i--){ total *= i } ..
지난 게시글 문제 해결 접근법과 이어지는 글입니다. 문제 해결 패턴 1. 빈도 카운터 (Frequency Counter) 자바스크립트 객체의 키-값 제어를 통해 다양한 값과 빈도를 수집 문제1 두 배열이 주어졌을 때, 한 배열 원소값들의 제곱을 담고 있는 다른 배열로 이루어진 경우 참을 반환하는 "Same" 함수를 작성하시오. (원소의 순서는 상관 없음) 해결1 이중 루프를 이용한 일반적인 해법, O(N^2) function same(arr1,arr2){ // 두 배열의 길이가 다른 경우 1차적으로 필터링 if(arr1.length !== arr2.length){ return false } for (let i=0;i
문제를 해결하기 위한 일련의 단계. 정답이 없음. 해답만이 존재할 뿐 문제 해결 접근법 0. 톺아보기 문제 이해 구제척 예시 탐색 문제 세분화 문제 해결 및 단순화 복기 및 재구성 1. 문제 이해 (Understand Problem) 코드를 입력하거나 보드에 작성하기 전 한 걸음 물러서서 직면한 과제를 확실히 이해하는 것. 당연하다고 들릴 수 있겠지만 굉장히 중요하다. 주어진 과제나 질문을 그대로 생각하는 게 아닌, 스스로의 방식으로 치환하여 이해하는 것 문제의 입력과, 내가 도출해내야 할 출력값은 무엇인가? 입력에 의해서만 출력값이 결정되는가? 문제 내부의 중요 데이터는 어떻게 레이블링하는가? 2. 구체적 사례 탐색 (Explore Examples) 앞선 문제 이해 과정을 마치고, 입력값과 출력값의 순..
