map과 unordered_map(hash_map) 중 무엇을 사용할까?

map이 내부 구조가 트리(레드-블랙트리) 형태로 되어 있기 때문에
기본 로직에 따라 자동 정렬되므로 logN의 시간이 추가된다.

반면에, unordered_map(hash_map)은 hash-table 구조로 되어 있기 때문에
데이터를 넣어도 자동으로 정렬되지 않으므로 logN의 시간을 아낄 수 있다.
그러나, 내부 hash-function에 의해서 성능이 저하되는 경우에 (특히, 문자열)
map보다 오래 걸릴 수도 있다.

정리해보면 기본적인 경우에는
둘 다 'key-value' 형식으로 되어있으므로 key를 이용하여 정렬된 결과를 얻을 것이 아니면
unordered_map을 이용하는 편이 나은 것 경우가 많다.
(대부분의 경우의 우리가 원하는 것은 key를 이용해 바로 value를 가져오고 싶기 때문)
물론 경우에 따라서 hash-function을 작성하기 나름이다.


아래 링크는 참고한 사이트
http://veblush.blogspot.com/2012/10/map-vs-unorderedmap-for-string-key.html

unordered_map을 적절히 사용하여서 해결할 수 있는 문제는 다음과 같다.
(map을 사용하였을 때와 unordered_map을 사용하였을 때, 시간 차이를 느낄 수 있다.)
https://programmers.co.kr/learn/courses/30/lessons/60060

댓글

댓글 쓰기

이 블로그의 인기 게시물

[PS] BOJ 20543번 폭탄 던지는 태영이

https://www.acmicpc.net/problem/20543 (혹시나 풀어보실 분들은 알고리즘 분류를 보지 않고 풀어보길 권장합니다.) 이 문제를 처음 보고, 간만에 신선하다는 느낌을 받았다. 어떤 알고리즘이나 자료구조를 알고 있으면,  흔히 많이 나오는 유형에 속하는 문제가 있는가 하면, 그렇지 않은 문제도 있다. 이 문제를 풀면서 규칙을 찾고 시간을 단축시켜 나가는 과정이 재미있었고, 예전에 수학에 매력을 느꼈을 때의 느낌과 비슷했다. 물론, 영문까지 포함한 많은 문제를 풀어본 건 아니지만 부족한 내가 느끼기에는 그랬다. 어려운 자료구조를 쓰지 않아도 (기본적인 재료로도)  충분히 난이도를 높여 갈 수 있는 (까다로우며 맛있는 요리?) 그런 문제들의 초입에 해당하지 않나 싶다. 아래는 풀이를 생각한 순서이다. 1. 출력은 맞지만 시간초과 풀이 2. 정답 풀이 먼저, 제한도 까다롭지 않고 시간도 2초나 주어졌기 때문에 풀어보는 것이 중요하다고 생각했다. N이 2,000일 때, 2차원 배열의 데이터 개수는 2,000 x 2,000 = 4,000,000 이다. O(n)에 해당하는 과정은 시간초과를 발생시키지 않으나, 폭탄을 찾기 위해서 자기 자신의 위치(arr[i][j])에서 가능한 모든 경우의 수를 찾으려고 하면 시간초과가 뜰 것이다. 여기까지 생각하고, 규칙을 생각해보았다. 예제 입력과 예제 출력들을 보면서, 가장 외곽에 위치한 배열의 원소들부터 채워가면 될 것이라고 생각했다. 먼저, (0, 0)부터 시작한다고 하면, 시계방향으로 테두리를 돌면서 1칸씩 안쪽으로 진행해볼 수 있다. 그러나 가장 첫 줄을 시물레이션 해보면,  우리가 이중 for문을 통해 배열을 탐색하는 일반적인 과정으로도 채워나갈 수 있다는 것을 알게 되었다. 왜냐하면, 폭탄이 있을 수 없는 구역이 존재하기 때문이다. (m = 1의 경우는 예외) m이 1인 경우에는 그대로 절댓값으로 바꿔서 출력하면 되고, m이 3이상의 홀수인 경우에 생각해보면, 외곽 테두리에 ...
자세한 내용 보기

프로그래밍에서 실수형의 부정확성

