numpy에서 indexing 연산은 생각보다 많이 써먹곤 했습니다. 그런데 numpy의 indexing에 걸리는 오버헤드가 어마어마하다는 것을 최근에야 알게 되었습니다. 상세 분석에서 분석할 기회가 있을 듯 싶습니다만 언제 할 지는 모르겠습니다. 여기에서는 간단하게 문제 상황을 정의하고, 어떻게 개선해야 하는지만 주로 잡도록 하겠습니다. 먼저 문제 상황을 정의해 보겠습니다. 간단한 점화식이 있습니다. 이 때, dp[19999]를 구하는 게 제 목적입니다. 누적합을 이용해서 매우 쉽게 풀 수 있지만, 저는 dp[n]을 구하기 위해 dp의 0번째 인덱스에 있는 값부터 n-1번째 인덱스에 있는 값까지 모두 접근을 한 다음에, 이들의 합을 계산해서, mod로 나눈 나머지를 취할 겁니다. 그리고, 이 값을 다시..
전체 글 검색 결과
이펙티브 자바를 보다 보면, 표준 예외를 사용하라는 item이 있습니다. 여기에 언급되는 exception들을 보면 Collections에서도 자주 보이는 예외가 몇 개 있는데요. 이번 시간에는 이 중에 UnsupportedOperationException에 대해서 보도록 하겠습니다. 저번에 예를 들었던 것 중에, CopiesList를 들고 오겠습니다. 이것은 AbstractList를 상속받는다고 되어 있어요. 명세를 보면, immutable list를 리턴한다고 되어 있어요. 저번에 본 바로는 CopiesList가 Collection 내부에 private 클래스로 되어 있었어요. 그리고, 계속 읽어보면, n copies of the specified Object라고 되어 있는데요. 특수 오브젝트의 n개..
안녕하세요. 이번 시간에는 java string에 있는 trim 함수에 대해 알아봅시다. trim은 보통 문자열의 앞과 뒤에 붙어 있는 공백을 제거하기 위해서 쓰는 경우가 많습니다. 공백, 아니면 tab을 제거할 때요. 코딩 테스트에서는 이 정도에서 해결을 볼 수 있는 경우가 대다수입니다. 여기까지는 별 문제 없어 보입니다. 그런데, 저는 이 글을 상세 분석에 쓰고 있습니다. 이렇게 간단한 메서드를 왜 상세 분석에 쓸까요? 질문 하나 드리겠습니다. trim은 문자열의 맨 앞과, 맨 뒤에 붙은 모든 white space를 제거할까요? 테스트 데이터를 만들어 보겠습니다. 3개의 String이 들어가 있는데요. 위에 2개는 white space가 공백과 new line, tab으로만 이루어져 있어요. 문제는 ..
c에서 multiple token을 처리하기 위해서 strtok을 이용할 수 있습니다. 자바는 split 로 매우 간단하게 처리할 수 있습니다. 그리고 이 메서드는 정규 표현식을 이용합니다. c++에서는 어떻게 하면 좋을까요? 자바의 split가 정규 표현식을 쓴다는 것에 착안하시면 무엇을 써야 할 지 쉽게 알 수 있습니다. 문자열 s를 ,과 .를 구분자로 나누는 예제를 생각해 보겠습니다. 먼저, delimeter는 . 아니면 ,입니다. 따라서, 이를 정규 표현식으로 표현하면 [.,]입니다. 이것은 scan 집합이 . 아니면 ,라는 의미입니다. 그런데, 이들이 한 번 이상 나오면 어떨까요? 예를 들어, 문자열 ",,"이나, "..,"는 어떤가요? 이런 경우도 match가 되게 하려면 regex의 패턴이 ..
제가 개최한 대회 중에, 2번 문제는 브루트 포스, 백 트래킹을 이용한 문제였습니다. 코딩 테스트에서 상당히 자주 보이고, 반드시 풀고 넘어가야 하는 유형이므로, 2번에 출제하였습니다. 보통, 백트래킹이라고 하면, dfs를 돌리면서 처리하는 경우가 일반적입니다. 이 문제도 예외는 아닙니다. 문제는 중복 방문하는 것을 어떻게 처리할 것인지였습니다. 예를 들어, (1, 1)에 고구마가 있는데, (1, 1)을 3번 방문했다면, (1, 1)에 있는 고구마를 한 번 먹은 것이지, 세 번 먹은 것이 아니기 때문입니다. 여기서 언급하는 문제는 실버1에서 골드5 정도로 그렇게 어렵지 않습니다. 그렇기에 더 자세히 분석해 보도록 하겠습니다. 가장 먼저 생각할 수 있는 방법은, 중복된 데이터를 제거하는 방법이 있습니다. ..
최근댓글