태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

잘하고 싶은 마음은 굴뚝 같지만, 나는 알고리즘에 굉장히 취약하다. 학부 때 중간고사에서 바닥을 깔아 전공 공부에 심각한 회의를 들게 만든 과목이 바로 알고리즘이었다. 안에서 새는 바가지 미국에서도 샌다고 마지막 학기라 단 한 과목만 들었던 학기였음에도 여기에서도 (아마도) 꼴찌였다.

머리가 나쁜 것이 원인이라고 말하고 웃어넘길 수 있겠지만, 알고리즘을 새롭게 디자인하는 것도 아니고 알려진 알고리즘을 활용하여 프로그램을 작성하는 수준이라면 왜 나는 못 하는 것일까? 이번 기회에 구체적으로 원인을 따져보면 해결책이 있지 않을까 해서 글을 써본다. 떠오르는 문제가 크게 3가지 있다.

첫째, 재귀적 사고력(recursive thinking)이 부족하다. 많은 문제가 재귀(recursion)로 풀면 쉽게 풀린다. 회사에서 문제 풀이(problem solving)를 한 적이 몇 번 있다. 여기에서 나는 놀란 점이 사람들이 꽤 재귀적 사고에 익숙하다는 점이었다. 재귀 방식의 장점은 풀이가 직관적이라는 것이다. 그런데 나는 그것이 쉽게 되지 않는다. 풀이를 보고 쉽게 이해되지도 않는데, 내가 그렇게 프로그램을 짜는 것이 얼마나 어려운 것인지는 말 안 해도 알 것이다.

둘째, 고집과 아집으로 인해 다른 접근 방식을 생각해보지 않는다. 물론 초기에는 이러저러한 접근 방식을 고려하지만, 어느 정도 방향이 보일 때 접근 방식에 대한 더 이상의 유연함이 없다는 점이 큰 문제이다. 정답이 다른 접근 방법으로 풀었고 훨씬 간단할 때 뼈져리게 느낄 수 있다. A 접근으로 해결책이 나오지 않으면, B 접근은 없을지 생각해보아야 하는데 그러지 않는 경우가 많다.

셋째, 세심하지 못하다. 경계 검증(binary check)을 참 못한다. off by one error와 같은 기본 문제를 발생시키지 않는 경우가 없다. 문제에 대한 해결책이 떠올라도 실제로 돌려보면 오답이 나오는 경우는 십중팔구 이 문제를 해결하지 못해서다. 툭하면 배열 인덱스를 벗어나 런타임 오류를 발생하는 원인이다.

위 문제들을 해결하는 방법이 딱히 있는지 모르겠다. 셋째의 경우 의도적으로 종이에 써서 하나씩 알고리즘을 완성하고 경계 검증까지 해보려고 하는데 그것도 쉽지 않고, 수차례 해서 오류가 나면 짜증이 날 뿐이다. 침착하고 정확하게 하기보다는 대충 빨리 풀고 오류를 고쳐나가는 try and error 방식으로 모든 문제를 풀어왔던 게 이런 문제를 일으킨 하나의 문제이기도 하다.

그렇다고 손 놓고 있을 수는 없으니, 앞으로 오랜 시간에 걸쳐 공부해나가면서 개선되는 점이 있으면 그러한 방법을 공유해 보도록 해야겠다. 나처럼 머리가 나빠서(?) 알고리즘과 같은 문제를 풀어내고 싶은데 고생하는 사람들이 많이 있을 테니 말이다.

정수 배열 N이 주어졌을 때 두 원소의 합이 특정한 값(T)이 되는 것을 찾는 방법에 대해 생각해보자. 예를 들면, N={-3, -5, 2, -2, 1}이고 T=-4라고 하자.

  1. 모든 경우를 따져보는 방법 - O(N^2)
  2. 해시 테이블을 사용하여 한 번만 읽으면서 찾는 방법 - O(N) (해시 테이블이 O(1)일 때)
  3. 배열을 가리키는 2개의 인덱스(혹은 포인터)를 사용하는 방법 - O(N)

이 글에서는 3번에 대해서 생각해보자. 먼저 정렬하면 N={-5, -3, -2, 1, 2}가 된다. 두 개의 인덱스(low, high)를 사용한다. low는 첫 번째 원소, high는 마지막 원소를 가리키는 인덱스를 저장한다. 각 인덱스가 가리키는 원소의 합(S)을 구해본다. 목푯값인 T와 비교하여 T<S이면 high 값을 감소시킨다. 원소의 합이 목표치보다 크기 때문에 합(S)을 줄여야 하기 때문이다. 마찬가지로, T>S이면 low 값을 증가시킨다. 원소의 합이 목표치보다 작으므로 합(S)을 키워야 하기 때문이다. 이러한 과정을 low<high를 만족하게 하는 동안 수행한다.

위의 예로 값을 구하는 과정을 살펴보면 아래와 같다.

N[low] N[high] S   
----------------------------------
-5     2       -3  (T<S, high--)
-5     1       -4  (T=S)

조금 더 문제를 확장해서 두 원소의 합이 T에 가장 가까운 경우를 찾는다고 해보자. 이 경우에도 비슷한 방식으로 하는데, S와 T의 차의 절댓값이 최소가 되는 정보를 유지해야 한다. 절댓값이라는 개념이 들어가는데도 위와 같은 식으로 하는 게 처음에는 잘 이해가 안 되는데 결국 S가 T에 가까워지는 방향으로 가려면 T>S일 떄는 low++, T<S일 때는 high--을 해야 한다.

