1강
Last updated
Was this helpful?
Last updated
Was this helpful?
스터디 OT
알고리즘이란?
C언어에 대해
C언어 스터디는 EC 신입생들의 통과의례 같은 것이었습니다. 아주 오래전부터 신입생들에게 c언어 스터디를 진행했었습니다. 전공수업 때 C언어를 배우기 때문에 전공 공부에도 도움을 주고 동아리 내부에 학습 분위기를 조성하고자 하는 목적 있었습니다.
저는 C 스터디에서 C언어의 문법만을 자세하기 가르치는것은 전공수업의 중복에 지나지 않는다고 봅니다. 저는 문제해결 능력이 가장 중요하다고 생각합니다.
문제해결 능력은 다른말로 알고리즘 능력이라고 합니다. 이는 C를하든 C++를 하든 Java를 하든 python을 하든 어떤 분야에서든 필요한 능력입니다. 게다가 코드를 작성하는 능력과 프로그램이 어떻게 돌아가는지 파악하는 능력은 덤으로 늘어나게 됩니다.
따라서 저는 여러분이 알고리즘에 관심을 갖고 알고리즘적 사고를 훈련하는것이 여러분에게 가장 도움이 되는 것이라 생각했고, 이에맞춰 스터디를 진행할 예정입니다.
앞으로 구글 문서라는 곳에 여러분의 코드를 관리하고 평가 할 것입니다. 제목을 수정하고 글을 쓸 수 있습니다. 주목할 것은 글을 드래그해서 댓글을 달 수 있다는 것입니다. 이를 이용해 코드리뷰등을 할 생각입니다.
백준 문제집에서 강의중 실습한것을 제외한것이 과제입니다. 과제는 강의 당일에 주어지고 해당 강의의 과제는 다음 강의전날 까지 해주시면 됩니다. 예를들어 월요일의 과제는 수요일 오후11:59분까지 해주시면 됩니다. 과제의 방식은 스터디를 진행하면서 약간 바뀔 수 있습니다.
C 스터디가 종료된 후 프로그래밍 과제가 있을 예정입니다. 몇개의 프로그래밍 주제와 프로그램을 작성할 때의 조건을 받고 프로그램을 작성해야 합니다. 작성을 완료한 프로그램은 구글문서에 업로드 하시고 저를 포함한 동아리 부원들이 코드리뷰를 해줄 것입니다. 여러분은 리뷰를 바탕으로 자신의 코드를 수정(리펙토링)해야 합니다.
여러분 최대 공약수는 어떻게 구하죠?
공약수란 두 숫자와 동시에 나누어 떨어지는 수입니다. 최대 공약수는 그 중 가장 큰 수를 찾는 것입니다.
두 정수의 최대공약수를 구하는 문제를 생각해봅시다.
이 문제를 해결하는 가장 단순한 아이디어가 있습니다. 두 수중 작은 수를 골라서 1씩 내려가면서 나눠보는 겁니다.
즉 1593에서 1까지 모든 수로 1593과 2124를 나눠보는 겁니다.
두 수가 동시에 나누어 떨어지는 수중 가장 큰 것이 최대 공약수 입니다.
하지만 이런 단순반복 작업은 인간이 하기엔 한계가 있습니다.
여러분은 컴퓨터에게 하기 귀찮은 것들(과도하다 싶을 정도로 단순 반복 작업들)을 시키게 됩니다.
컴퓨터에게 명령하기로 작정했다면 그다음은 컴퓨터에게 무엇을 해야 하는지 아주 구체적으로 알려줘야 합니다.
우리에게 아주 간단하고 당연한 것도 컴퓨터에겐 그렇지 않을 수 있기 때문입니다.
<프로그램 동작 과정> 1. 두 수를 입력받는다. 그 두 수를 a, b 에 저장한다 2. 두 수중 작은것을 고른다. 그 수를 c에 저장한다 3. c를 1씩 감소시키면서 a, b와 동시에 나누어 떨어질 때를 찾는다. 맨 처음 나누어 떨어질 때의 c가 최대 공약수 이다.
문제를 해결하기 위한 핵심 아이디어를 찾고 컴퓨터가 원하는 동작을 수행하도록 '알아듣게'잘 프로그래밍 하는 것 이러한 일련의 과정을 알고리즘 설계 라고 합니다.
<참고용 코드>
여기서 몇가지 더 고민해봐야 할 사항이 있습니다.
프로그램의 효율을 따져야 합니다.
만약 위의 과정에서 두 수가 서로소고 작은 값이 1억이라고 합시다. 컴퓨터는 1억에서 1까지 대략 1억번 이상의 연산을 수행해야 할 것입니다. 즉 작은 값이 커질수록 문제를 푸는 속도가 일차함수처럼 증가합니다.
만약 작은값이 1억이 넘어가면 최대공약수를 찾는 데에 몇 초가 걸릴지도 모릅니다.
물론 이정도도 충분하다고 생각하실 수 있지만 더 빠른 알고리즘이 필요한 곳은 분명 있습니다. 속도가 더 빠른 알고리즘을 찾는것은 매우 중요합니다.
이 문제를 더 빠른 시간안에 해결할 수 있는 유클리드 호제법이라는 알고리즘이 있습니다.
이 알고리즘은 수의 크기에 따라 컴퓨터의 반복 횟수가 log함수적으로 증가합니다. 앞선 알고리즘에서 작은값이 1억이라면 1억번 연산해야 했지만 이 알고리즘을 사용하면 무려 27번 정도의 연산만으로 최대공약수를 구할 수 있습니다. 엄청난 차이가 느껴지죠?
이처럼 문제를 정의하고, 자세한 프로그램의 동작 과정을 설계하고, 더 효율적인 해결 과정을 고민하는 과정을 통틀어 알고리즘이라고 할 수 있습니다.
C언어가 절차지향 프로그래밍이라는 말은 어디서 들어보셨을 겁니다. 절차지향 프로그래밍은 영어로 (procedure-oriented programming)이라고 합니다. procedure를 곧이곧대로 '절차'라고 번역한것은 매우 잘못됐다고 생각합니다. 절차적이지 않은 프로그래밍 방식이란건 애초에 존재하지 않습니다. 프로그래밍 분야에서 procedure라는 것은 쉽게 말해서 나중에 배울 함수와 비슷한 개념입니다. 그러니까 절차지향 프로그래밍은 절차를 중요시하는 프로그래밍이라는 뜻보다는 oriented또한 ~지향이 아닌 ~중심 라는 뜻으로 이해해서 함수 중심 프로그래밍 방식이라고 생각하시면 됩니다.
여러분들의 전공수업에 C언어가 있기 때문에 문법을 자세히 소개하지 않아도 되는 장점이 있어서도 있지만 C언어의 구조가 알고리즘을 공부하기에 가장 적합하다고 생각했기 때문입니다.
다시한번 명심하실 것은 저는 C언어 그 자체를 배우는 것 보다는 C언어를 통해 컴퓨터에게 명령하고 컴퓨터의 동작 과정을 이해하는 것을 중요시 합니다.
(주의) 채점 서버의 시간이 UTC-0 기준인것을 주의하세요
UTC-0 이 몇시인지는 검색해서 찾아보세요!
9와 12의 최대 공약수를 구해보세요. 3이죠 어떻게 알았죠? 그냥 해보니까 됐나요?
그려면 1593과 2124의 최대공약수를 구해보세요. 힘들겁니다..