알고리즘 문제 풀이 전략

jrcfore***l2017-11-15

[한빛미디어] 알고리즘 문제 풀이 전략

blackd***l2016-07-08

알고리즘과는 참 안친한 JAVA 개발자가 보는 알고리즘 문제 풀이 전략

■ [주요 포인트].

미리 말씀드리자면, 저처럼 수학에 약하신 분은 조금 각오하고 시작하셔야 할 듯 합니다. 1부의 경우에는 그래도 대학생때 들은 수업시간의 기억을 어렴풋이 더듬어서 진행해보았지만, 2부부터는 슬슬 멘탈(..)이 부서져 내리더군요.
(고백하자면 16, 17장에 이르러서는 거의 눈물날것 같다 싶은 마음으로, 개념만 훑어보았습니다.
스스로의 개념 부족을 절절히 체감하였습니다.)
개인적으로는 그래도 프로그래밍(C언어-배열, 포인터, 구조체)에 대한 기본 개념은 터득하고 계셔야 알고리즘을 풀어나가는 코드 부분을 이해하실 수 있을 듯 합니다.
(아 물론 C언어에서 포인터가 나오기 시작하면 많은 예비 개발자들이 진땀흘린다는 것을 감안하면,
단순히 논리적으로 알고리즘에 대한 개념 파악이 아닌 코드로 풀이하는 부분은 조금 난이도가 있는듯 합니다.
지금 이 포스팅을 진행하는 저도 C언어 한지가 몇 년이 된 경우인지라, 처음에 어..라? 하고 조금 진땀 흘렸습니다.)
책의 진행 중에서 알고리즘을 실제 풀이하는 부분에 들어가면, 입력과 출력이라고 하여 어떤 형식으로 진행될지 예시가 나옵니다.
ex) 입력 데이터 T개의 테스트 케이스로 이루어져 있고,T는 파일 첫 번째 행에 주어진다.
그리고 실제 입력되는 파일의 내용이 보여집니다.
2
5
1 3 5 3 0
조건에서 주어지는 변수가 늘어나면, 이 숫자가 무슨 변수에 대입된거더라(물론 책의 진도를 따라 진행하다보면, 규칙성이 보이기 시작합니다만) 하고 조금 헷갈리기 시작합니다.
제시된 파일의 입력 데이터 옆에는 상당한 양의 여백이 보이는데, 이 부분에 이 숫자가 어떤 의미의 변수 값으로 대입된건지 적어가며 이해하려 노력하면 책의 진도를 진행하기에 조금 더 용이합니다.
뒷 부분으로 책을 넘기다보면 소스 양이 점차 길어지기 시작합니다(살짝 울고싶어집니다. 3년차 개발자라고는 하나 업무와 관련된 로직 분기와 같은 부분만 익숙하지, 알고리즘이 담긴 C 언어의 정수(?)를 보면 눈앞이 깜깜해지더군요. 간혹가다 보이는 저자의 한마디 - "간단하다"라는 말은 충분한 멘탈붕괴를 일으키죠.).
그래도 걱정마세요(지금 읽고 계신 분만 어려운건 아닙니다. 최소한 저도 있으니까요! 한빛미디어 사이트에서는 해당 도서를 초급으로 분류하고 있습니다만.. 괜찮아요. 힘내요. 우리..).
소스의 일정 부분은 배열의 초기화와 파일 읽기와 같이 중복되는 부분도 적지않게 존재하니까요.
실제 알고리즘 대회를 준비하시는 분들을 위한 팁도 곳곳에 존재합니다.
개인적으로는 알고리즘 대회때 길이를 구하는 함수 같은 것을 사용하면 안되는 경우도 있다는 것은 처음 알았습니다.
(알고리즘 대회라는 것 자체를 엄두도 내지 않았었지만요)
오타가 조금.. 상당량 존재합니다
(..만 개정되겠죠. 그 부분을 감안하더라도 읽을 가치가 상당합니다.)

