Tagged: 알고리즘

컴퓨터 영역이 너무 어려워 지고 있다.

컴퓨터 영역이 너무 어려워 지고 있다. 어찌보면 그런 수순으로 가고 있는게 당연한건지도 모르겠다. 과거에 등안시 했던 것들, 대표적으로 알고리즘 같은 것들을 요즘에는 중요하게 여기는 걸 보면 말이다.

과거나 지금이나 알고리즘은 중요하다. 하지만 유독 그것이 부각되고 나머지는 좀 덜한 중요도를 갖는것처럼 왜곡되고 있는게 문제가 되지 않을까 싶다. 그동안에 개인의 역량이란게 무엇으로 평가 되었는지는 모르겠지만, 요즘에는 코딩 알고리즘 문제가 기본이 되다보니 책방에 가서 보면 알고리즘 관련 서적들이 아주 많다.

거의 15년정도를 컴퓨터 분야에 있다보니, 요즘들어 그런 생각이 더 깊어지는 것 같다.  코딩으로 알고리즘을 구현하는 것도 중요하지만 그것보다 더 중요한 것이 ‘상황인식’ 그리고 ‘아이디어’가 아닐까 싶은데 나보다 어린 사람들을 보면 알고리즘은 잘 아는데 나머지는 모두 부족함으로 다가온다.

개인적으로 어떤 사람이 경력을 봤을때에 다음과 같은 질문을 먼저한다.

  • 문서 작성은 잘하는가? 그렇다면 어떻게 작성하나?
  • 협업을 할때에 주로 어떤걸로 하나? 메신저? E-메일?
  • Java 를 쓴다고 하는데 객체지향 프로그래밍이 뭔가?
  • 디자인 패턴을 잘 사용하나?
  • 코드 재사용성 고려에는 어떤게 있나?
  • 뭔가 관심을 넓히려고 하는가?

나는 문서 작성을 중요시 한다. 어느 회사에 잠깐 있었을때에 어떤 개발자는 ‘소스코드에 다 있다’ 라고 말했던게 기억난다. Jira 와 소스코드를 보라는 말만 되풀이했던 곳이 였다.

정작 소스코드를 보고 있자면 커다란 배치 프로그램을 보는 느낌이 들곤 한다. 하나의 메소드에서 여러가지 조건들을 처리하기 위해서 if 문이 수십게 있었던 기억들… 클래스 하나에 조건마다 메소드를 작성하다보니 1000 라인이 넘었던 클래스…..

알고리즘으로 뭘썻네 하기전에 객체지향 프로그래밍이라도 먼저 해줬으면 하는 바람이 요새는 더 크게 다가온다.

알고리즘은 대략 이런게 있다정도의 내용을 인지하고 있고 상황에 맞게 활용할수 있도록 떠올리는 정도면 그만이다. 현업에서 알고리즘을 온전히 내 머리속에서 생각해서 구현해보적은 별로 없었던게 이유이기도 했지만, 혼자 일하고 있다면 알고리즘만 생각하겠지만, 협업을 하는 경우에는 알고리즘 만큼이나 중요한 여러가지가 존재한다는 사실도 잊지 않았으면 좋으련만…  (사실 많은 사람들이 사용하는 킬러 애플리케이션들에서는 독창적인 알고리즘이 중요하다. OS를 제작한다던가, Office 와 같은 것들… 거대하기도 하지만 내부적인 기능들이 정교하면서도 깊이가 있는 것들은 알고리즘을 속속들이 알고 응용하고 독창적으로 개발하기도 해야한다.  하지만 지금 경력을 뒤돌아볼때에 그러한 정교한 것들을 만들어보긴 했지만 깊이가 있는 것들을 작성해본적은 거의 없다. 웹, 서버개발들을 했었지만 사실 주어진 알고리즘 라이브러리를 잘 활용해도 왠만한 안전한 프로그램은 나온다)

