알고리즘과 자료구조 (19) 썸네일형 리스트형 [자료구조] 단일 연결 리스트에서 특정 노드를 제거하는 함수를 구현해보자 이전 시간까지 단일 연결 리스트에서 노드를 찾아서 조회하는 기능을 구현하였는데, 이번에는 타겟이 되는 노드를 검색해서 삭제하는 기능을 구현해볼 것이다. 단일 연결리스트에서 특정 노드를 삭제하려면 단일 연결리스트에서 특정 노드를 삭제하려면 우선적으로 연결 리스트 전체를 순회해야 한다. 왜냐 하면, 단일 연결리스트의 참조는 단방향이기 때문에 전체 노드를 순회해야 타겟 노드를 찾을 수 있기 때문이다. 또한, 타겟이 되는 노드를 제거하기만 하면 되는 것은 아니며, 타겟 노드를 이전 노드가 가리키는 다음 노드의 참조를 타겟 노드의 다음 노드에 해당하는 노드로 변경해주어야 한다. 예를 들어 5 -> 3 -> 1 이라는 연결리스트가 있다고 가정할 때, 2 라는 노드를 제거한다면 5 -> null -> 1 와 같은 형.. [자료구조] 단일 연결 리스트 | search 구현하기.sub | Index 를 사용하여 노드 찾기 [자료구조] 단일 연결 리스트 | Add 구현하기(2). sub | 뒤로 노드 추가하기 [ 자료구조] 단일 연결 리스트 - Add 구현하기[1]. sub | 노드를 앞으로 추가하기 단일 연결 리스트란? 단일 연결 리스트는 리스트의 각 요소가 다음 요소를 가리키는 연결 리스트의 한 유형이다. 리 duklook.tistory.com 단일 연결 리스트에서 search 단일 연결 리스트에서 타겟이 되는 노드를 찾는 search 메소드를 구현하는 방법은 다양하다. 실제 head 에 저장된 데이터(data)와 사용자가 입력한 값(target)이 일치하는 경우 true 혹은 false 를 반환하거나 해당 노드의 인덱스를 반환하게 할 수 있고, 아니면 오늘 구현해볼 방법인 인덱스를 기반으로 해당하는 인덱스에 위치한 요.. [자료구조] 단일 연결 리스트 | Add 구현하기(2). sub | 뒤로 노드 추가하기 [ 자료구조] 단일 연결 리스트 - Add 구현하기[1]. sub | 노드를 앞으로 추가하기 단일 연결 리스트란? 단일 연결 리스트는 리스트의 각 요소가 다음 요소를 가리키는 연결 리스트의 한 유형이다. 리스트는 노드를 요소로 가지고 있으며, 각 노드에는 데이터(data)와 다음 노드를 duklook.tistory.com 이전 시간에는 단일 연결 리스트에 노드를 추가하는 방법 중 노드를 앞으로 추가하는 함수에 대해서 정리해 보았는데, 오늘은 그 반대이자 일반적인 방식인 노드를 뒤로 추가하는 방식에 대해 정리하고자 한다. 노드를 뒤로 추가하는 add 함수 노드를 앞으로 추가하는 방법은 앞에서 알아 봤듯이 새로운 노드가 이전 노드를 참조하게 하는 방식으로 꼬리에 꼬리를 물도록 설계하는 것 이었다. add(d.. [ 자료구조] 단일 연결 리스트 - Add 구현하기[1]. sub | 노드를 앞으로 추가해보자 단일 연결 리스트란? 단일 연결 리스트는 리스트의 각 요소가 다음 요소를 가리키는 연결 리스트의 한 유형이다. 리스트는 노드를 요소로 가지고 있으며, 각 노드에는 데이터(data)와 다음 노드를 가리키는 참조(next) 를 담고 있다. 리스트에서 첫 번째 노드를 헤드(head)라 부르며, 마지막 노드는 null 에 대한 참조 담는다. 마지막 노드가 null 을 담고 있는 것은 [1 -> 2 -> 3] 이 있을 때 3을 담고 있는 노드의 다음 노드는 없기 때문이다. 단일 연결 리스트는 단방향 이므로 이전 노드에 대한 참조를 알지 못하는 것이 특징이다. 즉, 앞만 보거나, 뒤만 보거나 둘 중 하나의 방향만 가리킨다. 단일 연결 리스트의 시간 복잡도 단일 연결 리스트는 특정 위치의 노드에 직접 접근하려면 처음.. [알고리즘] 퀵 정렬 알고리즘 With JS 퀵 정렬 이 알고리즘은 먼저 배열의 한 요소를 피벗(pivot)으로 선택한 후, 피벗보다 작은 요소는 모두 피벗의 왼쪽에 위치하도록, 피벗보다 큰 요소는 모두 피벗의 오른쪽에 위치하도록 배열을 분할합니다. 그 다음, 분할된 두 하위 배열을 각각 재귀적으로 퀵 정렬을 수행하여 정렬을 완료합니다. 이 알고리즘의 핵심 아이디어는 분할(Divide) 단계에서 피벗을 기준으로 배열을 분할하여 정복(Conquer) 단계에서 각 하위 배열을 정렬하는 것입니다. 이 과정을 반복하여 분할된 배열이 더 이상 분할되지 않을 때까지 정렬을 수행합니다. 피벗 요소를 기준으로 해당 요소보다 작은 요소는 좌측으로, 큰 요소를 우측으로 분할하여, 배열을 분할한다. 그 후 분할 된 배열 내에서 재귀적 퀵 정렬(퀵 정렬 함수를 다시 호.. [알고리즘] 합병정렬 알고리즘(분할과 정복 알고리즘 유형 중 하나) With JS 합병정렬 알고리즘 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 배열을 반으로 나누어 각각을 재귀적으로 정렬하고, 그 결과를 합쳐서 정렬된 배열을 생성하는 알고리즘입니다. * 분할과 정복 알고리즘의 원리 접은 글 내에 글자 중복이 있습니다. 중복된 부뷰이 지우고 수정한 부분이었는데, 수정 시에는 안 보이는데 등록 후에는 보이는 이상한 버그가 있네요더보기 분할 정복 알고리즘의 일반적인 구조는 다음과 같습니다. 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복(Conquer) : 각각의 작은 문제를 동일한 방법으로 순환적으로 해결 합병(Combine) : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함 합병정렬도 위 구조에 따라, 배열을 분할하고.. [알고리즘] 삽입 정렬 with JS 삽입 정렬 배열의 요소들을 순차적으로 검사하면서 해당 요소가 들어갈 위치를 찾아 삽입하는 정렬 알고리즘입니다. 간단하게 설명하면, 첫 번째 요소는 이미 정렬되었다고 가정하고, 두 번째 요소(i)부터 시작하여 앞의 요소(j-1)들과 비교하면서 자신의 위치를 찾아 삽입하는 방식으로 정렬을 수행합니다. 즉, 배열을 순회할 때 마다 j= j-1 혹은 j-- 를 반복함으로써 정렬 대상인 key 요소와 j-1 요소 간의 크기 비교를 통해 key = 0 && arr[j] > key) { // j+1번째 인덱스에 j번째 인덱스의 값을 할당합니다. arr[j + 1] = arr[j]; // j를 감소시켜 while 문을 반복하여 key가 들어갈 위치를 찾습니다. // 만일 j 가 -1이 되면 즉시 while을 탈출합니다.. [알고리즘] 선택 정렬 with JS 선택정렬(Selection sort) 배열에서 가장 작은 값을 찾아서 배열의 맨 앞에 위치시키고, 그 다음 작은 값을 찾아서 두 번째 위치에 위치시키는 방식으로 정렬하는 알고리즘 입니다. 선택정렬 실행 과정 배열의 첫 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다. 가장 작은 값과 배열의 첫 번째 원소를 교환합니다. 배열의 두 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다. 가장 작은 값과 배열의 두 번째 원소를 교환합니다. 위의 과정을 반복해서 전체 배열이 정렬될 때까지 반복합니다. 선택정렬 코드 function selectionSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let minIndex = i; for (le.. 이전 1 2 3 다음
