최고 엔지니어의 꿈을 향해서

'Computer Science/Algorithm'에 해당되는 글 2건

  1. 2009.11.02 간단한 알고리즘 1
  2. 2009.11.02 알고리즘...

얼마 전, Daum 기술시험을 보게되었는데, 섹션1, 2 로 구성되어 있었다. 1은 간단한 단답형, 리팩토링, 코드 결과값, SQL쿼리문 작성, Unix명령어 조합 등이였다. 섹션 2는 비중이 더 컸는데, 알고리즘 3문제 였다.
첫번째 알고리즘 문제는
정수값을 받으면 역순으로 리턴하는 함수 코드를 작성하는 것이였다. 배열, 메모리같은 것은 쓰지말라는 조건이 있었다.

ex) 입력 12345  출력 54321
     입력 2340    출력 432
     입력 541     출력 145

recursion으로 해결하려 했으나, 그냥 iteration으로 짜보았다. 먼저 정수형의 자릿수를 /10 연산으로 구한뒤 그 자릿수만큼 %10 으로 뒷자리를떼넨후 그 결과값에 10000,1000, 100, 10 등을 곱한후 총 결과를 더하면 역순이 나온다. 시험장에서 생각한거기 때문에 좋은알고리즘인지는 잘 모르겠다. ;;

문제 2번은 스트링 패턴 관련 문제가 나왔다
가령 abcdabc는 abc가 겹치므로 문자열 길이 3을 리턴
       abcdefef 는 ef가 있으므로 2리턴
       aaaaaa 는 aaa가 있으므로 3을 리턴

;;
관련 알고리즘을 모르면, 그냥  a부터 일일이 검사하고 b하고 ab하고 ㅋㅋ ;;;;;

세번째 문제는 선분에 점들이 있을때 가장 가까운 거리를 구하는 것인데 분할정복을 이용하여 해결하라는것이다.
이것은 데이타를 일단 반으로 확 쪼갠후에 ...검사를 한다. 점이 두개인지..두개면 뒤에서 앞에를 빼서 값을 저장한다.
아니면 개속 반토막 낸다. 주의할 점은 반토막 낼때..그 반토막 낼때의 경계값을 나중에 다시 한번 검사해줘야 한다는 것이다.

--3--56---10--

이렇게 점 4개가 있다면 답은 6-5 = 1 이 답인데..
두동강이 낼때 (3, 5)  (6, 10) 이렇게 내서 각각 빼면 2, 4 인데 여기서 min(2, 4) 하면 2가 나온다.
저기 최소값을 경계값 (5, 6)하고 비교를 한번 더 해주는것으로 알고리즘을 생각해 보았다.

Divide and Conquer의 주의점은, 데이타의 싸이즈만 줄이는 것인지, 싸이즈를 줄이면서 문제도 계속 해결해 나가는지, 싸이즈를 줄여나갈때 누수점은 없는지..등을 체크해 보아야 한다.


Posted by 정해권 Trackback 0 Comment 0
알고리즘은 워낙 방대한 분야라서, 시간이 날때마다 조금씩 글을 올리도록 하겠다. 기본적으로 알고있어야 할 소팅, 서치 알고리즘부터 응용 알고리즘까지..다양하게 다뤄보도록 하겠다.

무엇보다 내가 생각하기엔, 테크닉적인 방법의 기억도 중요하지만, 기본이 되는 원리 이해부터 하는것이 중요하다고 생각한다.

알고리즘 영역에서 빠질 수 없는 기본적 컨셉들이 있는데 우선 Recursion에 대해 완벽히 이해 해야 할것이며, 그 다음으로 Divide and conquer, 깊이우선 탐색(DFS), Back tracking, Dynamic programming 등의 굵직한 개념 이해가 필요할 것이다. 이런 원리를 이해 한 후 텍스트 관련 알고리즘, 그래프 알고리즘, 프랙탈, 기하 관련 등등의 분야를 다루어 보면서 기본 알고리즘이 어떻게 응용되고 코딩되는지 하나하나 체득해 가는것이 중요하다.

물론 분야에 맞는 최적화된 알고리즘들은 대부분 인터넷에서 쉽게 찾아 활용할 수 있을것이다. 그러나 알고리즘을 직접 구현해 보고 연구해보면 기본적인 문제 해결력이 배양된다. 다양한 알고리즘을 구현해보다보면, (세일즈맨 문제, 가방채우기, nqueen문제 등등) 프로그래밍 실력도 향상될 뿐만 아니라, 새로운 문제에 직면했을때에도, 자세히 들여다보면, 기존 이미 알려진 문제와 흡사하다는 것을 깨닫고, 기존 학습한 방법으로 코딩을 할 수 있게 된다.

알고리즘을 너무 지루하게 생각하지 말고, 퍼즐 문제 푸는 것처럼 생각하면, 재미있어 진다. 알고리즘에 재미를 붙이기 위해 먼저 읽어 봐야 할 책들이 있다.

임백준 님이 지으신 씨리즈 모조리 다 읽어보면 좋다. 책이 너무 소설처럼 쓰여있어서, 정말 재밌다. 누워서 읽는 알고리즘부터 시작해서 요즘에 출간한 책들도 있을텐데 이름은 기억이 안난다.  책에서 다루어 지는 주제들이, 딱딱하지 않고 매우 이해하기 쉽고 재미있게 풀어 쓰셨다. 알고보니 인디애나 선배님 이셨다. 역시 ㅋㅋ

두번째는 생각하는 프로그래밍이다. 원제목은 Programming Pearls 2nd Edition 이고 존 벤틀리 형님께서 지으셨다. 실용적이면서 알아두면 좋을 만한 알고리즘을 다양한 분야에 걸쳐 소개 하고있다. 연습문제들도 있는데 다 풀수 있다면 진정한 geek으로 갈 수 있다. 공간과 속도의 반비례 관계를 잘 풀어서 설명하였다.

세번째는 한국에서 컴퓨터 공부하는 사람이라면 누구나 읽어본 C로 배우는 알고리즘 이재규 형님이 지으신 책이다. 자료구조 뿐만아니라 알고리즘에 대해 설명히 상당히 깔끔하고 잘 되어있다. 나도 지금까지 가장 많이 읽어본 책중에 하나인데, 공부 하면 할수록 이책 정말 잘 만들어 진 책같다.

네번째는 ACM 대비용으로 만들어진 Programming Challengers 라는 책이다. 문제 주고 코딩하라는 식으로 되어 있으며 해설지도 포함되어 있다. 이 문제를 하나하나 풀어보면, 정말 많은 도움이 되고 프로그래밍 신의 영역에 도달할 수 있다. 또한 카테고리별로 분류가 되어있어 나중에 쉽게 참조할 수도 있다.

이런책 외에도 다양한 명서들이 있지만 위에 책들은 부담없이 볼 수 있는 책들이라 소개하였다.

앞으로 하나하나 올려보도록 하겠다.


Posted by 정해권 Trackback 0 Comment 0


티스토리 툴바