어떤 일을 하던간에 많은 고민을 하면서 했으면 하는 바람이 있다. 자바 프로그래밍을 할 경우에 java 8 로 프로젝트를 한다고 하더라도 미래에는 바꿀 수밖에 없는 운명일 거다. 그렇다면 호환성을 고려해 제작해야하는건 개발자라면 당연한 역량인데도 나중에 생각하자는 식..

지금은 모로가던 서울로 가기만 하자라는 식의 사고방식의 개발자들이 너무나 많아 보인다. 그런 사고방식을 하면서 결국에는 남탓, 환경탓을 하고 있는 사람들이 너무나 많아 보인다.

최근 알고리즘 논쟁을 보고 느낌점…

최근 인터넷에 난데 없이 알고리즘 논쟁이 있었던 모양이다. 뭐 인터넷이라는게 방대하고 거기다 한국이란 곳으로 국한한다고 하더라도 몇몇 커뮤니티를 타고 옥신각신 한 정도밖에 더 될까만은 매우 흥미롭게 지켜보게 됐다.

원래 성격상 흥미가 없으면 ‘별 시덥잖은 이야기’ 정도로 치부하는데, 알고리리즘 논쟁을 보고 흥미가 생긴 이유가 아주 근본적인 사고차이에서 비롯된 것이라 생각했기 때문이다.

발단은 다음의 글에서 출발 했다.

개인적으로 알고리즘 관련 논람에 민감한 이유

알고리즘이 더 이상 모든 분야의 기본 지식이 아니라고 생각하는 이유는 이미 그런 토론을 통해 충분히 이야기했기 때문에, 지금은 왜 제가 이런 문제를 특히 민감하게 느끼는지에 대해 적어볼까 합니다.

제 생각에 자바나 C#, 혹은 자바스크립트 개발자에게도 ‘기초 지식’으로 알고리즘이나 운영체제 등을 공부할 것을 주문하는 것은 대체로 그런 ‘기본’을 배우면 나머지 ‘응용분야’는 쉽게 익힐 수 있을 것이라는 가정에서 출발하는 것 같습니다.

그리고 경우에 따라선 한 걸음 더 나아가 자바 같은 고수준 언어로 다루는 분야는 모두 그런 ‘응용’에 해당하기 때문에 보다 근본적이고 깊이 있는 운영체제나 C언어 등만 제대로 하면 어렵지 않게 익힐 수 있을 것이라는 근거없는 자부심으로 표출되기도 합니다.

https://okky.kr/article/396435

전체적으로 댓글이 우호적으로 달리는데, 개인적으로 적지 않게 놀랐다. 도대체 저런 글에 저렇게 많은 공감을 얻은 이유는 무엇일까? 라는 의문이들게 되면서 이 논쟁을 지켜보게 되었다.

얼마 가지 않아 다른분이 반론글이 올라오기 시작했다.

저주스러운 대한민국의 SI와 6개월짜리 국비지원 학원들 때문에 우리나라는 개발자들에 대한 인식이 형편없어졌는데, 개발자는 노가다꾼이 아니고 공학자에 속하는 직종이다. 자신의 재능이 아무리 비천할지라도 언제나 높은 수준에 오르기 위해 공부하고 자신의 결과물이 완벽에 가까워지도록 노력해야 하는 종류의 사람들이라는 뜻이다. 그런데 지금 소개하는 주장은 대학교에서 배우는 CS Fundamental이 구시대적이기 때문에 대학교의 커리큘럼이 예비 개발자들에게 구현에 대해 능숙해지도록 좀 더 가이드해야 한다고 주장한다. (대학이 직업학교인가?) 그런데 재미있게도 이런 주장을 하는 사람들은 이른바 개발자 커뮤니티의 네임드라는 부류는 될지언정 누구나 인정하는 구글러나 페이스북 개발자, 스타개발자는 아니다. (사실, 그런 사람들은 그런 시시한 커뮤니티를 하지도 않는다. 나도 페친들 링크 타고 가게됐을 뿐이다) 오히려, 인터넷에서 이름을 보는 대가들은 자료구조와 알고리즘을 탄탄이 하기를 당부한다. 그런데 왜 많은 사람들이 이런 말도 안되는 주장에 동조하고 열광하는가?

