[풀이] 초보 개발자 코드 트레이닝, Part 2: 알고리즘과 성능

초보 개발자 코드 트레이닝, Part 2: 알고리즘과 성능 이라는 웹 페이지에서 알고리즘에 대한 문제가 있어서 간단하게 풀이를 해 보았다. 풀이를 해서 응모를 트래백으로 해야 한다. 언어에는 제한이 없어서, php를 사용했다. 알고리즘과 성능이라고 되어 있는데, 솔직히 코드골프(http://codegolf.com) 같은 코딩을 최대한 압축하는 재미가 없다. 퀴즈가 요구하는 기본적인 바탕은 매우 중요한 부분인데, 많은 스크립트 언어들은 이 구현을 언어 자체가 지원한다. 그래서인지 내가 선택한 php도 대부분 지원을 해주고 있다. 우리가 프로그래밍을 할 때 기본적으로 마주치는 배열 또는 컬렉션에 대해서 잘 사용해야 하는데, 그런 부분은 생각하는 프로그래밍 같은 책에 잘 나와 있다. 아무튼 php로 해결한 풀이다.

퀴즈 1. 프로시저 Both 를 완성해 봅시다.

<?
$x = array(1,3,4,5,6,9,7);
$y = array(4,5,8,9,10,15,-1);
print_r( array_merge($x,$y))."\n";
print_r( array_intersect($x,$y))."\n";
?>

불행히도 php는 array 타입에 대해서 다양한 함수들이 존재한다. 만들 필요가 없다.

퀴즈2. 수행 속도를 높인 fastEither 를 만들어봅시다.

<?
$x = array(1,3,4,5,6,9,7);
$y = array(4,5,8,9,10,15,-1);
$aB = array_merge($x,$y);sort($aB);
$aE = array_intersect($x,$y);sort($aE);
print_r($aB)."\n";
print_r($aE)."\n";
?>

역시 이 퀴즈도 그렇다. 불행히도 php는 array 타입에 대해서 다양한 함수들이 존재한다. 만들 필요가 없다. 그래서 해당하는 코딩을 해 보았다.

<?
function fast_array_merge($x, $y) {
 $xS = count($x); $yS = count($y);
 $xP = 0; $yP = 0;

 while($xP<$xS && $yP<$yS) {
  if ($x[$xP]==$y[$yP]) {
   $aS[] = $x[$xP];   $xP++;   $yP++;
  } else if ($x[$xP]<$y[$yP]) {
   $aS[] = $x[$xP];   $xP++;
  } else if ($x[$xP]>$y[$yP]) {
   $aS[] = $y[$yP];   $yP++;
  }
 }
 if ($yP==$yS) return array_merge($aS, array_slice($x, $xP, $xS-$xP));
 else return array_merge($aS, array_slice($y, $yP, $yS-$yP));
}

function fast_array_intersect($x,$y) {
 $xS = count($x); $yS = count($y);
 $xP = 0; $yP = 0;

 while($xP<$xS && $yP<$yS) {
  if ($x[$xP]==$y[$yP]) {
   $aS[] = $x[$xP];   $xP++;   $yP++;
  } else if ($x[$xP]<$y[$yP]) $xP++;
   else if ($x[$xP]>$y[$yP])  $yP++;
   }
 return $aS;
}
?>

풀이가 길어졌다. 짧게 보이기 위해서 여러 줄을 한줄로.. 이 문제의 핵심은 O(N^2) 문제를 O(N)의 문제로 바꾸는 것이다. 성능은 당연히 n의 갯수에 제곱이냐 그냥 n에 비례하는냐의 차이가 될 것이다. n의 문제로 바꾸기 위해서 두개의 변수로 위치를 탐색하는 메모리를 추가 사용한다는 점 빼고는 좋다.

퀴즈 3. isSubstring 을 작성해 봅시다.

<?
$first = array('a', 'b', 'c');
$second = array('a', 'c', 'b', 'c');
$third = array('a','a', 'b', 'c');

var_dump(isSubstring($first, $second));
var_dump(isSubstring($first, $third));

function isSubstring($l, $r) {
 $cL = count($l);
 $cR = count($r);

 for($i=0;$i<$cR-$cL+1;$i++) {
  if (array_slice($r,$i,$cL)==$l) return TRUE;
 }
 return FALSE;
}
?>

내장 함수를 이용했다. 부분 문자열이 있는지를 구하는 것인데, 좀더 잘 만들어야할 듯 하다. 정규식 표현에서 사용할 수 있을 정도가 되어야 하는데, 시간이 나면 알고리즘을 내장 함수가 아니라 구현하는 것으로 변경해 봐야 겠다.


퀴즈 4. 프로시저 match 를 작성해 봅시다.

<?
$first = array('(', '[', '<', '{', '}', '>', ']', ')');
$second = array('(', '[', '<', '{', '>', '}', ']', ')');
$third = array('(', 'a', 'c', ')', '[', '{', '}', ']');
$str_m[0] = array('(', ')');
$str_m[1] = array('[', ']');
$str_m[2] = array('{', '}');
$str_m[3] = array('<', '>');

var_dump(match($first));
var_dump(match($second));
var_dump(match($third));

function match($cs) {
 global $str_m;
 $cnt_m = count($str_m);
 $cnt_cs = count($cs);

 $stack = array();

 for($i=0;$i<$cnt_cs;$i++) {
  for($j=0;$j<$cnt_m;$j++) {
   if ($cs[$i]==$str_m[$j][0]) array_push($stack, $cs[$i]);
   else if ($cs[$i]==$str_m[$j][1]) {
    if (array_pop($stack)!=$str_m[$j][0]) return FALSE;
   }
  }
 }
 return TRUE;
}

?>

조금 신경을 쓴 코드다. 괄호를 어떻게 지정할 것인지에 대해서 미리 정의를 해 두어서 확장성을 고려했고, 비교 루틴을 간략화했다. 간단하게 stack 을 사용했다. 꽤 간결해진 듯 하다.