백준 1325번은 c,c++로 풀면 쉽게 풀리는 dfs, bfs 문제 중 하나입니다. 그런데 Java로 풀면 시간이 빡빡한데요. 그 이유 중 하나는 박싱, 언박싱에 의한 객체 생성 때문입니다. 이에 대해서 아직 익숙하지 않으시다면, 이 포스트를 보고 오시는 것도 좋습니다. 통과를 하시고 나서, java로 통과한 코드 중에서 1등과 2등 코드의 차이를 보면 대충 3초 가량이 나는 것을 볼 수 있습니다. 이 두 코드를 보시면, 하나는 primitive type 배열을 썼고, 다른 하나는 그렇지 않았음을 볼 수 있는데요. 3초 차이라니. O(nm) 복잡도에서, 아슬아슬하게 통과할 복잡도에서, 3초면 상당히 큽니다. 그 원인 중 하나가 필요 없는 객체 생성이라 했으니, trace를 해 보겠습니다. jdk 8 기..
전체 글 검색 결과
이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다. 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다. 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x
파이썬에는 built in 함수로 id가 있습니다. 문서에 따르면, 이것은 객체의 고유값을 리턴하는 메서드입니다. cpython은 주솟값을 돌려준다고 문서에 언급이 되어 있습니다. 저는 이 메서드를 어떤 객체를 가리키는지 보기 위해서 쓰곤 합니다. 몇 개의 예를 보고, 톡방에 질문 들어왔던 내용도 보도록 하겠습니다. 예제 1입니다. 그리 어려울 것은 없습니다. a는 배열 [5]를 가리키고, b는 [10]을 가리킵니다. 이 상태에서 id(a)와 id(b)를 출력합니다. 다음에, b에 a를 대입합니다. 다음에, id(b)를 출력합니다. id 값을 찍어보니 위와 같이 나왔습니다. 이것을 trace 해 보도록 하겠습니다. 먼저 4번째 줄 상황을 보겠습니다. id(a)와 id(b)가 달랐습니다. a와 b가 다른 ..
파이선에서 n차원 배열을 초기화 할 일은 꽤 많습니다. 어제도 그러한 코드를 작성했거든요. n = 2일 때만 작성해 보도록 하겠습니다. n > 2이상일 때는 2일 때만 잘 응용하면 되기 때문입니다. 어떻게 해야 하는지 예제 코드들을 보도록 하겠습니다. 요구 사항은 int형 Object를 저장할 2차원 배열을 만들라는 것입니다. 저는 9x9짜리 배열을 만들었습니다. 그런데, 이 코드는 어떻게 동작할까요? 저는 2번째 줄에서 arr[0][0]만 1로 바꾸었습니다. 그런데, arr[0][0]과 arr[1][0]을 출력해 보니, 둘 다 1이 나왔습니다. 왜 그럴까요? 어디선가 주소값만 복사되는 얕은 복사가 일어났기 때문입니다. python에서 id는 해당 객체의 값을 얻어오는 코드입니다. 9개의 루프를 돌면서 ..
lombok에 빌더 어노테이션에 대해 생각해 보다가, 문득 builder를 왜 쓰는지가 궁금했습니다. 디자인 패턴에 대해서 하나도 모르는 저는 빌더 패턴을 3편에서 4편 정도를 쓸 듯 싶습니다. 먼저, '완전한 상태'에 대해서 생각해 보겠습니다. age와 name으로 이루어진 모델이 하나 있습니다. 그리고, 이 오브젝트는 생성이 되면 값이 변경되지 않습니다. getter와 setter가 있습니다. 그리고 Main 함수를 보겠습니다. 모델의 나이를 set하고, name을 set 합니다. Model 클래스에서 이름과 age가 필수 항목이라고 할 때, 모델 객체만 만든 상태는 완전한 상태인지 생각해 보겠습니다. 그렇지 않습니다. 이 상태에서 뭔가 작업을 한다고 하면 문제가 생길 듯 해 보입니다. 그래서 4번째..
최근댓글