[알고리즘] 알고리즘 입문

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

 

알고리즘이란

1. 알고리즘 분석의 필요성: 알고리즘 분석은 문제 해결에 필요한 효율성을 결정하는 중요한 과정입니다. 이를 통해 어떤 알고리즘이 가장 효과적인, 어떤 컴퓨팅 리소스를 필요로 하는지 파악할 수 있습니다. 또한, 복잡한 문제나 큰 데이터 세트를 처리할 때, 알고리즘의 효율성은 중요한 역할을 합니다. 따라서, 알고리즘 분석은 최적의 알고리즘 선택과 컴퓨팅 리소스의 적절한 사용에 중요한 역할을 합니다.

 

2. 알고리즘의 수행시간: 알고리즘의 수행시간은 알고리즘의 효율성을 측정하는 기본적인 척도입니다. 이는 입력 크기와 연산의 복잡성에 따라 달라집니다. 일반적으로 알고리즘의 수행시간은 '빅 오(Big O)' 표기법으로 표현되며, 이는 최악의 경우에 얼마나 많은 시간이 걸리는지를 나타냅니다.

 

3. 재귀와 귀납적 사고: 재귀는 문제를 작은 부분으로 나누어 해결하는 방법입니다. 이는 큰 문제를 작은 문제로 쪼개고, 그 작은 문제들을 해결함으로써 원래의 큰 문제를 해결하는 방식입니다. 귀납적 사고는 이와 유사하게, 가장 작은 문제에서 시작하여 복잡한 문제를 해결하는 방법입니다. 이 두가지 방법은 알고리즘 설계에 있어 핵심적인 개념입니다.

 

4. 알고리즘으로 어떤 문제를 푸는가: 알고리즘은 다양한 문제 해결에 사용됩니다. 예를 들어, 데이터 정렬, 검색, 최단 경로 찾기, 그래프 문제 해결, 효과적인 자원 할당 등 다양한 문제를 푸는데 사용됩니다. 알고리즘은 문제를 정형화하고, 효율적으로 해결하기 위한 단계적 절차를 제공합니다. 따라서 알고리즘은 컴퓨터 과학 및 프로그래밍의 핵심적인 요소입니다.

 

알고리즘의 표현법

알고리즘은 다양한 방법으로 표현할 수 있습니다. 아래는 알고리즘의 세가지 표현법입니다.

 

1. 자연어: 자연어를 이용한 알고리즘 표현은 일반적인 언어를 사용해 알고리즘을 설명하는 방식입니다. 이 방식은 이해하기 쉽지만, 애매모호함이나 오해의 소지가 있을 수 있으며, 상세한 구현에 필요한 정보가 누락될 수 있습니다.

 

2. 의사코드: 의사코드는 프로그래밍 언어와 자연어를 혼합하여 알고리즘을 설명하는 방법입니다. 의사코드는 특정 프로그래밍 언어의 문법을 따르지 않으므로, 언어에 구애받지 않고 알고리즘을 표현할 수 있습니다. 이는 알고리즘의 로직을 명확하게 이해하는 데 도움이 됩니다.

다양한 스타일의 의사 코드, 출처: 위키백과

 

3. 순서도: 순서도는 알고리즘을 시각적으로 표현하는 방법입니다. 순서도는 흐름도(flowchart)라고도 하며, 도형과 화살표를 이용해 알고리즘의 흐름을 그래픽으로 표현합니다. 순서도는 알고리즘의 흐름을 직관적으로 이해하는 데 유용하지만, 복잡한 알고리즘을 표현하기에는 한계가 있을 수 있습니다.

c언어의 순서도, 출처: 위키백과