알고리즘을 공부하기 위해 책과 자료들을 수집해 보고 공부하기만 해서 정리하는 느낌으로 알고리즘 시리즈를 연재해보려고 합니다.
알고리즘에 대한 갈증
알고리즘에 대한 필요성은 클립플러를 개발하면서 강하게 느꼈다. 클립플러의 일부 기능 중 clip으로 만들 사이트의 메타태그를 긁어와 유효한 태그를 추천하는 기능을 설계하는데 가장 큰 문제에 봉착했었다. 바로 코딩. 분명 팩토리얼로 단어의 조합을 만들면 된다는 생각은 있는데 팩토리얼 알고리즘 맞는지 그리고 어떻게 구현하는지 까마득했다;;; 그러다 잠시 개발은 중단하고 알고리즘에 대한 기초중의 기초와 중간을 건너띄고 팩토리얼 알고리즘에 대해 공부했다. 기능개발은 했지만 리팩토링은 물론 성능분석도 거의 하지 못했다. 그러다 조언을 구하면 더 나은 코드 설계와 개발실력을 갖추기 위해서는 알고리즘 공부가 도움이 많이 되고, 나중에 취업을 할때에도 도움이 많이 될거라고 했는데… 그렇게 모두의 충고를 과소평가하고 드문드문 보기만 했다;;; 그러다보니 알고리즘에 대한 베이스가 약하고, 코딩 테스트를 보더라도 쉬운 문제까지가 한계였다.
그래서 이번 기회에 알고리즘에 대한 숙제를 시리즈로 연재해보려고 마음 먹었다. 다시 시작하는 마음으로 꼬박꼬박 정리해가면서 다음에 봐도 공부할만한 자료가 될때까지.
먼저 알고리즘에 대해 간략하게 다룬 후 연재를 어떤 방향으로 할지 논해보려고 한다.
알고리즘이란?
우리는 이미 알고리즘에 익숙해져있다. 다만, 그러한 것들을 ‘알고리즘’이라고 부르지 않을뿐. 이를테면,
- 가장 빠른 또는 편한 출근길 또는 퇴근길 경로 탐색
- 오늘 치킨을 먹을것인가, 주중에 먹을것인가에 대한 기회비용 탐색
- 한정된 금액 안에서 장보기
위와 같은 과정 모두 알고리즘이라고 할 수 있으며, 특정 문제를 해결하기 위한 일련의 계산과정으로 입력, 출력 그리고 계산과정 이 존재한다.
프로그래밍에서 알고리즘이란 필수적인 것은 아니지만 더 효율적이고 효과적인 방법으로 어떤 결과값(출력)을 만들어낼 수 있는 과학적 접근법으로, 어떤 알고리즘으로 과정을 설계하느냐에 따라 결과가 동일하더라도 프로그램의 속도나 처리방식 등이 크게 차이나는 경우도 있다.
알고리즘의 조건
알고리즘은 다음의 조건을 만족해야 한다.
- 입력: 외부에서 제공되는 자료가 0개 이상 존재한다.
- 출력: 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
- 명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
- 유한성(종결성): 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
- 효율성: 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.
좋은 알고리즘이란? 분석 기준.
- 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
- 최적성 :그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 ‘잘 - 알려진’ 이 아니라 ‘가장 좋은’의 의미이다
- 시간 복잡도 (Big-O Notation), (이 부분에 대해서는 연재물로 따로 다루겠습니다.)
- 기억 장소 사용량 (공간 복잡도) : 수행에 필요한 저장 공간
알고리즘 설계 순서
- from leobit님 블로그 - 알고리즘
- 일반적인 알고리즘 순서
- 문제 정의
- 모델 고안
- 명세 작성
- 설계
- 검증
- 분석(복잡도 등)
- 구현
- 테스트
- 문서화
- 자연어 ↔ 프로그래밍 언어 사이의 방식을 단계별로 기록
- 프로그램의 진행 과정에 조금이라도 관심이 있는 사람이라면, 이 의사 코드를 읽고 이해할 수 있을까?
- 이 의사 코드는 실제 코드로 쉽게 바뀔 수 있을까?
- 과정을 진행하는데 필요한 단계 중, 빠뜨린 것은 없나?
- 의사 코드를 읽는 사람들이 이해할 수 있는 용어들을 사용했는가?
알고리즘과 함께 논하는 개념들
- 시간 복잡도
- 자료구조
- 정렬
알고리즘 공부를 준비함과 동시에 취업 및 면접에 대한 자료를 찾고 읽으면서 가장 많이 언급된 것들로 시간 복잡도에 대한 정확한 이해와 각 알고리즘에 대한 시간 복잡도 특성에 대해 암기수준으로 준비를 한다면 면접에서 많은 점수를 딸수 있다고 했습니다. 그리고 자료구조와 정렬의 경우도 마찬가지이다. 알고리즘과 뗄 수 없는 관계이며 각 알고리즘에 맞는 자료구조와 어떤 특징을 가지고 있으며 왜 사용하는지 를 알고 있다면 이 또한 (많은) 점수를 얻을 수 있다고 합니다.
연재 계획
앞으로 다룰 주제는 알고리즘과 함께 논하는 개념들 순서로 연재할 것이며 중간중간 문제를 풀어보며 되새김질을 빙자한 복습을 이어가려고 합니다.
주워 들은 팁
이 부분은 yena님의 알고리즘 포스팅에서 보고 나 또한 상기하는 목적에서 복붙해왔습니다.
많은 사람들이 공통적으로 얘기하는 사실들이 있다.
- 처음부터 어려운 걸 하려고 하지 말고, 간단한 것부터 시작하자.
- 선택한 언어의 문법과 클래스를 잘 파악하자.
- 풀고 난 후 다른 사람의 풀이 참고하자.
- 경험이 쌓이면 익숙해진다. 조급해하지 말자.
(보실지는 모르겠지만 yena님 감사합니다.)