전체 글 검색 결과

해당 글 904건
java hashset은 key의 해쉬 코드가 모두 같을 때 최악 복잡도가 어떻게 될까요?

저번에, 왜 equals를 구현하면 왜 hashCode를 같이 구현해야 하는지에 대해서 설명을 했습니다. hash 계열의 자료구조 때문에 그렇다고 했었습니다. 그렇지 않으면 어떻게 동작하는지는 여기를 참고하시면 좋겠습니다. 이 내용에 대해서 숙지하셨다고 가정하고 진행하도록 하겠습니다. 면접 질문에서 간혹 가다가 등장하는지는 잘 모르겠습니다만, 어떠한 객체의 hashCode 값이 같은 것들을 모두 hashSet에 넣을 때, 어떤 일이 벌어지는지는 꽤 중요한 문제 중 하나일 겁니다. 사실, 우리는 그렇게 바보같이 구현할 일이 없습니다. 그렇지만, 저는 이에 대해서 포스팅 하도록 하겠습니다. 먼저 Java 8에서부터, hashMap은 버킷에 8개 이상 달려있을 때, Balanced Tree로 변환이 된다는 것..
레퍼런스/분석 2019. 12. 18. 22:35
2048 퍼즐 게임 1턴 구현 : 읽는 방향과 flag만 잘 고려하면 어렵지 않아요.

안녕하세요. chogahui05입니다. 저번 시간에 소코반을 구현해 보았습니다. 다소 어려웠어요. 오늘은 그것보다 다소 쉬운 2048 퍼즐의 1턴을 구현해 보도록 하겠습니다. 사실 뿌요뿌요 게임도 구현해 보면 재밌긴 합니다. 그런데 그건 BFS, DFS를 알아야 하는 전제가 깔리니 쉽지 않긴 하지만요. 하튼, 구현해 봅시다. 2048은 어떠한 것을 합칠 수 있는 방향이, 위, 아래, 왼쪽, 오른쪽이 있습니다. 이 중, 퍼즐이 요렇게 있고, 우측으로 합친다고 해 봅시다. 그러면, 먼저 2와 2가 merge 될 거에요. 다음에 노란색 4와 파란색 4는 merge 되지 않아요. 단지, 파란색 4끼리만 merge가 됩니다. 이렇게 합쳐질 겁니다. 다음에 8과 4를 합치려니, 되지 않습니다. right 명령을 내..
구현 2019. 12. 18. 17:22
sql 셀프 조인 (self join) : 자기 자신과 자기 자신을 조인한다.

이번 시간에는 Self Join에 대해서 배워보도록 하겠습니다. 이것은, 자신과 자신을 Join하는 것을 의미하는데요. 예를 들어, 이런 경우를 생각해 볼 수 있어요. 도시 이름과 인구, 도시 ID가 저장된 테이블이 있다고 가정해 봅시다. 이 때, 해당 도시의 인구 랭킹을 구하고 싶습니다. 단, 동순위는 같은 번호로 처리합니다. 이 쿼리를 어떻게 처리하면 좋을까요? 물론 MYSQL도 지금은 rank 함수가 지원됩니다. 아마 8.0부터인가부터 말입니다. 실제로, 이것을 써 봤는데 무난하게 되었습니다. 하핫. 그런데 이 함수를 쓰는 게 불가능하다. 그러면 어떻게 하면 좋을까요? 몇 가지 방법이 있는데요. 그냥 성능 생각하지 않고 짤 수 있는 방법 중 하나는 self join을 하는 것입니다. 먼저, city..
코딩/Sql 2019. 12. 18. 01:34
리눅스 alias unalias 명령어 : 별칭을 추가하고 제거한다.

alias는 별칭이라는 뜻입니다. 예를 들어서 A라는 이름을 가진 사람을, B라고 부를 수 있습니다. 이 때, B는 A의 별칭 (별명) 이라고 많이 이야기를 합니다. 명령어도 다르게 부를 수 있는데요. 예를 들어서, ll은 'ls -l --color=auto'의 다른 이름이라고 할 수 있어요. 엄청나게 긴 것을 단 2글자로 압축을 할 수도 있어요. 이 정도만 보면 꽤 대단하고 위력적인 것임을 알 수 있습니다. alias만 쉘에 쳐 보면, 현재 별칭이 적용되어 있는 것들만 출력이 됩니다. 먼저, 명령어 A를 B라는 이름으로 다시 부르게 하도록 하기 위해 등록하는 명령어는 alias B = 'A'입니다. 예를 들어서, head 라는 명령어를 hd라는 이름으로 다시 부르게 하려면, alias hd = 'hea..
OS/리눅스 2019. 12. 17. 10:05
우선순위 큐 : 부모가 자식들보다 rank가 높다.

우선순위 큐는, 삽입과 삭제가 일어날 때, 가장 우선순위가 높은 것을 빠르게 찾을 수 있는 구조입니다. 일단, 이것의 특징 먼저 간단하게 잡고 넘어가 봅시다. 먼저, 부모들은 자식들보다 rank가 높습니다. 예를 들어서, A의 자식이 B, C라고 해 봅시다. 그러면, A >= B이고 A >= C입니다. 그러면 A의 모든 child들 (자식의 자식이라던지)은 무조건 A보다 rank가 같거나 낮을까요? 위 그림을 봅시다. B(1)의 직계 child는 B(2), B(2)의 child는 B(3), ... 이런 식으로 가고 있어요. 그러면 A >= B(1) >= ... >= B(n)이 성립합니다. 연쇄입니다. 따라서, A >= B(n)입니다. 부모에서 자식으로만 연결된 간선이 있고, x가 A로부터 도달 가능할 때..
자료알고/자료구조 2019. 12. 16. 21:56