https://medium.com/@ghilbut/%EC%8B%A4%EB%AC%B4-%EA%B0%9C%EB%B0%9C%EC%9E%90%EC%97%90%EA%B2%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80-%EB%8D%9C-%EC%A4%91%EC%9A%94%ED%95%A0%EA%B9%8C-fcbab7f87074

많은 사람들이 이글을 보았을 텐데, 웃기게도 ‘글이 너무 격양되어 있다’, ‘논리적인 글보다 욕하는 글’이라는 씹선비질 하는데 웃음이 났다. ㅋㅋ 격양된 글이긴 하지만 나름대로 논지가 있었기 때문에 그 논지에 대한 말들은 없고 그져 글이 어떠내 저쪄네… ㅋㅋ

위 글은 1부, 2부로 나뉘는데 이 글을 쓴 사람의 논지는 ‘알고리즘은 문제를 해렬하기 위한 방법으로 기능적 유효성이 있다’ 정도로 보인다.

 

알고리즘=문제해결 능력

개발자도 아닌 나 같은 사람은 알고리즘을 몰라도 된다. 탐색트리가 어쪄네 뭐가 어쩌네 하는 골치아픈 것들은 개발자들이나 하는 것이지 나 같은 밑바닥 인생을 사는 사람과 거리가 먼 이야기다.

이렇게 말을 하면 첫번째 글에 동조하는 듯하지만, ‘알고리즘’ 이라는 전형적인 전산학이 의미를 버리고 ‘문재 해결 방법’ 이라는 의미를 부여하면 두번째 글이 더 설득력이 있게 된다. 나 또한 두번째 글쓴이에 말에 동의 하는 바이고 그가 주장하고 비토했던 것에 전적으로 동의한다.

개발이 아니라 시스템을 운영하다보면 별의별 사건사고가 발생한다. 흔히 ‘장애’ 가 발생하면 최대한 빠르게 문제를 해결해야 한다. 그렇지 않으면 고객으로부터 손해배상을 제기하겠다는 서슬퍼런 이야기를 듣게 될테니까.

전부 다 그렇게 일하는 것은 아니겠지만 시스템 운영측면에서 장애 발생하면 대부분의 사람들은 ‘경험’ 에 의존하게 된다. 과거에 유사한 장애가 발생한 경험을 기반으로 문제를 해결하는 것이 가장 빠른 방법이기 때문이다. 시간은 자꾸가는데 운영체제론이 어쩌고 컴퓨터이론이 어쩌고 떠들어대봤자 답이 안나온다.

문제는 이러한 경험을 문제를 해결하고 난 다음이 문제가 된다. 반드시 장애 처리 후에 복기를 해보는데, 이게 정말 제대로된 문제해결이였는지를 평가해 향후 같은 장애가 발생하지 않도록 하는 회의를 진행한다.

바로 이 회의에서 ‘알고리즘’ 이 나온다. 웽? 시스템 장애 대응 회의때에 개발자 알고리즘이 나온다고?

ㅋㅋㅋ 알고리즘을 문제해결 능력이라는 측면으로 본다면 시스템 장애 대응 회의는 알고리즘이 회의가 된다. 개발자들이라는 시각으로만 좁게 보다보니 알고리즘이라고 하면 전산학 이론의 알고리즘만을 생각하지만 그 시각을 좀 더 확대 해보면 알고리즘이라는 말 자체는 문제를 해결하는 방법론을 전부 총칭한다.

결국 알고리즘을 잘 하냐 못하냐는 문제를 해결할 능력이 있는냐 라는 말과 같은 것이다. 이렇게 보면 알고리즘이라는 것 자체는 우리가 살면서 매일매일 생각하고 해결하는 것들과 다를바 없다.

그래서 두번째 글의 글쓴이가 예를들었던 면접 관련 이야기가 알고리즘이 무엇인지를 정확하게 보여준거라 생각한다.

