알고리즘이란 무엇인가
> 프로그래밍을 배우고 다양한 문제를 접하면서 간단한 알고리즘만 안다면 훨씬 더 쉽게 해결하는 경우가 있었기 때문에 한 번에 깊게는 아니더라도 차근차근 공부를 하다보면 보다 더 유용하게 다양한 범위에서 사용할 수 있을 것 같다.
- 알고리즘이란 ?
> 알고리즘이란 주어진 문제를 해결하기 위한 명확하고 정확한 절차나 규칙, 방법 등을 체계적으로 나열한 것.
> 프로그래밍에서 알고리즘은 특정 작업을 수행하거나 문제를 해결하기 위해 컴퓨터에게 지시하는 단계별 명령의 집합.
> 기본적인 정의를 넘어, 생각의 표현, 아이디어의 구현, 그리고 복잡성을 단순화하는 방법이라고 할 수 있따.
> 일상생활 속의 예를 들자면 조리법은 재료를 특정한 결과물인 완성된 요리로 변환하는 알고리즘이고 집으로 오는 길을 설명할 때, 사실상 경로를 찾는 알고리즘을 제공하는 것이다.
- 알고리즘의 중요성
> 프로그램의 효율성과 성능을 결정짓는 핵심 요소
> 복잡한 문제를 단순화하고 해결 과정을 명확하게 한다.
> 소프트웨어 개발에서 예측 가능성과 재사용성을 높인다.
알고리즘의 특성
- 입력 ( Input ) : 외부에서 제공되는 자료
- 하나 이상의 명확하게 정의된 입력을 가지고 있어야 한다. 입력은 알고리즘의 작동에 필요한 데이터나 정보를 제공하며, 이는 알고리즘이 실행되는 동안 변환되거나 처리된다.
- 알고리즘의 동작을 이해하고 예측하는 데 도움 됨. - 출력 ( Output ) : 알고리즘의 결과물
- 하나 이상의 명확하게 정의된 출력을 생성해야 함. 출력이란 알고리즘의 실행 결과를 나타낸다.
- 알고리즘이 어떤 문제를 해결하거나 어떤 작업을 수행하는지를 이해하는데 도움 됨. - 명확성 ( Clearness ) : 각 단계가 명확해야 함
- 단순하고 명확해야한다. 그 단계는 명확하게 정의되어야 하고, 모호성이 없어야 한다. 이는 알고리즘의 각 단계가 서로 분리되어 있으며, 각 단계가 명확하고 이해하기 쉬운 작업을 수행한다는 것을 의미한다.
- 알고리즘을 이해하고 따르는 데 도움 됨. - 유한성 ( Finiteness ) : 특정 시간 내에 종료되어야 함
- 유한한 단계 후에 종료되어야한다.
- 반드시 언젠가는 완료되어야 한다.
- 이것은 알고리즘이 무한 루프에 빠지지 않으며, 항상 특정조건이 충족되면 종료된다는 것을 보장한다. - 효과성 ( Effectiveness ) : 모든 과정이 실행 가능해야 함
- 각 단계는 실행 가능하고 해당 단계를 수행하는 데 필요한 시간과 리소스가 최소화 되어야한다.
- 성능을 최적화하는 데 중요하며, 대량의 데이터를 처리하거나 복잡한 계산을 수행하는 경우에 더 중요하다.
알고리즘의 대분류
- 정렬 알고리즘
- 데이터를 특정 순서(일반적으로는 숫자의 오름차순 또는 내림차순) 에 따라 재배열하는 알고리즘이다. 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등 각기 다른 방법으로 데이터를 정렬하며, 각각 장점과 단점을 가지고 있다. 데이터를 빠르고 효율적으로 정렬해야 하는 상황에 대응한다. - 탐색 알고리즘
- 데이터 구조 내에서 특정 항목을 찾는 데 사용된다. 선형 탐색, 이진 탐색 등과 같은 다양한 방법을 사용하여 데이터를 탐색하고, 각 방법은 그 자체의 특징과 사용 사례를 가지고 있다. 데이터의 빠른 검색과 효율적인 관리를 가능하게 한다. - 동적 프로그래밍 알고리즘
- 복잡한 문제를 작은 하위 문제로 분할하고, 이 하위 문제의 해결책을 결합하여 원래 문제를 해결하는 방법. 피보나치 수열, 배낭 문제, 최장 공통 부분 문자열 등과 같은 다양한 문제에 적용 가능하다. 복잡한 문제를 효율적으로 해결하는 데 중요한 도구를 제공한다.
문제를 이해하고 분석하기
문제를 잘 이해하기
> 문제의 요구사항을 명확하게 파악하고, 필요한 알고리즘을 설계하고, 적절한 테스트 케이스를 생성하는 데 도움 된다.
- 문제 이해하기
- 문제를 읽고 이해하는 것이 가장 첫 단계. - 요구사항 파악
- 문제의 요구사항 파악하는 것 . ex) 입력으로 정렬되지 않은 정수 배열 받아서, 가장 빈번하게 등장하는 정수 출력 등 - 예외사항 파악
- 문제에서 확인할 수 있는 예외 케이스 확인. 문제 설명에 자세하게 있는 경우도 있지만, 유추해야 하는 경우도 존재함.
문제를 잘 분석하기
> 분석하는 과정에서 문제의 복잡성 파악, 가능한 해결책 조사, 가장 적합한 알고리즘 선택
- 문제를 작은 단위로 나누기. 이를 "분할 정복( Divide and Conquer )"라고도 한다. 주어진 문제를 더 작고, 더 쉽게 해결할 수 있는 부분 문제로 나누는 것. 이 작은 문제들을 각각 해결하고, 해결책들을 합쳐서 원래의 문제를 해결하는 것이 분할 정복 전략이다. 문제를 보다 관리 가능한 부분으로 나누어 복잡성을 줄이고, 논리적인 단계를 설정하는 데에 도움 되며, 이를 통해 문제이 각 부분을 보다 깊이 이해할 수 있다.
- 가능한 해결책 조사하기. 다양한 알고리즘과 접근 방식을 고려하고, 장점과 단점을 비교한다.
- 가장 적합한 알고리즘 선택. 가장 효과적으로 해결할 수 있는 알고리즘 선택. 문제의 복잡성, 사용 가능한 리소스, 목표에 따라 달라진다.