자료알고 검색 결과

해당 글 130건
java treemap compareto나 compare만 구현했을 때 제대로 동작할까요?

자바에는 TreeMap이 있습니다. 키 오브젝트가 Obj의 인스턴스라고 해 봅시다. Obj 클래스에서 equals를 override 하지 않고 compareTo를 비교하거나, Obj를 비교하는 방법인 comparator만 생성자로 넘기면 어떻게 될까요? 그래도 잘 동작할까요? 우리가 걱정하는 부분은 equals입니다. equals는 두 객체의 동등성을 비교합니다. 이 메서드가 어디에서 쓰이는지 TreeMap 내부에서 한 번 찾아보도록 합시다. putAll에 등장합니다. Objects.equals이네요. comparator를 넘기는 것으로 보아서는, 비교하는 객체를 넘기는 것으로 보입니다. 따라서, 키 값과는 아무런 연관이 없습니다. 다음 replace 입니다. 이 부분도 잘 보면, value에 대해서만 ..
자료알고/자료구조 2023. 5. 11. 00:14
java linkedhashmap removeeldestentry 메소드에 대해 알아봅시다.

가희배 5회 코딩테스트가 4월 2일에 열렸습니다. 제가 플레 이상으로 예측한 문제도 있었지만, 골드 정도로 예측했는데 실제로 까 보니 플레였던 문제가 있었습니다. 그 문제에 이어서 또 당한 셈인데요. 이 문제가 어려웠던 이유는 2가지가 있습니다. 카카오 기출 문제를 3개나 섞었다. 그리고, 이 문제에 jpop 이랑 kpop이 상당히 많이 들어가면서 지문 자체가 어마어마하게 길었다. 이 2가지가 있겠습니다. 이것은 가희와 코드도 마찬가지입니다. 후자는 사전 지식이 없으면 해석하는 데 시간이 구현시간보다 더 걸렸을거고 전자는 구현량이 생각보다 있었습니다. 문제에서 요구하는 것은 2가지입니다. lru, 가장 가까운 cache 찾기, 엄청나게 긴 지문과 이상하게 jpop과 kpop이 들어간 예제 해석. 이 중 ..
자료알고/자료구조 2023. 4. 4. 02:16
java stack 클래스와 대체해서 쓸 만한 arraydeque를 간단히 알아봅시다.

java에는 stack 클래스가 있습니다. 스택은 마지막에 들어온 원소가 먼저 빠져나가는 것으로 유명한 자료구조입니다. 계산기 같은 것을 구현할 때 많이 쓰이기도 합니다. 백준 문제를 풀다 보면 간혹 가다 쓰일 때가 있습니다. 간단한 예제를 하나 보겠습니다. 위 예제는 0부터 4까지의 수를 넣은 다음에, 맨 위에 있는 원소를 peek으로 가져오기만 합니다. 다음에, pop으로 맨 위에 있는 원소를 가져오면서 제거합니다. peek 메서드의 설명을 보면, 보다 명확합니다. 스택에서 원소를 제거하지 않고 stack의 맨 위에 있는 원소를 가져온다. 반면에 pop은 제거까지 합니다. 비어있는지 검사하기 위해서 empty를 호출했습니다. 다음에, 원소를 넣기 위해 push를 썼습니다. 나중에 넣은 4가 먼저 빠지..
자료알고/자료구조 2023. 2. 28. 23:55
실수 오차의 무서움과 가희와 방어율 무시

가희와 방어율 무시 문제는 상당히 쉬운 문제였습니다. 그럼에도 불구하고 정답률이 그렇게 높지 않았는데요. 실수 오차 때문에 고전하는 경우가 상당히 많이 있었습니다. 이와 비슷한 이슈가 있었던 문제 중 하나는 가희와 btd5가 있었습니다. 먼저, 오답 코드는 위와 같습니다. 물론, 백준 질문에도 올라왔던 코드입니다. 어느 케이스에서 틀렸을까요? 500 80에서 제대로 답을 출력하지 못합니다. 왜 그럴까요? 실수 오차 때문이다. 라는 것을 누구나 알 수 있습니다. 어떠한 과정에서 잘못된 결과가 나왔는지 하나씩 보겠습니다. 먼저 1, b/100, c에 대해서 bit 값을 출력해 보겠습니다. 저는 memcpy 등으로 변수를 배열에 복사한 뒤에, 저장되어 있는 값의 bit를 하나씩 꺼내왔습니다. 저는 b, b/1..
자료알고/알고리즘 2022. 9. 5. 01:00
가희와 프로세스 2 : 관점을 바꾸어서 이분 탐색을 적용해 봅시다.

안녕하세요. 팀 codingdog입니다. 1회에 출제된 문제 중 가장 어려웠던 문제는 가희와 프로세스 2 문제였는데요. 대회 당시에 단 2분만 푸셨을 정도로 쉽지 않은 문제였습니다. 어떤 점이 발목을 잡았는지, 그래서 어떻게 접근을 해야 했는지만 보겠습니다. 먼저 기본 아이디어는 가희와 프로세스 1 문제와 동일합니다. 나머지 프로세스의 우선순위가 1 상승하는 것을 상대적인 관점에서 생각한다. 즉, 현재 실행되고 있는 프로세스가 실행되면, 우선순위가 1 하락한다. 달라보이지만, '상대적'인 관점에서 생각하면 똑같은 말입니다. 어렵지 않죠? 문제를 요래 변형하는 게 첫 번째 포인트입니다. 이 부분은 2회의 가희와 거북이 인형 문제에서도 교과서에 나온 개념 그대로 연계해서 출제한 적이 있습니다. 예제 1번을 ..
자료알고/알고리즘 2022. 2. 21. 01:01