'👩‍💻 프로그래밍/🎐 알고리즘' 카테고리의 글 목록 (3 Page)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 왼쪽에는 정렬이 끝난 수가 오게되고, 오른쪽에는 아직 확인하지 않은 숫자가 남게 되는데, 오른쪽 미탐색 영역에서 숫자를 하나 꺼내어 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식 이미 정렬이 되어있다면 필요없이 종료한다. InsertionSort(A[ ], n) { for (i=1; i 0 && A..

버블 정렬(Bubble Sort)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 왼쪽에서 오른쪽 방향으로 인접한 두 개의 숫자를 비교해 교환하여 정렬 오름차순으로 정렬될 때까지 다시 돌아와 반복한다. 반대 방향으로도 가능 BubbleSort(A[ ], n) { for (i=0; i A[j+1]) // ‘왼쪽 데이터 >오른쪽 데이터’이면 A[j]와 A[j+1]의 자리바꿈; return (A); } 🟩 시간 복잡도 for문 i (외부 반복문) : 0 ~ (n-2) 👉 (n-1)회 for문 j (내부 반복문) : 동일 👉 (n-1)회 총 비교 횟수 = O(n^2) 🟩 성능 선택 정렬에 비해 데이터 교환이 많이 발생. 선택 정렬보다 비효..

선택 정렬(Selection Sort)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 입력 배열에서 가장 작은 값부터 순서대로 '선택'해서 나열하는 방식 수열 중에서 최솟값을 찾아 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다. 최솟값을 찾을 때는 선형 탐색을 사용 SelectionSort(A[ ], n) { for (i=0; i A[j]) min = j; A[i]와 A[min]의 자리바꿈; // ②최소값과 A[i]의 위치 교환 } return (A); } 🟩 시간복잡도 총 비교횟수 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 👉 O(n^2) 루프i 0 1 2 ... n-2 루프j의 비교횟수 n..

재귀(순환) 알고리즘

2024.03.27· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며, 그 반대도 가능하다. 재귀 함수를 작성할 때는 함수 내에서 다시 자기 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함 되어야한다는 부분을 인지하고 작성하면 무한루프를 방지 가능 🟩 for, while문 등 반복문과 비교하면 처리에 시간이 오래 걸리고 메모리 소모를 많이 한다. 스마트하게 프로그램을 작성할 수 있을 때만 사용해야 하는 기법 🌟 예1. 카운트다운 🌟 예2. 구구단 출력 🌟 예3. 팩토리얼 #include int factorial(int n) { printf("factorial(%d)가 호..

동적 계획법(dynamic programming) feat. 피보나치 수열

2024.03.27· 👩‍💻 프로그래밍/🎐 알고리즘

분할한 문제의 답을 기억해 두고, 이를 재사용함으로써 같은 문제를 여러 번 푸는 낭비를 방지한다는 프로그래밍 기법상향식 접근방법 🟩 특징각 소문제는 원래 주어진 문제와 동일한 문제 👉 입력 크기만 작아진 문제소문제들은 서로 독립일 필요없다.해를 구축하는데 테이블을 사용한다. 최솟값/최댓값을 구하는 최적화 문제에 주로 사용"최적성의 원리"를 반드시 만족하는 문제에만 적용 가능하다.주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다. 🟩 처리 과정1. 최적성의 원리가 주어진 문제에 성립하는 지 확인2. 주어진 문제에 대해서 최적해를 제공한느 점화식 도출3. 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장4. 테이블에 저장된 소문제의 해를 이용하여 점차적으로 입..

분할정복 알고리즘

2024.03.27· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후, 이들의 해를 결합하여 원래 문제의 해를 구하는 방식 🟩 분할된 작은 문제는 원래 문제와 동일하다. 입력의 크기만 작아진다. 🟩 분할된 문제는 서로 독립적이다. 순환적인 분할 및 결과 결합이 가능하다. 🚀 활용1 정렬 : 합병정렬, 퀵정렬 🚀 활용2 탐색 : 이진탐색

그리디 알고리즘 (탐욕 알고리즘)

2024.03.27· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 매 순간에서 지금 이 순간 당장 최선의 답을 선택해 적합한 결과를 도출하자! = 간단하면서 효율적인 알고리즘을 만들 수 있는 강력한 기법 최솟값/최댓값을 구하는 최적화 문제에 주로 사용 각 단계마다 선책한 최적의 해가 전체적인 최적의 해가 되지 않을 수 있다! 🚀 활용1 거스름돈 문제, 배낭 문제 배낭 문제 #include // 배낭의 최대 무게 #define KNAP_MAX 6 // 물건의 종류 #define ITEM_NUM 5 // 물건의 명칭 char name[] = { 'A', 'B', 'C', 'D', 'E' }; // 물건의 무게 int weight[] = { 1, 2, 3, 4, 5 }; // 물건의 가치 int value[] = { 100, 300, 350, 500, 650 }; // ..

선형 검색 (보초법)

2024.01.06· 👩‍💻 프로그래밍/🎐 알고리즘

선형 검색 임의의 배열에서 원하는 데이터를 찾는 알고리즘 '임의의'인 이유는 크기 순서대로 정렬된 배열이라면 '이진 검색'을 사용하는 것이 낫다. 순서 무작위. 배열의 앞에서부터 데이터를 확인한다. 계산 시간은 O(n) 예) 지정한 값과 배열의 값이 같을 경우 종료. 배열에 같은 값이 중복으로 있을 경우에도, 처음 발견된 시점에 종료한다. x=68인 경우, '1' 원하는 값이 발견되지 않은 경우 '-1'을 표시한다. -1은 인덱스로 사용할 수 없는 값이기 때문 #include #define LENGTH 10 int main(void) { int x = 0; int pos = -1; int a[] = { 72, 68, 92, 88, 41, 53, 97, 84, 39, 55 }; printf("입력할 숫자 ..

하노이의 탑

2024.01.06· 👩‍💻 프로그래밍/🎐 알고리즘

n+1개의 탑을 이동하려 할 때, 가장 큰 원반을 무시하고, n개를 b로 이동 시킨다. 가장 큰 원반을 c로 이동시킨 뒤 이동시키면 된다. 처음에 b로 n개의 탑을 이동시킬 때, c와 나누어서 이동시켜야 하기 때문에 계산적으로 해야한다. n개 탑 문제는 n-1 탑 문제를 활용하면 되고, n-1은 n-2를 활용하면 되기 때문에 재귀적 알고리즘이다. 계산 시간 n-1개를 A에서 B로 이동시킬 때, n-1 가장 큰 원반을 C로 이동시킬 때, 1 B에 있는 n-1개를 C로 이동시킬 때, n-1이 필요하므로 T(n) = 2T(n-1) + 1 = 2^n - 1

소수 판별법(페르마 테스트)

2024.01.06· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 소수는 1과 자신 이외는 약수로 가지지 않는 1보다 큰 자연수이다. 🟩 페르마 테스트 = 확률적 소수 판별법 어떤 수가 '소수일 가능성이 높은지'를 판별하는 것 1. 해당 수보다 작은 수를 해당 수만큼 제곱한다. 예)5 -> 1^5 ~ 4^5 2. 각각의 숫자를 mod 연산을 이용해 해당 수로 나눈다. 예) 1^5 = 1 mod 5 = 1 3. 원래 수와 나머지 값이 모두 일치하면, 소수이다. 페르마의 소정리를 만족하는지를 소수 판별을 하는 방법이 '페르마 테스트' 일치하는지 확인하는 횟수를 늘릴수록 소수일 확실성이 높아진다. 단 p보다 작은 모든 수를 확인하려면 매우 오랜 시간이 걸린다. 실제로는 몇 개의 수만 확인해서 소수일 가능성이 매우 높다고 판단할 수 있으면 '아마도 소수'라고 판정하고 있다..

시간복잡도

2024.01.03· 👩‍💻 프로그래밍/🎐 알고리즘

알고리즘 효율성 분석 1. 공간 복잡도 메모리의 양 = 정적 공간 + 동적 공간 2. 시간 복잡도 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간 = 각 문장(연산)이 수행되는 횟수 👉 입력 크기 (데이터의 갯수) 예) 리스트의 원소 개수, 행렬 크기, 그래프 정점의 수 👉 입력 데이터의 상태 점근성능 : 데이터의 값 n이 무한히 커짐에 따라 결정되는 성능 시간복잡도 구하기 알고리즘의 모든 문장이 아닌 루프의 반복 횟수만을 조사하여 최고 차수를 시간 복잡도로 취함

알고리즘이란 (feat 유클리드 호제법) | 코딩테스트 전에 알면 좋은 것들

2024.01.02· 👩‍💻 프로그래밍/🎐 알고리즘

'수'에 대한 '문제를 푸는 방법' 컴퓨어 분야에서는 '공식화된', '단계적'이라는 조건 애매모호하며 언제 끝날지 모르는 절차는 알고리즘으로 부를 수 없다. 유클리드 호제법 두 정수의 최대공약수를 구하는 알고리즘 1. 두 정수의 큰 쪽 - 작은 쪽, 양쪽이 같아질 때까지 반복한다. 2. 같아진 값이 최대공약수가 된다. 예) 50과 30의 최대공약수 = 10 30 30 30-20=10 10 50 50-30=20 20 20-10=10 cf. 나머지로 최대공약수 구하기 더보기 큰 쪽에서 작은 쪽은 나눈 나머지를 계속 구한다. 나머지 값이 0이 되는 몫을 최대공약수라 한다. 예) 50과 15의 최대공약수 = 5 1. 15 50 % 15 = 5 (50 -> 5) 2. 5 15 % 5 ..

티스토리툴바