실수형의 부정확함(?)에 대해서 생각해보다가, 어떤 분의 블로그를 보게 되었다. 우리는 아래의 문제에 대한 답을 생각해볼 수 있다. (1) double a = 0.1 + 0.1; double b = 0.2; if (a == b)     printf("same"); else     printf("different"); Output : ? (2) double a = 0.1 + 0.2; double b = 0.3; if (a == b)     printf("same"); else     printf("different"); Output: ? (3) double a = 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1; double b = 1.0; if (a == b)     printf("same"); else     printf("different"); Output : ? 위의 문제의 답은 (1) same, (2) different (3) different 이다. 이 이유에 대해서 간단히 말하면, 컴퓨터의 모든 명령은 0과 1로 이루어진 이진수로 동작하기 때문이다. 즉, 실수 표현도 이러한 이진수로 표현하려고 하기 때문에 오차가 발생할 수 있는 것이다. (컴퓨터 구조마다 이진수의 오차를 처리하는 방법에 따라 결과값이 다를 수 있다.) 위의 문제를 직접 이진수로 표현해보자. 0.1 = 1/16 + 1/32 + 1/256 + ... 계산하다보면 알겠지만, 절대 정확하게 나타낼 수가 없다. 0.5와 같이 딱 떨어지는 값은 나타낼 수 있겠지만, 무수히 많은 실수가 오차를 갖는다. 위와 같이 10진수 체계에서 딱 떨어지는 값이여도 2진수 체계에서 무한한 길이를 갖는다면, 오차가 생기는 것을 알 수 있다. 확장해서 무한소수를 이진수...
자세한 내용 보기

프로그래머스 2019 윈터코딩 온라인 테스트를 보았다. (풀이)

이미지
첫 번째 문제에서 테스트케이스의 일부분이 실패하길래 디버깅하다가 1시간을 쓴 것 같다.. (0이 들어오진 않고, 로직은 맞았으나 형 변환을 하지 않아서 틀렸다.) - 19/11/16 많이 아쉬웠던 건 모든 문제에 대해서 접근 방법과 구현 방법이 떠올랐는데, 제대로 된 정답을 내지 못한 것이다. 대체로 요번 윈터코딩에서는 규칙성을 찾는 문제 위주로 나온 것 같다. 2번 문제는 정답이지만, 1번 부분점수 상태에서 디버깅 하다가 3번을 제대로 못풀고.. 그래서 아쉬운 대로 내가 풀었던 방법을 적어놓고자 한다. (현재 모든 문제 해결하였습니다.) #1 멀쩡한 사각형 N x M 격자판에 양 꼭짓점으로 대각선을 하나 그었을 때,  직선에 걸치는 사각형을 전체 사각형의 개수에서 빼는 문제이다. 격자의 최소 단위는 1 x 1로 이루어져 있고, w와 h가 주어진다. (범위는 1억까지) 규칙을 찾다가, 정사각형일 때와 아닐 때 를 생각해보았다. 정사각형인 N x N 형태이면, 대각선으로만 걸치므로 w * w - w를 하면 된다. 정사각형이 아닌 N x M 형태이면,  선에 걸치는 사각형들이 오른쪽 또는 아래를 걸쳐서 선을 타고 내려오는 모습이 된다. (그림 참조) 3x3 사각형과 8x12 사각형 대각선이 아닌 오른쪽 또는 아래로만 거쳐서 선에 걸치는 사각형만 있으면 생각하기 쉽다. 그러나, 문제에서 주어진 예제 테스트케이스로 w=8, h=12를 생각해보면 중간마다 정사각형일 때 처럼, 대각선으로 걸치는 경우도 있다. 이 경우가 언제인지를 생각해보자. 그림에서 보면 정확히 2 x 3지점에서 대각선으로 걸치고 있다. 그리고 전체가 2 x 3인 사각형들을 4번 대각선으로 붙인 모습이다. 여기서 생각해볼 수 있는 건 이 2 x 3이 현재 전체 사각형들이 대각선으로 걸치는 최소 단위라는 것이다. 직선이므로, 내부에 존재하는 부분 직선도 ...
자세한 내용 보기