알고리즘 인터뷰가 시작되면, 면접관은 데이터와 해결해야 할 문제를 포함한 몇 가지 조건들을 준다. 다만, 이 조건들은 대부분 완벽하지 않다. 대부분은 필수 요소 몇 가지가 빠져있으며, 때로는 아무 쓸모없는 조건들이 함께 있을 때도 있다. 이 조건들을 질의응답을 통해 문제 정의 가능한 수준으로 정리해야 한다. 그리고 나면 그 문제를 해결하기 위해 어떤 전략을 사용할 것인지를 설명한다. 면접관과 문제 해결 전략과 솔루션의 공간복잡도 및 시간복잡도 등에 대해 토론한 뒤 정리가 되면 구현을 시작한다. 이 때, 면접관이 내가 생각하지 못한 예외 케이스들을 자꾸 제시해서 코드 수정이 잦아지면 인터뷰는 200% 망했다고 보면 된다. 합격하려면 일반적으로 코드가 한번에 완성되어야 하고, 그렇기 때문에 구현 전에 토론과 함께 주의 깊게 전략을 완성해야 한다. 일반적으로는 그렇게 문제 풀이가 끝나지만, 구글은 종종 해당 문제에서 데이터셋의 스케일이 매우 커졌을 때에 대한 질문을 던진다. 현재 솔루션으로 확장된 데이터 규모에 대응 가능한지, 그렇지 않다면 이유가 무엇인지, 그럼 어떤 방식으로 더 큰 규모의 데이터를 처리할 수 있는지에 대해 솔루션을 요청한다. 이 때, 인터뷰 내용은 구글 내부에서 실제로 처리하는 업무의 인터뷰 버전일 가능성도 있다. 다시 강조하지만, 알고리즘 인터뷰는 절대 당신이 얼마나 아름다운 알고리즘을 외우고 있는지 보려는 것이 아니라 당신의 커뮤니케이션 능력과 논리적 사고력을 보고 싶어하는 것이다.

구글이라는 회사의 예제인데, 당연히 구글은 컴퓨터 회사이고 우리가 알고 있는 전산학의 알고리즘쯤은 줄줄이 꽤고 있어야 하며 그것을 기반으로 구글이 문제를 풀어야 한다. 문제는 두번째 글쓴이가 예를든 글을 자세히 읽어보면 면접시에 단순하게 면접자에게 알아서 풀어봐식은 하지 않는다는 것이다.

개인적으로 외국계회사에 면접도 몇몇보고 느낀 것이 바로 두번째 글쓴이가 이야기한 구글의 면접과 비슷했다. 면접관이 문제를 주는데, 문제자체가 문제가 있는 경우가 많았다. 그것을 캐취해서 자신이 의견을 피력하고 면접관과 토론을 벌여야만 했다.

겁나, 아니 존나 힘들었다. 면접관가 토론을 한다고 ??? ㅅㅂ 그냥 화이트보드에 알고리즘 기술하고 ‘맞죠?’ 하고 말지… 면접관은 화이트보드에 마커를 집어들기 전까지 ‘니가 문제를 어떻게 할지 설명해봐~’ 를 계속 요구했다. 이미 내 머리는 김이나기 시작했고……

그런다음에 Python 으로 문제 해결을 구현해야하는데, 이때부터도 난제들이다 . Python 을 얼마나 알고 있는지를 테스트하기 위해서 코딩하는 내내 ‘이건 왜 일케 코딩했지?’ 라는 질문이 계속 쏟아졌다. ‘Python 은 글케 하면 비효율적이다’, ‘문자열 처리는 일케 하면 어케하냐?’ 식의 비난과 비판.. ㅋㅋ 물론 팁도 준다. ‘이건 이렇게 해야 더 좋아~’ 식인데, 문제는 그게 왜 좋은건지 모르면 답 없는 거지.. ㅋㅋㅋ (내가 그랬음.. ㅋㅋ 왜 글케 해야하는지 몰랐음.. ㅋㅋㅋ 그냥 면접관이 그게 좋다니까 그걸로 했지.. ㅋㅋ)

