이진 탐색이란?정렬된 배열에서 특정 값을 찾을 때, 매번 탐색 범위를 반으로 줄여가며 효율적으로 찾는 알고리즘이다.배열: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]찾는 값: 71단계: 중간값 5와 비교 → 7 > 5, 오른쪽 범위로2단계: 중간값 8과 비교 → 7 선형 탐색이 O(n)인 반면, 이진 탐색은 O(log n)의 시간복잡도를 가진다. 동작 원리배열의 중간 값을 확인찾는 값과 중간 값을 비교같으면 → 탐색 성공크면 → 오른쪽 절반에서 탐색작으면 → 왼쪽 절반에서 탐색범위가 없어질 때까지 반복 장단점장점빠른 탐색 속도: O(log n)대용량 데이터에서도 효율적단점배열이 정렬되어 있어야 함삽입/삭제 후 재정렬 필요정렬되지 않은 데이터에는 사용 불가 구현재귀 방식function bina..

컴퓨터 과학에서 어떤 문제가 쉬운지 어려운지, 더 나아가 해결 가능한지 불가능한지를 판단하는 척도가 있다. 바로 P-NP 문제이다. P-NPP-NP는 컴퓨터 과학에서 어떤 문제가 쉬운 문제인지 어려운 문제인지, 더 나아가 해결이 가능한지 불가능한지를 판단하는 척도가 되는 개념이다.결정 문제와 최적화 문제먼저, 문제의 유형을 이해해야 한다.결정 문제 (Decision Problemn)어떤 문제가 주어졌을 때 yes 또는 no로 대답할 수 있는 문제를 말한다."이 배열이 정렬되어 있는가?" → Yes/No"이 그래프에서 A에서 B로 가는 경로가 존재하는가?" → Yes/No 최적화 문제 (Optimization Problem)어떤 상황이 주어졌을 때 최적의 해를 찾는 문제이다."배열을 정렬하라""가장 짧은 ..

같은 계산을 반복하는 것은 비효율적이다. 예를 들어 피보나치 수열에서 fib(5)를 계산할 때, fib(3)을 여러 번 중복 계산한다.한 번 계산한 결과를 저장해두면 훨씬 빠를 것이다.이것이 바로 동적 프로그래밍(Dynamic Programming)의 핵심 개념이다. 동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다.동적 프로그래밍은 크게 두 가지 방식으로 구현할 수 있다. 메모이제이션타뷸레이션방식하향식 (Top-down)상향식 (Bottom-up)구현재귀 + 캐싱반복문 + 테이블계산필요한 값만 계산모든 값을 미리 계산메모리스택 + 캐시 공간테이블 공간만문제: 피보나치 수열피..

책장에 있는 책들을 키 순서대로 정리한다고 생각해보자. 작은 책부터 큰 책 순서로 나열하는 방법은 여러 가지가 있다.어떤 방법은 간단하지만 느리고, 어떤 방법은 복잡하지만 빠르다. 이것이 바로 정렬 알고리즘이다.정렬 (Sort)정렬은 데이터를 특정 순서대로 배열하는 알고리즘이다.오름차순(작은 것부터 큰 것), 내림차순(큰 것부터 작은 것) 등 다양한 기준으로 정렬할 수 있다.정렬 알고리즘 비교 시간복잡도난이도특징버블 정렬 O(n²)쉬움인접한 원소를 교환선택 정렬 O(n²)쉬움최솟값을 찾아 교환삽입 정렬 O(n²)쉬움적절한 위치에 삽입병합 정렬 O(n log n)어려움분할 정복, 안정 정렬퀵 정렬 O(n log n) ~ O(n²)어려움분할 정복, 실정네서 빠름 버블 정렬 (Bubble Sort)인접한 두 ..

거울 앞에 거울을 놓으면 무한히 반복되는 모습을 볼 수 있다. 이처럼 자기 자신을 참조하는 것을 재귀라고 한다. 프로그래밍에서 재귀는 함수가 자기 자신을 호출하는 것을 의미한다. 재귀 (Recursion)재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 프로그래밍에서는 함수가 자기 자신을 호출하는 재귀 함수로 구현된다.재귀 함수의 필수 요소재귀 함수는 탈출 조건(기저 조건)이 없으면 무한히 자신을 호출하기 때문에, 결국 스택 메모리가 가득 차서 프로그램이 종료된다.(Stack Overflow). 따라서 재귀 함수에는 반드시 다음 두 가지가 필요하다. 설명기저 조건 (Base Case)재귀를 멈추는 조건재귀 호출 (Recursive Call)자기 자신을 호출하는 부분 간단한 재귀 함수 예시..

