순차 탐색(Sequential Search)리스트의 처음부터 끝까지 차례대로 탐색하면서 원하는 데이터를 찾는 가장 기본적인 알고리즘입니다.(탐색: 여러 데이터 중에서 원하는 데이터를 찾아내는 것) 순차 탐색 알고리즘 동작 방식첫 번째 원소부터 탐색 시작현재 원소가 찾고자 하는 값과 같은지 비교같으면 해당 인덱스를 반환끝까지 탐색해도 없으면 -1 반환순차 탐색의 시간 복잡도최선의 경우: `O(1)` (첫 번째 요소가 찾는 값일 때)최악의 경우: `O(n)` (리스트 끝까지 탐색)평균적인 경우: `O(n)` 프로그래밍 연습임의 리스트가 다음과 같이 `randDataList`로 있을 때원하는 데이터의 위치를 리턴하는 순차 탐색 알고리즘 작성해 보기(원하는 데이터가 없을 경우 `-1` 리턴)import java..

병합 정렬(Merge sort)재귀 용법과 분할 정복 알고리즘을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 분할각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬두 부분 리스트를 다시 하나의 정렬된 리스트로 합병 VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only payment that we ask of you is for you to tell the existence of VisuAlgo to oth..

퀵 정렬(Quick sort)퀵 정렬은 데이터를 정렬할 때기준값(피벗)을 하나 정하고 나머지 데이터를 작은 값(left)과 큰 값(right)으로 나눈 다음이 두 그룹을 재귀적으로 정렬하는 방식입니다. 과정:기준점(pivot)을 정해서기준점보다 작은 데이터는 왼쪽큰 데이터는 오른쪽으로 모으는 함수가 필요각 왼쪽, 오른쪽은 재귀 호출을 통해 위 작업을 반복함함수는 [왼쪽] + 기준점 + [오른쪽]을 리턴함 동작 과정 예시:예시: `[5, 3, 8, 4, 2, 7, 1, 6]` 피벗 선택: 리스트의 첫 번째 값 5를 피벗으로 선택분할:피벗보다 작은 값 → `[3, 4, 2, 1]`피벗보다 큰 값 → `[8, 7, 6]`재귀 정렬:`[3, 4, 2, 1]` → 다시 퀵 정렬`[8, 7, 6]` → 다시 퀵 정..

동적 계획법(Dynamic Programming, DP)작은 부분 문제들을 해결한 후 해당 부분 문제들의 해를 활용하여 보다 큰 부분 문제를 해결하면서 최종적으로 전체 문제를 해결하는 알고리즘「상향식 접근법」으로 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Memoization 기법을 사용함Memoization(메모이제이션)이란?: 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨예: 피보나치 수열 분할 정복(Divide and Conquer)문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘「하향식 접근법」으..

** 재귀 용법(Recursive Call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 ** 예제 팩토리얼을 구하는 알고리즘 분석: 규칙이 보임 n! = n * (n-1)! def factorial(num): if num > 1: return num * factorial(num - 1) else: return num ** 예제: 시간 복잡도와 공간 복잡도 factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함 일종의 n-1번 반복문을 호출한 것과 동일 factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n) ** 재귀 호출의 일반적인 형태 # 일반적인 형태1 def functi..

삽입 정렬(Insertion sort)리스트를 왼쪽부터 차례대로 보면서현재 요소를 그 앞쪽의 정렬된 구간에 적절한 위치에 '삽입'하는 방식즉 하나씩 꺼내서 앞에서부터 위치를 찾아 넣는 방식이라서 삽입 정렬이라고 불립니다. 과정두 번째 요소부터 시작해요. 이 값을 key라고 부를게요.key의 왼쪽에 있는 값들을 하나씩 거꾸로 보면서key보다 큰 값이 있다면 한 칸씩 뒤로 밀어요.이렇게 하다 보면 key보다 작거나 같은 값을 만나게 되는데그 바로 뒤에 key를 넣으면 돼요.이 과정을 리스트 끝까지 반복하면 정렬이 완료됩니다. 동작 과정 예시정렬할 리스트: `[5, 3, 4, 1, 2]` `i = 1`, 3은 5보다 작다 → swap → `[3, 5, 4, 1, 2]``i = 2`, 4는 5보다 작다 → sw..