내가 봤던 외국회사에 면접에서는 전산학 알고리즘은 단 한줄도 나온적이 없다. 그렇다면 내가 그 면접에서 알고리즘을 사용한적이 없는가? 전혀 그렇지 않다. 면접관과 토론하고 문제에 어떤 문제가 있으며 조건을 어떻게 만족해야 하며 Python 이라는 언어적 특성을 살리고 이렇게 구현하면 컴퓨터의 Compute, Memory 를 적게 차지하면서도 많은 일을 하게 할 것인가? 이것을 풀어나가고 최종적인 완성품을 만든것이 모두 다 알고리즘 문제라고 보면 된다.

결국 알고리즘은 모든 것의 기본이라고 봐야 한다. 시스템 운영을 하던 개발을 하던 수많은 문제에 직면하게 되는데, 알고리즘이 없다? 자바스크립트를 배우는데 있어서 복잡 다단한 알고리즘보다는 라이브러리를 아는게 더 중요하다? 그런 다음에 수 많은 문제들을 어떻게 해결할 것인가? 라이브러리를 끼워 넣으면서 해결할 건가? 물론 이진트리, 정렬등을 다 알고 있어야 한다는 건 아니다. 그렇다 라이브러리를 많이 안다고 문제 해결 능력이 저절로 생겨나나?

시스템 운영이라는 직군에서 면접에서도 마찬가지다. 외국의 경우에 어떤 장애 발생시에 어떻게 문제를 해결했는지에서 관심이 있지 몇분만에 그것을 해결했는지에는 아무런 관심도 없다. 문제를 인식하고 니가 그 문제를 바라본 관점이 무엇인지를 설명하라고 하는데, 그 바라본 관점이란게 당연히 컴퓨터 이론을 기반으로 한 것이여야 했다. 그러다보면 당연히 컴퓨터 강의실의 토론처럼 변하는 경우가 많았다.

알고리즘이라는 말 자체가 ‘현실세계에서 발생한 문제를 컴퓨터라는 도구를 이용해서 어떻게 해결할 것인가?’ 라는 것 아닌가?

문제해결은 고사하고 검색하기 바쁨.

내가 왜 이런 글을 장황하게 쓰냐하면 SI 에서 밥벌이를 하다보니 느끼는게 많이 있었기 때문이다. 그중에 하나가 ‘문제 해결능력 없는 인간들이 너무나 많다’ 라는 거다.

내가 알고 있던 한 사람은 개발 경력만 15년정도 였는데, 그가 들고 다닌 컴퓨터에는 그가 그동안 했던 프로젝트의 소스코드들이 들어 있었다. 그는 그것을 자신이 프로젝트를 할때마다 활용한다고 자랑스럽게 이야기를 하곤 했다.

내가 보기에 그것은 자랑거리가 못된다. 그 사람은 구글를 이용한 검색을 하지 않을뿐, 자신이 했던 과거의 코드를 기반으로 모든 프로젝트를 수행하고 있는 것 뿐이다. 과거의 코드가 현 시점의 문제해결에 부합한다면 사용하는데 아무런 문제가 없겠지만 시간을 흐르고 문제해결의 관점도 바뀌는 경우가 많다.  과거의 코드를 재활용할 생각이 였다면 그것을 현시점의 문제해결에 적합한지 정도는 테스트해야 하는게 맞지만 뭐 그렇게 하는 인간을 본적이 없으니… 도대체 자신이 한 프로젝트의 소스 코드를 왜 들고 있는거냐? 그것도 이해 못할 일이다.

뭐가 문제냐? 문제 될 것은 없다. 문제는 이후에 벌어지는데, 적어도 구글이나 github 에서 따온 코드라면 적어도 그것을 이용할때에 테스트라도 한번 했어야 했다. 테스트 하는 인간 못봤다. 그냥 Copy&Paste 지.. ㅋㅋㅋ   그리고 문제 생기면 서버 안좋데.. -_-;;