■ [총점 및 평론].

오타가 상당량 존재한다는 점이 꽤나 아쉬웠습니다.

하지만 그것을 감안하더라도,
개발자로써 한번쯤은 이 악물고, 울고 싶은 기분일지라도 끝까지 읽어볼 가치가 충분하다고 확신합니다.

다만 한번만 읽어서 될 책은 절대 아닌듯 합니다.(알고리즘과 안친하셨던 보통의 IQ를 지닌 분들은 동의해주시리라 믿고싶습니다..).

개인적으로는 올해 들어서 읽은 책 중 가장 난이도 있는 책이었습니다.

msq***l2016-07-08

C언어로 배우는 가장 쉬운 알고리즘 입문...

일부 개발자들과 알고리즘 대회 출전을 준비하는 분들에게만 필요한 것으로 여겨지던 알고리즘이, 면접과 이직시에 개발자들의 능력을 평가하기 위한 도구로 많은 회사에서 사용되는 분위기가 꽤 오랜시간 이어져 오고 있다. 책 제목에 "알고리즘 테스트 시대가 온다!", "프로그래머의 취업, 이작을 결정하는" 내용이 적혀 있는 것도 해당 트렌드를 반영한 것일 것이다.

책은 기본적인 알고리즘에 대한 의미, 측정방법등을 설명한 후에 바로 C언어를 이용한 자료형, 배열, 포인터등을 설명한다. 전반적으로 C언어를 이용하고 있기때문에, 예전 처럼 C언어를 기본으로 배우는 세대가 아닌 분들을 위해 다른 언어에도 있는 제어문이나 금방 익숙해질 부분은 생략하고 C언어에 익숙해지는데 필요한 자료형, 배열, 포인터를 설명하는 것이 지면의 낭비를 막은 것 같았다.

실제로 한 문제를 실행하는데 걸리는 실행시간과 사용하는 메모리를 제한하는 대회에서는 C언어나 C++을 주로 사용한다고 하니, 적절하다고 할 수 있다.

필수 자료구조인 링크드 리스트, 스택, 큐를 학습 한 뒤에 기본 자료구조의 개념을 이용해 트리를 살펴본다. 특별히 많은 용도로 사용되는 이진트리에 대해서는 부가적인 내용이 충실히 언급되어 있다.

가장 많이 나오는 정렬 알고리즘에는 선택, 삽입, 버블, 셸 정렬 알고리즘이 모두 설명되고 있고, 추가적으로 퀵정렬, 기수정렬, 병합정렬, 힙정렬까지 많이 언급되는 정렬 알고리즘은 모두 설명되고 있다는 생각이 들었다.

이진 검색 알고리즘과 해시 알고리즘을 마지막으로 알고리즘 문제를 해결하기 위한 기본기를 학습하는 것을 마무리 한다. 거의 책의 절반을 나눌때 앞에 언급한 기본기 학습 부분이 전반부이고, 후반부는 실제 문제를 통해서 알고리즘 문제를 푸는 감각과 능력을 키우도록 구성되어 있다.

몸풀기 알고리즘 문제는 정말 쉬운 코딩 문제들로 이루어져 있어서 알고리즘 문제에 대해 두려움이 있다면 조금은 날려버리는 시작이 될 수 있을 것이다.

그 이후 차근 차근 많은 알고리즘 문제를 다루는데, 대회에서도 많이 사용되는 탐욕법(Greedy),

분할 정복(Divide and Conquer), 동적 계획법, 백트래킹(Back tracking) 등을 익힐 수 있도록 골고루 문제가 배분되어 있고, 부록으로 Visual Studio 설치법을 알려주는 것으로 책은 마무리 된다.

이 책의 가장 큰 장점은 쉽다는 것이다. 단계별로 잘 구성되어 있고, 바로 결과를 확인 할 수 있는 짧은 예제들로 이루어져 있는 점이 장점이라고 할 수 있다.

