백엔드 개발 한 걸음

https://www.google.com/search?gs_ssp=eJzj4tVP1zc0zC0rqbJMSs82YPRSezN3y6tNzUBS4c3eKa-nrHzb2vOma8nbrh2vu5covO3pAcq86V0DAPVSHyQ&q=%EC%9D%B4%EA%B2%83%EC%9D%B4+%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4+%ED%8C%8C%EC%9D%B4%EC%8D%AC&oq=%EC%9D%B4%EA%B2%83%EC%9D%B4+%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4+%ED%8C%8C%EC%9D%B4%EC%8D%AC&gs_lcrp=EgZjaHJvbWUqBwgBEC4YgAQyCggAEAAY4wIYgA..

원형연결리스트는 말 그대로 연결리스트가 원형 형태로 이루어진 것으로, 가장 큰 특징으로는 마지막 노드와 첫 번째 노드가 만난다는 점이다. 이러한 원형의 특징을 가졌기에 원형연결리스트, 다른 말로 순환연결리스트라고도 부른다. 이 원형 연결리스트는 시작과 끝이 없기 때문에 헤드 포인터를 설정해주지 않으면 무한히 순환할 수 있다. 그래서 이 부분에 주의해야 한다. 원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있다. 구현 코드에 주석을 달아놓았으니 이해하기 어렵지 않을 것이다. # 노드를 정의하며, # 각 노드는 데이터 (data)와 다음 노드를 가리키는 링크 (link)를 포함함 class ListNode: def __init__(self, data): self.data ..

정의 : 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 핵심은 노드와 노드가 서로 연결되어 있다는 점이다. 아래 그림을 보면 단순 연결 리스트(linked list)와는 다르게 노드가 이전 노드(previous)와 다음 노드(next)로 구성되어 있다. 이것의 가장 큰 장점은 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다는 것이다. 삽입 구현 과정 다음과 같이 head와 tail 노드만 존재하고 있을 때, 새로운 데이터를 가진 노드(new)를 넣고 싶다면 1. tail의 Llink가 가리키는 노드의 Rlink가 new를 가리키게 한다. (tail->Rlink->Rlink = new) 2. newnode의 Llink를 tail의 Llink가 기리키는 ..

정의 Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. Process 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정..

Merge Sort 💡 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘 중 하나 작동 원리 분할(Divide): 주어진 배열을 절반으로 나눕니다. 이 분할 과정은 원소가 하나만 남을 때까지 재귀적으로 계속됩니다. 정복(Conquer): 분할된 작은 문제들을 해결합니다. 병합 정렬에서 이 단계는 원소가 하나만 있는 배열이므로 이미 정렬된 상태입니다. 병합(Merge): 정렬된 두 개의 부분 배열을 하나의 정렬된 배열로 병합합니다. 이 과정은 재귀적으로 수행되며, 전체 배열이 정렬될 때까지 계속됩니다. 시간 복잡도 최선, 평균, 최악의 경우 모두: O(nlogn) 공간 복잡도 O(n) (추가적인 메모리 공간이 필요합니다.) 장단점 장점 ..

퀵 정렬 (Quick Sort) 💡 퀵 정렬(Quick Sort)은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용하여 배열을 정렬합니다. 작동 원리 배열에서 하나의 원소를 선택합니다. 이 원소를 '피벗(pivot)'이라고 합니다. 피벗을 기준으로 배열을 두 부분으로 나눕니다: 피벗보다 작은 원소들의 부분 배열과 피벗보다 큰 원소들의 부분 배열. 각 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 모든 부분 배열이 원소 하나만을 가질 때까지 위의 과정을 반복합니다. 시간 복잡도 최선의 경우와 평균적인 경우: O(nlogn) 최악의 경우: O(n2) (이미 정렬된 배열이나 역순으로 정렬된 배열에서 피벗 선택이 잘못될 경우) 공간 복잡도 평균적인 경우: O(..

삽입 정렬 (Insertion Sort) 💡 삽입 정렬(Insertion Sort)은 카드를 정렬하는 방법에 비유될 수 있는 정렬 알고리즘입니다. 이 알고리즘은 각 숫자를 적절한 위치에 "삽입"함으로써 작동합니다. 작동 원리 http://algorithm.wiki/ko/app/ 두 번째 원소부터 시작하여 현재 원소를 "임시 변수"에 저장한다. 이전 원소들과 비교하면서 적절한 위치를 찾아간다. 현재 원소가 이전 원소보다 작으면, 이전 원소를 한 칸 뒤로 이동한다. 임시 변수에 저장한 원소를 적절한 위치에 삽입한다. 위의 과정을 배열의 마지막 원소까지 반복한다. 시간 복잡도 최선의 경우: O(n) (이미 정렬된 배열에서) 평균적인 경우: O(n2) 최악의 경우: O(n2) 공간 복잡도 O(1) (in-pla..

선택 정렬 (Selection Sort) 💡 선택 정렬(Selection Sort)은 배열 내에서 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞의 원소와 교환하는 방식을 사용하는 정렬 알고리즘입니다. 작동 원리 http://algorithm.wiki/ko/app/ 배열에서 현재 위치를 제외한 나머지 원소 중에서 가장 작은 원소를 찾는다. 찾아진 가장 작은 원소와 현재 위치의 원소를 교환한다. 현재 위치를 한 칸 앞으로 이동하고, 배열의 끝까지 위의 과정을 반복한다. 시간 복잡도 최선의 경우: O(n2) 평균적인 경우: O(n2) 최악의 경우: O(n2) 공간 복잡도 O(1) (in-place 정렬) 장단점 장점 구현이 간단하며, 공간 복잡도가 작다. 데이터의 양이 작을 때는 효율적일 수 있다. 단점 데이..

정의 가장 간단한 정렬 알고리즘 중 하나로, 이름에서 알 수 있듯이 "버블"처럼 큰 값이 배열의 끝으로, 작은 값이 배열의 시작으로 이동하게 다. 이 알고리즘의 기본 아이디어는 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하는 것 과정 첫 번째 원소부터 마지막 원소까지 반복하면서 인접한 두 원소를 비교한다. 두 원소의 순서가 잘못되어 있다면(즉, 오름차순 정렬에서 첫 번째 원소가 두 번째 원소보다 크다면) 위치를 교환한다. 1~2의 과정을 배열의 끝까지 반복한다. 이렇게 하면 가장 큰 원소가 배열의 마지막 위치로 이동한다. 배열의 길이를 1 줄이고 위의 과정을 반복한다. 배열의 길이가 1이 될 때까지 위의 과정을 반복한다. 시간 복잡도 최선의 경우: O(n) (이미 정렬된 배열) 평균적인 경우: O..

해쉬란? 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조 key : value의 형태를 갖는 자료구조 ex)전화번호부 (이름 : 전화번호) (검색어 : 검색결과) 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 모든 데이터 타입으로 접근 가능 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다. 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다. 파이썬 터미널로 작성해보면, 이미 해쉬 함수가 제공되고 있음을 알 수 있음 >>> hash("fast") -146084012848775433 >>> hash("slow..