안녕하세요 개발자 밍이입니다 🌿
알고리즘은 이제 우리에게 굉장히 친숙한 단어가 되었습니다. 유튜브의 '알고리즘'은 유명해졌으며 개발을 공부하는 사람들이라면 알고리즘 대회를 준비한다던가 알고리즘 코딩테스트를 준비한 경험이 있으실테죠. 여기서 우리가 자주 이야기하는 알고리즘이라는건 무엇일까요? 이 글에서는 알고리즘이 무엇인지 어떻게 풀어내야하는지 다룰 것입니다.
알고리즘의 정의
A procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation
사전적의미의 알고리즘은 문제를 풀기 위한 절차나 방법을 공식화된 형태로 표현하는 것입니다.
다시 이야기하면, 알고리즘은 어떠한 문제를 풀기 위한 효율적인 절차입니다. 문제를 푸는 단계적 절차를 명확하게 기술하는 것이죠.
예를 들면, 반의 30명의 학생들이 있고 이들의 영어 평균 성적을 구하는 문제가 주어집니다.
여기서 입력값은 30명 학생들의 영어 성적이고 구해야하는 출력값은 평균 성적입니다.
1. 학생들의 영어 성적을 전부 더한다
2. 영어 성적의 총합을 학생들의 인원수 만큼 나눈다.
3. 위의 나눈값을 평균 성적으로 리턴(출력)한다.
위의 절차가 알고리즘이 되겠습니다.
이와같이 어떠한 문제가 주어졌을때, 그 문제를 풀어가는 단계적 절차를 명확하게 기술하는것이 알고리즘인 것입니다.
알고리즘의 조건
알고리즘은 다음 5가지 조건을 만족해야합니다.
- 입력과 출력: 외부에서 0개 이상의 값을 받아 1개 이상의 값을 출력한다.
- 명확성: 각 단계가 단순해야 하며, 명확하게 정의되어있어야 한다.
- 유한성: 한정된 수의 절차 수행 후에는 반드시 종료되어야 한다.
- 효과성: 모든 절차와 명령은 실행가능해야한다.
- 효율성: 알고리즘은 효율적이여야 한다.
알고리즘에서 중요한것 / 공부하는 방법
그렇다면 알고리즘을 공부하는 우리에게 중요한 것은 무엇일까?
당연하게도 가장 중요한 것은 "문제와 해답" 입니다.
알고리즘에서 해답을 찾을 때에는 모든 경우에서의 해답을 찾아야합니다. 즉, 어떠한 입력값이 주어지더라도 정확한 해답을 구할수 있는 단계적 절차를 기술해야하는 것입니다.
알고리즘을 문제를 풀어 나갈때, 문제를 읽고 바로 푸는 것을 추천하지 않습니다.
How to solve?
- 문제를 읽은 후 문제 분석:
문제에서 입력값과 출력값을 알아야합니다. 어떠한 입력값이 주어지는지 그리고 어떠한 것을 출력하는지 명확히 알아야합니다. 모든 경우에서의 해답인 답을 찾아야 하기에 제한사항을 체크해야하죠. - 문제 유형에 맞게 코딩방향성 계획:
문제 분석후 이 단계에서는 노트와 펜을 준비해 순서도를 작성할수도 있으며 혹은 컴퓨터에 간단하게 수도코드를 작성할 수 있습니다. 방법은 본인에게 맞는 택하되, 중요한 것은 코드를 짜기 전에 어떠한 자료구조를 사용할것인지와 어떻게 해결할 것인지 대략적인 방향을 정해야 합니다. - 코드 작성후 디버깅:
알고리즘 풀이 후 디버깅을 하며 테스트를 합니다. 모든 경우에서 코드가 실행이 되고있는지와 코드가 효율적인지도 살펴야 합니다.
효율적인 알고리즘
효율적인 알고리즘은 절차를 수행하면서 출력값이 나올때까지 실행시간이 짧고 자원을 상대적으로 적게 사용하는 것입니다. 알고리즘의 효율성을 확인하기 위해서는 위해서는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)를 알아야 합니다.
시간복잡도
시간복잡도는 알고리즘을 수행하는동안의 연산횟수를 세고 처리해야할 데이터의 양에 대한 함수를 계산한다. 즉, 알고리즘에서 사용되는 연산횟수의 총량입니다.
공간복잡도
공간복잡도는 알고리즘 수행하고 종료하기까지 필요한 자원 공간의 양입니다. 총 공간요구는 고정공간요구와 가변공간요구의 합입니다. 고정공간은 입출력의 크기와 상관없는 공간의 요구이고 가변공간은 동적으로 필요한 공간입니다.
알고리즘 공부
알고리즘 문제 풀이에 능숙해지기 위해서는 두가지가 필요합니다. 알고리즘 문제 풀이를 위한 자료구조에 대한 이해와 기초문제부터 숙련도가 필요한 알고리즘 문제까지 연습문제를 꾸준히 풀어보는것입니다. 이 블로그에는 여러 자료구조의 개념에 대한 글과 백준사이트에서의 알고리즘을 단계별로 풀이한 글을 올릴 예정입니다.
