(2차원) 배열에서 가장 큰 정사각형을 찾는 것은 dp로 해결할 수 있습니다. 문제를 조금 바꿔보겠습니다. 가장 큰 직사각형은 어떻게 구해야 할까요? 문제의 제한이 딱 하나 바뀌었을 뿐인데, 난이도는 4단계 정도 높아졌습니다. 이 문제를 보도록 하겠습니다. 문제를 요약하면 다음과 같습니다. n이 범위는 1이상 2000 이하입니다. 시간 제한이 3초인 것을 감안했을 때, O(n^2)나 O(n^2logn) 정도에 풀어야 한다는 결론을 얻을 수 있습니다. 그런데, 후자는 생각보다 상수 줄이기가 빡빡하기도 하고 제가 시도해 본 방법이 아니므로, 저는 전자로 시도해 보겠습니다. 먼저 간단한 상식 아닌 상식을 통해서 관찰을 하나 해 보도록 하겠습니다. 길이가 3, 4, 2, 6인 높이 1짜리 직사각형이 있습니다. ..
전체 글 검색 결과
이펙티브 자바 3편을 보면 for each에 대한 설명이 나와 있습니다. 거기에서도 언급했다 시피, for each문을 도는 동안에 이터를 돌고 있는 자료구조에 변형이 오면 안 됩니다. (item 58) 만약에 변형이 오면 어떻게 될까요? 사실 저는 null Exception이 뜨거나 (Linked인 경우에), 아니면 정상적으로 수행이 될 거라고 생각했습니다만.. 예상과는 다른 것이 출력되었습니다. 그 이유는 modCount 필드와 관련이 있습니다. 아래 코드를 보겠습니다. 0부터 4까지 차례대로 LinkedList에 넣습니다. 그리고, List를 순회합니다. 이는 향상된 for loop를 써서 할 수 있습니다. 그런데, 이 코드에서는 단순히 '순회'만 하지 않습니다. list에 있는 첫 번째 원소를 도..
대소문자 구분없이 grep을 이용해서 matched 되는 줄을 찾는 방법을 알아봅시다. grep의 man 페이지를 보면 -i, --ignore-case라고 되어 있습니다. 이는, 대소문자의 다름을 무시한다는 이야기입니다. sample.txt를 보겠습니다. 여기에는 5개의 줄로 이루어진 데이터가 들어 있습니다. 여기서, grep group을 뽑으면, 이렇게 2개의 줄만 matched 됩니다. 이는, GROUP은 대소문자를 엄격하게 구분한다면, group이 아니기 때문입니다. 이것을 무시하기 위해서 -i 옵션을 줘 보겠습니다. 그러면, GROUP 또한 매치가 됨을 알 수 있습니다. 이런 옵션은 다른 명령어에서도 유용하게 쓰일 수 있습니다. 예를 들어서, 현재 제가 있는 위치인 /home/cho을 기준으로 해..
오늘은, 아래와 같은 상황에서, 키가 중복해서 들어가 있다면, update를, 그렇지 않으면 insert를 하는 예제를 보도록 하겠습니다. 당연하게도, 이 문서를 같이 읽어보시는 것을 권해드립니다. 기존 테이블은 오래된 데이터입니다. 몇 데이터가 들어오는데, 이 중에는 '업데이트'가 된 데이터도 있습니다. 예를 들자면, id에 대해서. 그러한 경우에 어떻게 해야 할까요? postgresql에는 upsert가 있다고 하는데.. 문제부터 보겠습니다. sampleT는 아래와 같습니다. id와 name으로 정의가 되어 있고, id는 primary key입니다. sampleT에 추가되어 있는 데이터를 보도록 하겠습니다. select from을 이용하면 매우 간단하게 조회할 수 있습니다. 1, 'cho'하고, 2,..
저번 시간에 InputStream으로 파일을 읽는 것에 대해서 배웠습니다. 다시 1.txt를 보겠습니다. 이번에는 한글이 포함된 무언가가 있습니다. 이것은 UTF-8로 인코딩 되어 있습니다. 제가 저번에 작성했던 이 프로그램은, 의도대로 잘 동작할까요? 인풋의 크기에 비해서 버퍼의 크기가 상대적으로 크니 제대로 동작하는 것처럼 보입니다. b의 배열 크기를 5로 줄여보도록 하겠습니다. 이 프로그램을 실행시켜 보겠습니다. 그러면 글자가 깨져서 나옵니다. 이는, 2byte나 3byte 길이의 데이터를 읽다가 끊었기 때문입니다. 어떻게 읽어들였는지, 헥사로 출력해 보도록 하겠습니다. 요렇게 바꿔 보겠습니다. Integer.toHexString은, int 값을 Hexa로 출력해 주는 겁니다. 우리는 byte 값을..
최근댓글