병합 정렬(Merge Sort)은 원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.이 과정은 재귀적으로 구현된다.동작 원리다음 숫자들을 오름차순으로 정렬해보자.7 4 5 2 6 3 8 1 1단계: 분할숫자들을 반으로 계속 나눈다.7 4 5 2 | 6 3 8 17 4 | 5 2 | 6 3 8 17 | 4 | 5 2 | 6 3 8 1 원소가 한 개가 될 때까지 나눈다.7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 2단계: 병합이제 작은 숫자가 먼저 오도록 병합한다.숫자 1개씩 병합:4 7 | 2 5 | 3 6 | 1 8 숫자 2개씩 병합:4 7과 2 5를 병합: 2와 4 비교 → 2, 4와 5 비교 → 4, 7과 5 비교 → 5, 7 남음2 4 5 7 | 1 3 6 ..

알고리즘을 구현할 때 동일한 작업을 반복해야 할 때가 있는데 이를 함수로 구현하면 코드를 효율적으로 만들 수 있다. 그렇다면 함수 내에서도 동일한 작업이 반복되는 경우는 어떻게 해야 할까?함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 알아보자.재귀란지금까지 우리는 main 안에서 프로그램을 작성하면서 필요한 순간에 함수를 호출했다. main도 함수이므로 함수 안에서 또 다른 함수를 사용한 것이다. 함수 안에서 다른 함수를 호출하는 것처럼, 자기 자신을 호출할 수도 있는데 이를 재귀(Recursion)라고 부른다. 반복문으로 피라미드 그리기피라미드 모양을 출력하는 코드다.#include #include void draw(int h);int main(void){ int height..

알고리즘 실행시간 비교실행시간의 상한O(n²): 선택 정렬, 버블 정렬O(n log n)O(n): 선형 검색O(log n): 이진 검색O(1) 실행시간의 하한 (개선 전)Ω(n²): 선택 정렬, 버블 정렬Ω(n log n)Ω(n)Ω(log n)Ω(1): 선형 검색, 이진 검색 샌프란시스코 대학교 컴퓨터 과학 부서의 비교 정렬 시각화 도구 버블 정렬 개선정렬이 모두 되어 있는 리스트가 주어진다면 어떨까? 원래의 의사 코드Repeat n-1 times For i from 0 to n-2 If i'th and i+1'th elements out of order Swap them실행시간의 하한: Ω(n²)문제: 이미 정렬되어 ..

정렬된 배열이 정렬되지 않은 배열보다 탐색하기 쉽다. 선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 찾아 첫 번째 위치의 값과 교환하는 방식의 정렬이다.교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.동작 원리정렬되지 않은 숫자들을 오름차순으로 정렬해보자.6 3 8 5 2 7 4 11단계:가장 작은 값인 1을 찾는다첫 번째 값인 6과 교환한다결과: 1 3 8 5 2 7 4 62단계:정렬된 1을 제외하고 두 번째부터 가장 작은 값을 찾는다가장 작은 값인 2를 두 번째 값인 3과 교환한다결과: 1 2 8 5 3 7 4 63단계 이후:이 과정을 더 이상 교환이 일어나지 않을 때까지 반복한다최종 결과: 1 2 3 4 5 6 7 8의사 코드:For i from 0 to n-1 ..

정렬되지 않은 배열을 탐색하는 것보다 정렬 후 탐색하는 것이 더 효율적이다.정렬 알고리즘은 여러 가지가 있으며 각각 실행 시간이 다르다. 그중 버블 정렬에 대해 배워보자. 버블 정렬(Bubble Sort)은 두 개의 인접한 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 단 두 개의 요소만 정렬하는 좁은 범위의 정렬에 집중한다. 이 접근법은 간단하지만 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있다. 동작 원리8개의 숫자가 임의의 순서로 나열되어 있다.6 3 8 5 2 7 4 1 오름차순으로 정렬해보자.1. 가장 앞의 6과 3을 비교해 순서를 바꾼다. 2. 6과 8은 순서가 맞으므로 그대로 둔다. 8과 5를 비교해 순서를 바꾼다. 3. 이 과정을 끝까지 수행하면 다음과..