구글 검색을 활용하는 것에 뭐라하는게 아니다. 활용을 잘 했으면 한다는 거다. 특히나 시스템 운영에서도 구글 검색을 많이 이용하는데, 구글 검색한 내용이 이미 10년전이나 몇년이 지난 내용들을 가져다 실무에 적용하는 인간들 적지 않다.

한국의 SI 산업에 가장 큰 문제는 문제 해결 능력이 없다는데 있다. 문제 해결 능력은 많은 프로젝트를 수행하고 경력이 많다고 쌓이는게 아니다. 문제 해결을 잘할려면 이론도 많이 알아야 하고 문제가 시사하는 관점을 정확하게 파악하고 문제 해결을 위한 기획, 설계를 잘 해야한다. 하지만 SI 산업에 그렇게 일을 하는 인간 없다고 봐야 한다.

이런 측면에서 알고리즘 논쟁은 흥미로운 것이다. 개발자만의 논쟁거리가 못된다. 알고리즘을 그져 트리, 정렬문제로만 축소해보면 답이 없다는 것이다. 그런 관점이 잘 들어난 것이 첫번째 글쓴이의 글로 보인다. 그나마 두번째 글쓴이 정도가 알고리즘의 대한 관점을 잘 제시했다고 본다.

알고리즘 – 최대공약수(Great Common Divisor)

분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다.

약분, 최대공약수를 구하라.

최대공약수 구하기 1

최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다.

최대공약수를 구하는 무한대입법이라고 보시면 됩니다.

작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 이용하기 위해서 for 문을 이용했고, maxDiv 변수에 최대공약수 값을 저장하도록 했습니다.

근데, 이렇게하면 아시겠지만 아주 큰수의 경우에 아주 오래 걸립니다. for 문 그냥 막 돌아야하니까요.

최대공약수 구하기 2 – 뺄셈이용.

이 방법을 유클리드(Euclidean) 방법인지는 모르겠습니다. 유클리드 방법은 나눗셈을 이용하는 방법인데, 이것을 뺄셈으로 변환한 것으로 보이거든요.

두 숫자가 있다고 합시다. 두 숫자를 관호에 넣고 왼쪽엔 큰 숫자, 오른쪽엔 작은 숫자를 넣습니다. 그리고 이 둘을 뺀 값을 제수로 넣습니다. 그리고 다시 큰 수를 왼쪽에 넣고 다시 빼고 나온 값을 다시 제수로 넣고 이를 반복하다 보면 나머지가 0일때에 피제수값이 나오는데 이게 바로 최대공약수 입니다.

(3654, 1365)

이 둘을 빼면 2289 값이 나옵니다. 그러면 3654(제수)를 버리고 다음과 같이 적습니다.

(2289, 1365)

다시 둘을 빼면 다음과 같이 나옵니다.

(924, 1365)

왼쪽에는 항상 큰 숫자여야 해서 이 둘을 교환합니다.

(1365, 924)

이것을 한눈에 알아보도록 표기를 하면 다음과 같습니다.

위와 같은 방법이 되고 마지막에 (0, 21) 이니까 두수의 최대공약수는 21 이 되는 것입니다.

이 방법이 유클리드 호제법과 같다는 이유는 뺄셈하는 방법이지만 제수를 항상 나머지로 다시 넣기 때문입니다. 유클리드 호제법은 나눗셈을 이용해서 나온 나머지를 다시 제수로 넣는 방법인데 둘은 같습니다.

(3654, 1365) = (2289, 1365)

이를 공식으로 쓰면,,,

3654 = 1365*1 + 2289

이는 3654/1365 를 나눈 나머지 2289 랑 같습니다.

여기서 규칙은 한가지, 두수를 비교해서 큰수를 왼쪽에 넣어준다 입니다.

최대공약수 구하기 2 – 나눗셈이용.

이를 유클리드 호제법이라고 합니다. 앞에 뺄셈을 나눗셈으로 바꿔서 하는 방법입니다. 이게 뺄셈보다 좋은 점은 반복적인 뺄셈을 없애줍니다. 규측인 뺄셈과 같습니다.

위와같이 while 문을 이용해서 할수도 있지만 재귀호출(Recusive) 로도 다음과 같이 구현할 수 있습니다.

