학교 선배가 알려주는! gbsw 신입생 부트캠프

응용반에 오신 것을 매우 환영합니다.

아마 이 반을 선택하셨다면,

C, 또는 다른 프로그래밍 언어의 기초적인 문법을 어느 정도 배운 적이 있을 것입니다.

이 반에서는 "문법"이 아닌 "알고리즘"에 초점을 맞추었기에,
C의 특별한 문법은 쓰지 않을 것입니다.(포인터, 기타 헤더 파일 등)

1) 알고리즘이란?

문제를 해결하기 위한 절차, 또는 방법을 뜻합니다.

집에서 학교로 이동하는 최단 경로를 구하거나(다익스트라),
웹페이지에서 ctrl + f로 원하는 단어를 찾거나(kmp),
집 비밀번호를 뚫기위해 하나하나 다 시도해보는(브루트 포스) 것.

모두 알고리즘입니다.

간단한 예시 문제를 들고 왔습니다. 이 문제를 풀기위한 알고리즘은 무엇일까요?

거스롬돈의 액수가 주어지면, 최소한의 동전만 사용해서 거스름돈을 반환하시오.
(단, 동전의 종류는 500, 100, 50, 10이고, 거스름돈은 10으로 나누어떨어진다.)

정답은, 사용할 수 있는 가장 큰 동전부터 차례대로 사용하는 것입니다.

거스름돈이 2790원 일 경우,
500원 동전 5개, 100원 동전 2개, 50원 동전 1개, 10원 동전 4개.
총 12개의 동전을 사용하여 반환할 수 있으며, 이 것이 최소한의 동전 갯수입니다.

(이런식으로, 현재 상태에서 가장 최적의 상태만을 생각하는 알고리즘을 그리디 알고리즘이라고 부릅니다.)

2) 알고리즘을 왜 배우는가?

여러가지 이유가 있겠지만, 필자가 생각하는 이유는 크게 두 가지입니다.

(1) 문제 해결 능력 향상

프로그래밍은 로직 구현과 디버깅의 반복. 즉, 문제를 해결하는 과정의 연속입니다.
정보과학의 문제를 공부 함으로써, 실무에서 퍼포먼스를 향상 시키는 것입니다.

(2) 코딩 테스트 준비

대부분의 회사에서는, 개발자를 채용할 때 "코딩 테스트"를 응시해야 합니다.
시험에서 출제되는 문제를 해결하기 위해, 미리 문제들을 풀어보면서 공부를 할 필요가 있습니다.

3) 어떤 알고리즘을 배우게 되는가?

알고리즘의 종류는 셀 수 없을 정도로 많습니다.(필자가 백준에서 사용해본 알고리즘만 60가지가 넘습니다.)

모든 알고리즘을 배울 수는 없기에, 필자가 선정한 4가지의 알고리즘을 배울 예정입니다.

(1) 브루트 포스

완전 탐색, 무식하게 풀기 등으로도 불립니다.
가능한 모든 경우의 수를 탐색하는 알고리즘입니다.

(2) 그리디

앞서 설명하였듯, 지금 당장 최적의 해를 탐색하는 알고리즘입니다.

(3) DP

Dynamic Programming(동적 계획법)의 약자로,
작은 문제의 해답을 큰 문제의 해결 방법으로 사용하는 알고리즘입니다.

(4) 정수론

정수의 성질에 대해 연구하는 학문이자, 알고리즘입니다.
중1 수학시간 때 배운 그거 맞습니다.

추가적으로 시간이 남는다면, 필자가 좋아하는 쉬운 알고리즘(애드 혹, 누적 합 등)도 작성해보겠습니다.

이번 시간에는 알고리즘의 정의, 배워야 할 이유, 앞으로 배울 알고리즘의 종류를 알아보았습니다.

다음 시간에는 알고리즘의 성능을 파악하는 "시간복잡도"를 알아보겠습니다.