순회 검색 결과

해당 글 4건
java map set 순회하는 방법을 간단하게 알아봅시다.

java에서 map, set 계열을 다룰 때 전체 원소들을 순회해야 할 때가 있습니다. 이 때 어떻게 해야 하는지 간단하게 알아보겠습니다. 보통 map 계열 중에서는, treemap과 hashmap의 사용 빈도가 꽤 높은 편인데요. 이는 hash 계열은 equal 쿼리에, tree 계열은 range 쿼리에 매우 유리한 구조이기 때문입니다. 그리고 저는 농담처럼 자바에서는 TreeMap만 알고 있으면 풀 수 있는 코딩테스트 문제가 상당히 많을 거다. 라는 말도 하는데요. equal 쿼리도 성능이 그렇게 썩 나쁜 편이 아니기 때문입니다. 로그 복잡도로 찾아도 나름 빠르기도 하고요. 먼저, Map에서의 Key, Value 쌍을 모두 순회하기 위해서는, keySet을 이용해야 합니다. 이것은 Map에 있는 ke..
레퍼런스/예제 2021. 10. 17. 19:12
파이썬 for in 문 : 데이터 구조를 순회할 때도 많이 쓴다.

안녕하세요. 이번 시간에는 for in문에 대해서 알아보겠습니다. 보통 ps를 하거나, 코테를 준비한다고 하면, 저는 3개만 잘 하라고 합니다. balanced tree, hash, array. 이 3개에서 거의 벗어나지 않기 때문이에요. 이 3개를 가지고 for in 문을 갖고 놀아보겠습니다. 기본적으로 파이선은 bintree 계열이 없는 듯 하니, bintree 패키지를 깔아줍시다. 가상 환경에 깔아두면 유용하게 써먹을 수 있습니다. 이것은 rb 트리 뿐만이 아니라, AVL도 포함하고 있습니다. 프로그램은 간단합니다. 30번 loop를 돌면서, tree에 (x,1) pair를 추가합니다. 그리고 8번째 줄에서 뭔가를 하는 듯 보입니다. 출력 결과를 봅시다. 트리 안에 있는 (K, V)쌍을 출력했음을 ..
코딩/파이선 2021. 1. 13. 02:39
c++ set이나 map을 전체 순회하는 데 시간 복잡도는 얼마일까요?

질문이 하나 들어왔습니다. 아래에 있는 foo 함수의 시간 복잡도는 어떻게 되나요? 쉽지 않은 질문입니다. c++에서 map이나 set은 self balanced binary Tree로 되어 있습니다. 흔히 '균형 트리' 라고 이야기를 합니다. 중요한 것은 어느 기준 점을 기준으로 왼쪽은 작은 것이, 오른쪽은 큰 것이 저장이 되어 있다는 것입니다. set이나 map이 Binary Tree의 속성을 가진다는 것은 시간 복잡도를 계산하는 데 굉장히 중요한 정보입니다. 즉, root를 기준으로 작은 것은 L, 큰 것은 R 부분에 있습니다. 그렇다면, iterator를, s.begin()부터, s.end()에 도달할 때 까지, 순회한다고 생각해 봅시다. 즉, 작은 것부터 큰 순서대로 순회를 한다고 하면 어떻게 ..
자료알고/자료구조 2020. 1. 31. 01:11
링크드 리스트 : 왜 순회 시간이 배열보다 오래 걸릴까요?

리스트와 배열의 차이점은 면접에서 자주 나오는 질문 중에 하나입니다. 저에게 메일로 질문이 들어온 것 중 하나는, 순회 속도가 어떻게 차이가 나느냐였습니다. n이 작을 때는 별 차이가 없을 수도 있습니다. 하지만 n이 3000 ~ 4000만 정도만 되도 이야기가 달라집니다. 배열은 순차적으로 저장이 되지만, 리스트는 그렇지 않습니다. cache를 이용하기 좋은 구조는 리스트보다 배열이라는 겁니다. 정말 그런지 실험을 해 봅시다. 배열과 링크드 리스트의 순회 성능 테스트를 위한 코드를 작성해 봅시다. node형을 하나 선언해 주었는데요. data 필드와, 다음 주소를 가리킬 필드를 선언해 주었습니다. 단일 링크드 리스트는 포인터가 1개, 더블은 2개일 거에요. C++의 리스트는 더블로 구현이 되어 있습니다..
자료알고/자료구조 2019. 7. 4. 18:08