펜(UPenn)에서 인터뷰와 네트워킹에 대한 설명회(discussion)를 외국인 학생을 대상으로 열었다. 비록 학생은 아니지만, 내용이 도움될 것 같기도 하고 집에서 길만 건너면 있는 건물에서 열려서 소림이가 신청해주고 내가 대신 갔다.

엄청나게 새로운 것을 알게 된 것은 없지만, 인터뷰나 네트워킹에 도움이 될 실용적인 내용을 대단히 상세하게 알려줬다. 학부를 다닐 때는 취직은 너희가 알아서 능력껏 하라는 분위기였고, 대학원을 다닐 때는 내가 부지런하지 못해서 이런 프로그램의 도움을 받지 못했던 것이 아쉽다.

아래는 오늘 내용을 간단하게 정리한 파일이다. 대답하려면 충분히 미리 생각해보고 준비해야 할 질문이 많다.

interview_networking.pdf

'[아는게 힘이다] > [강의/강좌]' 카테고리의 다른 글

A good taste in code (리누스 토발스)  (0) 2016.04.12
인터뷰와 네트워킹  (1) 2016.02.24
  1. 소림 2016.02.29 14:00 신고

    아주 일목요연하게 잘 정리해줘서 고마워요^^ 역시 자기님은 멋지네요!!

구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 12월 초에 풀다가 잘 안 풀려서 2달 정도 손을 놓았다가 다시 풀었다. 알고 보면 굉장히 간단한 문제인데, 접근을 엉뚱하게 해서 풀이만 복잡해지고 제대로 된 결과를 구할 수 없었다.

문제를 간단하게 서술해보자. 서로 함께 있으면 문제를 일으키는 쌍에 대한 정보를 준다. 과연 문제가 없이 사람끼리 모이도록 전체 사람들을 두 그룹으로 나누는 것이 가능한가?

접근 방법은 다음과 같다. 각 사람을 vertex로 하고, 서로 문제를 일으키는 사람 간에 edge가 존재하는 그래프를 생각한다. 그리고 각 vertex를 둘 중 하나의 색으로 칠하는데, edge로 이어진 두 vertex는 서로 다른 색이어야 한다.

처음에는 모든 vertex에 색이 없다. 칠해지지 않은 한 vertex를 선택하고, 그 vertex를 시작으로 BFS를 통해 연결된 vertex를 조사한다. 이때 이 vertex는 1) 색이 없는 상태 2) 연결될 수 없는 같은 색이 있는 상태 3) 연결될 수 있는 다른 색이 있는 상태 중 하나이다. 1)의 경우에는 다른 색을 칠하고 그것과 연결된 vertex들을 조사하게 한다. 2)의 경우 두 그룹으로 나눌 수 없다는 결론을 낸다. 3)의 경우 이 vertex에 대한 조사는 중단한다. (이미 이것과 연결된 vertex에 대한 조사는 끝났기 때문) 

BFS 과정에서 찾아지는 vertex가 없으면, 칠해지지 않고 남아 있는 vertex로 앞의 작업을 반복한다. 문제없이 모든 vertex를 칠할 수 있으면 두 그룹으로 나눌 수 있다.


"성형 수술이 개성을 말살시킨다"라는 표현을 하고 싶을 때, '개성'을 표현하는 단어로는 individuality나 uniqueness, '말살'을 표현하는 단어로는 destroy 정도가 적절한 것 같다.

Plastic surgery destroys the individuality (or uniqueness) and character in each person's face.

다음은 아래 밑줄에 들어간 단어는 무엇인가를 찾는 것이다. 보기는 instinct/instinctual/instinctually였다.

It would be an ___________ panicked move with no forethought or malice.

일단 수업 시간에는 instinctually라고 했는데, 나는 instinctual이 답이 될 수 있지 않으냐는 의문을 제기했다. 이유로는 instinctual이 panicked의 앞에 있기는 하지만, move를 서술하는 형용사가 오는 것으로 보는 것이 옳다고 생각해서였다. 일단 원어민 선생님(TESOL 학생)이 instinctually라고 했고, instinctually가 의미상으로 panicked를 수식하는 것으로 봐야 한다고 했다.

물론 big red roses와 같이 두 개 이상의 형용사가 붙는 경우도 있는데, 이렇게 여러 형용사가 명사를 수식하는 경우에는 일반적으로 콤마(,)를 사용한다고 한다. 집에 와서 구글에 그 문장을 쳐보니 instinctual이 답이다. 아무래도 instinctual move와 panicked move에서와같이 둘 다 move를 수식하는 것으로 보는 것이 옳은 것 같다.

다음으로 minimum과 minimal에 대한 구분 문제가 있었는데, minimum은 명사라서 뒤에 명사가 오지 못한다고 하던데, minimum value와 같은 단어를 그동안 많이 봐왔기 때문에 이상했다. the minimum value와 같이 관사를 말이 된다고 하는데 정확한 설명이 부족했다. 좀 더 생각해보고 다시 정리해봐야겠다.

+ Recent posts