책의 후반부에 몰려 있는 알고리즘 문제들의 해답들도 평균적으로 공백이나 Bracket만 있는 줄을 포함하고도 60~80줄이라서 따라서 입력하고 이해하는데 어려움이 없는 적절한 소스 크기로 구성되어 있다.

가장 마지막인 영역의 크기 문제와 식인종과 연구원 문제만 각각 110줄, 207줄이다.

면접이나 대회의 알고리즘 문제를 해결하기 위해서는 언어 하나는 정말 잘 다룰 수 있어야 하고, 연습이 많이 되어 있어야 하므로 책의 모든 소스가 한빛미디어 홈페이지에 59MB의 압축파일로 전부 올라와 있지만, 길지 않은 소스 이므로 직접 입력하면서 익숙해지는 것을 추천하고 싶다. 소스 중에 오탈자로 등록된 부분도 있으므로 홈페이지에서 미리 확인하면 시간을 절약할 수 있을 것이다.

책의 단점이자 아쉬운 점이라면, 앞에 시작할때 알고리즘의 평가를 초반에 설명을 하긴 하지만, 실제 알고리즘 문제풀이에서는 사용하는 메모리나 속도에 대해서는 큰 언급이 없다는 점이다.

실제 대회나 면접에서는 거의 실행 조건이 주어지기 때문에 해당 부분도 항상 언급하면서 문제 풀이과정에 보태졌더라면 더 좋았을 것이라는 생각이 든다.

또한 8개의 정렬을 소개하는데, 각각 대표되는 정렬들을 마지막에 표와 시각적으로 wrap-up할 수 있는 내용이 추가되면 정리가 더 잘될꺼 같다.

이 책은 전혀 프로그래밍을 모르는 분들이 보기에는 어렵지만, JAVA나 다른 프로그래밍 언어를 알 고 있는데 C로 알고리즘을 접근하고 싶다면, 이 책이 가장 쉬운 접근이 되지 않을까 생각한다.

본 서적을 다 읽은 후에는 더 많은 알고리즘 문제를 풀어 보고 싶은 생각이 들 것 같다.

him***l2016-07-08

알고리즘 문제 풀이에 도전하라

프로그래밍을 공부하다 보면 항상 이런 의문이 생깁니다. "과연 알고리즘을 따로 공부해야 내가 원하는 프로그램을 만들 수 있는 것 일까?" 이 질문에 대한 정답은 없겠지만, 알고리즘을 공부하는 과정에서 얻는 경험이 프로그램을 효과적이고 효율적으로 만드는데 도움이 된다는 사실은 부정할 수 없을 것 입니다.

시중에는 이미 많은 알고리즘 책이 나와있고, 저 또한 2권의 알고리즘 책을 보유하고 있지만, 끝까지 집중력을 잃지 않고 보기란 쉽지 않았습니다.

이 책은 그러한 일반적인 알고리즘 전문 서적의 단점을 해결한 것으로 보입니다. 단순히 알고리즘을 소개하는 것에 그치는 것이 아니라, 공부한 알고리즘을 활용하는 방법도 같이 제공하고 있는데, 바로 정보올림피아드나 IT기업 취업시 면접에 나올법한 문제를 제시하면서 독자의 도전 의식을 불러 일으킵니다.

이 책은 제목 부터 '알고리즘 문제 풀이 전략'인데, 책의 많은 부분을 실전 알고리즘 문제 풀이에 할애하고 있습니다. 이러한 책의 구성, 깔끔한 편집, 많은 그림 및 친절한 설명이 집중력을 잃지 않고 이 책을 읽는데 도움이 되었습니다.

다만, 책의 예제가 C언어로 되어 있어서, '기본적인 C언어'를 알고 있어야 합니다. 포인터, 배열 등의 개념에 대해서 잘 모르더라도 괜찮습니다. 이 책에서 별도로 자세히 설명하고 있으므로, 'Hello world'를 화면에 출력할 수 있는 정도면 충분한 것 같습니다.

