본문 바로가기

부분합(subsum) 문제 관련 정수 배열 N이 주어졌을 때 두 원소의 합이 특정한 값(T)이 되는 것을 찾는 방법에 대해 생각해보자. 예를 들면, N={-3, -5, 2, -2, 1}이고 T=-4라고 하자.모든 경우를 따져보는 방법 - O(N^2)해시 테이블을 사용하여 한 번만 읽으면서 찾는 방법 - O(N) (해시 테이블이 O(1)일 때)배열을 가리키는 2개의 인덱스(혹은 포인터)를 사용하는 방법 - O(N)이 글에서는 3번에 대해서 생각해보자. 먼저 정렬하면 N={-5, -3.. 더보기
인터뷰와 네트워킹 펜(UPenn)에서 인터뷰와 네트워킹에 대한 설명회(discussion)를 외국인 학생을 대상으로 열었다. 비록 학생은 아니지만, 내용이 도움될 것 같기도 하고 집에서 길만 건너면 있는 건물에서 열려서 소림이가 신청해주고 내가 대신 갔다. 엄청나게 새로운 것을 알게 된 것은 없지만, 인터뷰나 네트워킹에 도움이 될 실용적인 내용을 대단히 상세하게 알려줬다. 학부를 다닐 때는 취직은 너희가 알아서 능력껏 하라는 분위기였고,.. 더보기
그래프 색칠하기 구글 코드 잼 연습 문제를 오랜만에 풀어보았다. 사실 작년 12월 초에 풀다가 잘 안 풀려서 2달 정도 손을 놓았다가 다시 풀었다. 알고 보면 굉장히 간단한 문제인데, 접근을 엉뚱하게 해서 풀이만 복잡해지고 제대로 된 결과를 구할 수 없었다.문제 보기문제를 간단하게 서술해보자. 서로 함께 있으면 문제를 일으키는 쌍에 대한 정보를 준다. 과연 문제가 없이 사람끼리 모이도록 전체 사람들을 두 그룹으로 나누는 것이 가능한가?접근 방법은 다음과 같다. 각 .. 더보기
영어는 참 미묘하다. "성형 수술이 개성을 말살시킨다"라는 표현을 하고 싶을 때, '개성'을 표현하는 단어로는 individuality나 uniqueness, '말살'을 표현하는 단어로는 destroy 정도가 적절한 것 같다. Plastic surgery destroys the individuality (or uniqueness) and character in each person's face. 다음은 아래 밑줄에 들어간 단어는 무엇인가를 찾는 것이다. 보기는 inst.. 더보기
[2015.09.16] 전공 선택하는 법(?) 일주일에 한 번씩 참석하는 영어 수업의 두 번째 시간이었다. 오늘의 주제는 전공 선택하는 방법이었고, 이에 대해 여러 가지 이야기를 해보았다. 전공에 대한 열정(꿈)과 현실(돈) 중에서 무엇을 따라야 하는지, 전공에 대해 미리 알아보는 것과 그냥 닥치고 전공하는 것 중 어떤 것이 좋은지, 전공 선택에 부모의 의견을 따라야 하는지, 전공과 다른 일을 하는 것에 대해서는 어떻게 생각하는지 등등 다양한 내용이 오갔다. 다양한 경험을 하고 그중.. 더보기
[2015.05.05] 기록의 중요성... 파리행 비행기에서 네 편의 영화를 보았다. 오늘 누군가와 이야기하면서 그 네 편의 영화가 무엇인지를 설명해주다가 한 편이 도통 생각이 나지 않았다. '러브, 로지', '신의 한 수', '백 투 더 비기닝'만 생각이 났다. 마지막 한 편은 결국 생각해내지 못했다. '늙어서 기억을 못 한다', '머릿속 메모리 용량의 한계로 하나를 기억하면 하나를 잊는다'라고 결론짓곤 생각하기를 포기했다. 호텔에 돌아와서 네이버 영화에서 검색을 하고서야 마지막 한 편이 .. 더보기
[2015.05.04] 프랑스 파리 출장 오랜만에 떠나온 출장을 기념해서 간만에 쓰는 일기다. 파리 출장은 2011년 7월 이후 거의 4년 만이다. 출장가서 호텔 방에 들어오기까지 아무 일이 없기란 쉽지 않다. 오늘은 용케도 무사히 지나가는가 싶었다. 그러면 그렇지. 호텔 앞에서 택시 요금을 카드로 내는 데 문제가 발생했다. 카드리더기에 카드를 긁었는데, 212라는 오류가 뜬다. NON INITIALISE라는 프랑스말이 뜬다. 내 카드도 다 같은 오류다. 호텔에 .. 더보기
미국 서부 여행 회사의 지원으로 미국 서부 지역 여행(?)을 다니고 있다. 샌프란시스코에서 시작해서 로스앤젤레스, 어바인, 그리고 샌디에이고를 지나는 여정이다. 미 서부 지역은 날씨가 참 좋다. 더보기