🏖️ jcowwk's study

정렬1. 버블 정렬2. 선택 정렬3. 삽입 정렬4. 병합 정렬5. 퀵 정렬6. 힙 정렬1. 버블 정렬인접한 두 개의 값을 비교하여 큰 값을 뒤로 보내는 방식으로 정렬 - 동작 과정1. 배열을 처음부터 끝까지 순회하며 인접한 두 요소를 비교2. 앞 요소가 뒤 요소보다 크다면 위치 교환3. 한 번의 순회가 끝나면 가장 큰 값이 배열의 끝으로 이동4. 이를 배열이 정렬될 때까지 반복 - 코드 구현void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; ..

LIS와 LCS1. LIS2. LCS1. LISLIS(Longest Increasing Subsequence)는 최장 증가 부분 수열입니다.주어진 수열에서 원소들의 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 10, 20, 10, 30, 20, 50 수열에서 LIS는 10, 20, 30, 50 입니다.이를 찾는 방법은 동적 계획법과 이분 탐색+DP가 있습니다. 2. LCSLCS(Longest Common Subsequence)는 최장 공통 부분 수열입니다.두 개의 문자열에서 순서를 유지하면서 가장 긴 공통 부분 수열을 찾는 문제입니다. 문자열 A: ABCD 과 문자열 B: ACBD 에서 LCS는 ABD 또는 ACD 입니다.이를 찾는 방법은 동적 계획법과 메모이제이션이 있습니다.문제..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)1. 깊이 우선 탐색(DFS)2. 너비 우선 탐색(BFS)3. 최적 경로와 최단 경로 차이1. 깊이 우선 탐색(DFS)한 방향으로 끝까지 탐색한 후, 되돌아가면서 다른 경로를 탐색하며 최적 경로를 찾는 알고리즘입니다.최적 경로는 여러 조건을 고려하여 가장 적합한 경로를 찾는 것입니다.서울에서 부산까지의 거리만 짧은 것이 아닌 교통 체증, 고속도로 톨게이트 비용 등을 고려하여 길을 찾을 때 사용됩니다. 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘에서 사용됩니다. - 동작 과정1. 시작 노드를 방문하고 스택에 넣음 (또는 재귀 호출)2. 현재 노드에서 갈 수 있는 노드를 방문3. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아감4. 모든 노드를 반복할 ..

Knapsack 알고리즘 - C언어1. Knapsack 알고리즘2. 코드 구현 알고리즘 복습하기 위해 포스팅 하고 있습니다.1. Knapsack 알고리즘배낭 문제(Knapsack Problem)은 제한된 용량을 가진 가방에 여러 개의 물건을 넣을 때, 가치의 합이 최대가 되도록 하는 최적화 문제입니다. 배낭 문제의 종류에는 0/1 배낭 문제(DP)와 분할 가능 배낭 문제(그리디 알고리즘으로 해결 가능)가 있습니다. 해당 포스팅에서는 그리디 알고리즘를 다뤄보겠습니다. 2. 코드 구현- 전체 코드#include #include typedef struct Bag { int value; int weight; float ratio;} Bag;int compare(const void *a, co..