끝으로 이 책의 서문에 제시된 학습 로드맵을 잘 챙겨보시면, 알고리즘 공부의 전체 흐름을 확인할 수 있는 것은 물론이고, 학습 능률 향상에 큰 도움이 되는 것 같습니다.

chars***l2016-07-08

기본기를 탄탄하게 만들어주는 책

해당 리뷰는 “한빛미디어”에서 제공하는 도서를 이용하여 리뷰를 진행하였습니다.

이 책의 제목은 미사여구를 포함해서 "프로그래머의 취업, 이직을 결정하는 알고리즘 문제 풀이 전략" 입니다. 솔직히 말해서, 국내는 알고리즘 문제를 이용해서 기술 면접이 이루어지는 곳이 엄청 많지는 않습니다. 그리고, 약간 면접관에 의해서 케이스 바이 케이스인 경우도 많구요. 다만, 이제 점점 전화면접이나 온라인 홈워크나 문제 풀이를 이용해서 지원자를 스크리닝 하는 경우는 점점 늘어나고 있습니다. 다만, 외국의 특정 G사, F사 처럼 문제 풀이만 시키는 형태가 되기에는 아직은 시간이 걸릴듯 합니다.

아픈 기억이지만, 저도 실제로 알고리즘 문제만 푸는 면접을 2012년에 본 적이 있습니다. 이렇게 아픈 기억이라고 얘기하는 건, 똑 떨어졌다라는 이야기입니다. 5시간 동안 알고리즘만 풀면... 머리가 안돌아가는...

다시 책 이야기로 돌아와서, 이 책은 크게 두 부분으로 구성되어 있습니다. 기본적인 자료구조/알고리즘 부분...(C코드로 되어있는...) 나머지는 실제로 문제와 그에 대한 해답입니다. 개인적으로 이 책의 최대 장점은 문제 부분보다는, 앞쪽에 잘 정리된 자료구조/알고리즘 부분입니다. 이미지를 통해서 실제로 단계별로 어떻게 이렇게 진행되는지에 대해서 자세히 설명되어 있습니다.(간단한거는 그냥 쉽게 훅 넘기기도 합니다. ㅎㅎㅎ)

보통 알고리즘 문제를 내는 곳도 엄청 어려운 문제를 내지는 않습니다. 그리고 정답을 맞추는 것보다 정답을 맞추어가는 과정을 중요시합니다. 그래서 실제 이런 문제를 풀 때는, 자신이 생각하는 과정과 풀이 과정을 계속 면접관과 맞추어가는 것이 중요합니다.

그래서 어떤 자료구조를 선택하고 알고리즘을 선택할 것인가에 대해서 기본기가 튼튼해야 하는데, 이런 부분이 잘 갖춰져 있다는 겁니다. 그리고 문제를 다 풀어보는 것도 꽤나 도움이 될듯합니다. 실제로 같은 문제가 나오지는 않겠지만...(craking code interview 라는 책이 있는데, 인사이트에서 "코딩 인터뷰 완전분석" 이라고 번역되어 나왔습니다. 외국에서 이 책은 거의 취업쪽 바이블로 통하는...) 문제를 풀어보고 연습해 둔다는 것이 상당히 중요합니다. 실제 외국에서도 이직을 할려면 이런 쪽 문제랑 공부를 대략 6개월 정도 합니다.

사실 제가 약한 부분이던, 전위/중위/후위 순회라든지, 정렬쪽이 상당히 설명이 잘 되어있어서 좋았습니다. 여러 책을 보시겠지만, 앞에서 언급한 책과 함께 보시면 좋을듯 합니다.

알고리즘 문제 풀이 전략

자료 다운로드시 유의사항

▶ 부록/자료 관련 FAQ