최대공약수(GCD)를 구했는데, 1이 값으로 나온다면 이는 최대공약수가 없다는 것을 의미합니다. 1은 모든수의 공약수이기 때문입니다.

알고리즘 – 분수(Fraction) 문제

알고리즘 – 분수(Fraction) 문제는 컴퓨터 알고리즘을 시작하는데 좋은 예제입니다. 분수는 어릴적 산수시간에 배운 그게 맞습니다. 1/2, 1/3, 1/4 식 입니다.

분수에는도 사칙연산을 할 수 있습니다. 더하기(add), 빼기(subtract), 곱셈(multiply), 나눗셈(divide) 가 그것입니다. 이를 컴퓨터 프로그램 언어를 이용해서 만들어보는 겁니다.

참고: http://interactivepython.org/runestone/static/pythonds/Introduction/ObjectOrientedProgramminginPythonDefiningClasses.html#a-fraction-class

분수의 정의와 제약사항

분수는 다음과 같이 정의됩니다.

수학에서 분수(分數, fraction)는 a/b 이나  \frac {a} {b} 꼴로 표시한다. 이것은 a를 b로 나눈 값, 즉 a와 b의 를 뜻하며, 여기서 a는 분자b는 분모라고 한다. 이 때 분모 b에 0이 들어가는  \frac {a} {0}(a는 상수)라는 수는 정의될 수 없으므로 b0 이어야 한다.

From 위키페디아

중요한 것이 분모는 0 이여서는 안됩니다. 또 한가지 이 글에서 제약조건을 걸어야 하는데, 분자와 분모 모두 양수로만 이루어진 분수를 다룹니다. 또, 모두 정수여야 합니다. 이를 정리하면 다음과 같습니다.

  • 분모는 0 이여서는 안됩니다.
  • 분자, 분모는 모두 양의 정수(양수이며 정수)

분수의 덧셈

분수의 덧셈은 먼저 분모를 ‘통분’해야 합니다. 무슨말이냐 하면 덧셈을 하기 위한 두개의 분수들의 분모 크기를 같은 값으로 만드는 것(=분모를 통일하는것)입니다. 예를들어

1/2 + 1/3 이 있다면 분모를 통분하는데 서로서로 분모값을 분자,분모에 곱해주면 됩니다. (1*3)/(2*3) + (1*2)/(3*2) = 3/6 + 2/6 = 5/6

분모가 같아지니까 분자만 그대로 더해주면 됩니다.

분수의 뺄셈

분수의 뺄셈은 분수의 덧셈과 마찬가지로 분모를 통분해주고 분자까리 빼주면 됩니다.

분수의 곳셈

분자는 분자까리, 분모는 분모끼리 곳해주면 끝~

분수의 나눗셈

나누는 분수을 역으로 바꾸고 둘을 곱셈하면 된다.

2/5 나누기 1/3 = 2/5 * 3/1 = 6/5

여기까지가 분수에 관한 수학적 알고리즘입니다.

컴퓨터 알고리즘

컴퓨터 알고리즘은 컴퓨터를 이용해서 문제를 해결하는 방법입니다. 그럴려면 아무래도 프로그래밍을 해야하고 프로그래밍을 위해서는 프로그램 언어를 이용해야 합니다. Python, Java, PHP 등이 여기에 속합니다.

한가지 컴퓨터 알고리즘을 할때에는 선택한 언어의 특성을 이용하는 경우가 있습니다. 예를들어 Python 을 이용할 경우에 내장 메소드를 이용할 수 있는데, 이번 분수 알고리즘에서 이를 사용할 것입니다. 다른 언어로 구현할 경우에는 이러한 Python 의 내장 메소드 기능을 제공하지 않기 때문에 다르게 구현을 해야합니다.

이 말은 결국 컴퓨터 알고리즘을 구현하는데 사용하는 언어에 영향을 어느정도 받는다는 것입니다.

Python 의 특징(python3.4 기준)

Python 은 내장 메소드를 지원합니다. 이는 모든 데이터를 객체로 인식하고 레퍼런스하기 때문에 가능한 것입니다. 단순한 숫자조차도 다양한 메소드를 지원합니다.

위에 보시면 숫자에 대한 내장 메소드를 볼수 있습니다. 이 내장 메소드들은 특정한 연산을할때에 자동으로 작동합니다. 예를들어, ‘__add__’ 의 경우는 숫자를 더할때에 자동적으로 호출되어 작동합니다.

Python 에서 사칙연산에 관한 내장 메소드는 다음과 같습니다.

구현하기

Fraction 이라는 클래스를 만들고 내장 함수들을 조작함으로써 완성함으로써 완성됩니다.

먼저 두개의 숫자를 입력받는걸로 분수를 만듭니다.

그리고 덧셈 테스트를 해봅니다.

같은 클래스의 객체를 만들어서 덧셈을 해보면 저렇게 내장 메소드가 없다라고 나옵니다. 그러면 저 내장 메소드를 만들어주면 됩니다.

위와같이 덧셈 내장 메소드를 정의해주고 다음과 같이 테스트를 합니다.

잘 되네요. 뺄셈, 곱셈, 나눗셈은 앞에서 말한 방법대로 내장 메소드를 이용해서 구현하면 됩니다.

제약조건인 음수와 0에 대한 것을 예외로 처리하였습니다. 다음과 같이 실행 합니다.

마이너스(-) 표시가 마음에 안들긴하지만 일단 구현까지만하는 걸로..

Stack 알고리즘.

스택(Stack) 알고리즘.

흔희들 스택(Stack) 알고리즘을 가장 단순한 것으로 생각한다. 아니 다시말해서 가장 단순한 것으로 생각한 나머지 별 할일 없는 알고리즘으로까지 치부하는게 문제다. 하지만 스택 알고리즘은 가장 단순하면서 그 단순함으로 인해서 가장 강력하고 널리쓰이는 알고리즘이다.

스택(Stack) 을 말할때에 가장 먼저 떠오르는 것이 LIFO 다. Last-In First-Out. 가장 나중에 들어간 데이터가 가정 먼저 나온다는 것을 영어로 표현한 것인데, 이것을 다른 관점에서 생각해보면 역정렬 알고리즘에 일종이기도 하다.

reverse_order
Figure1. Reverse Order by Stack

스택에 넣었다 꺼내면 역정렬된 상태가 된다.

이를 잘 활용할 수 있는 것이 있는데, 진수 변환이다. 10진수를 2진수로 진수 변환할때를 보자.

Stack 알고리즘
Figure2. Stack 알고리즘

중학교때 배웠던 10진수를 2진수로 만드는 수학 방법이다. 이것을 자세히 보면 나머지로 나오는 것들을 스택에쌓아두고 역으로 뽑아내면 그것이 바로 이진수가 된다는 사실을 알 수 있다.

스택의 또 다른 용법에는 체커(Checker) 도 있다.

위는 간단한 PHP문법이다. PHP는 함수를 사용하거나 조건문과 같은 문법을 사용할때에 ‘{‘ 를 사용한다. ‘{‘ 로 열고 ‘}’로 닫는 식이다. 그래서 항상 쌍으로 존재하는데, PHP 컴파일러는 이러한 것이 오류가 없는지를 어떻게 체크를 할까?

다음과 같이 스택을 이용하면 간단히 체크할 수 있다.

Stack 의 괄호 체크.
Figure3. Stack 의 괄호 체크.

처음에 ‘{‘ 를 만나면 스택에 넣는다. 그리고 ‘}’를 만나면 스택에서 제거한다. 최종적으로 더 이상 빼내야할 ‘{‘ 이 없고 스택이 텅 비어있다면 PHP 컴파일러는 문법으로 쓰이는 ‘{‘ 가 제대로 사용되었다라고 판단한다. 그래서 위 PHP의 예제를 스택을 이용해서 체크해보면 ‘{‘ 가 스택에 하나 남게되어 PHP 문법에 오류가 있다는 것을 알 수 있다.