키워드

• map
• set
• unordered_map
• 시간복잡도, Big O
• BST, 해시 테이블
• count(), insert(), erase()
• map[key] 자동 생성
• countMap[n]++

기억해야 할 것

• for (int num : arr) 정도면 충분. int는 굳이 const int&까지 안 써도 됨.
• 삼항연산자는 값 고를 때만. push_back(), sort() 같은 동작 분기는 그냥 if로 쓰기.
• sort(answer.begin(), answer.end()) 하면 기본 오름차순 정렬.
• vector에서 찾기는 보통 끝까지 봐야 해서 O(n), map 검색 / 삽입 / 삭제는 O(log n).
• unordered_map은 정렬 안 되지만 평균 검색 속도 O(1).
• m["key"]는 없는 key를 읽기만 해도 기본값으로 생성.
• countMap[n]++ 패턴
• UE: TMap, TSet

[코드카타]나누어 떨어지는 숫자 배열

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12910

문제 요약

• array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
• divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

내가 제출한 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr, int divisor) {
    vector<int> answer;
    for(const int& num: arr)
    {
        if(num%divisor==0)
        {
            answer.push_back(num);
        }
    }
    answer.empty() ? answer.push_back(-1) : sort(answer.begin(), answer.end());
    return answer;
}

피드백

• for(const int& num: arr): int 같은 작은 타입은 const & 까지 할 필요 없다. 걍 복사해도 부담없음.
• answer.empty() ? answer.push_back(-1) : sort(answer.begin(), answer.end());: 삼항연산자를 action 용으로 쓰면 겁나 길어진다. 값 고를 때만 쓰자. if() 문으로 해결.

배운 점

• vector.empty()
• sort(vector.begin(), vector.end()): 비교함수 없이 sort 하면 오름차순.

알고리즘 라이브 세션 - Map

• 블랙이진트리, key value, 기준에 따라 자동 정렬되는 트리, 시간복잡도 logn, 유일한 key와 그에 대응하는 value
• 검색 기능이 없는 무작위 전화번호부면 -> 하나하나 번호 읽고 확인해야 함.
  • 시간복잡도 O(n). 벡터의 find 시간복잡도

시간복잡도

• 대...충 이 알고리즘이 어느 정도 시간이 걸리는지. 입력크기에 따라 연산 횟수가 어떻게 증가하는지.

• Big O 표기법(점근 표기법)으로 표기함.
  

• vector는 O(n), map은 O(log n)

String 복습

• 벡터의 사촌. find, substr, replace 있다.
• 문자는 숫자다 (char) - 'A'는 65, 'a'는 97

Vector의 한계

• vector<pair<string, int>> 형식으로 이름-전화번호를 저장한다 치자. 검색하려면 처음부터 하나씩 비교 -> 1만 명이면 최대 1만 번 검색해야 함.

Map

• map은 key - value 쌍을 저장하는 자료 구조. key는 이름표(찾는 기준), value는 실제 데이터.

map<string, int> scores;
scores["김철수"] = 78;
scores["김철수"];

규칙

1. key는 중복 불가. 같은 키로 다시 넣으면 기존 값이 사라짐.
2. 순회하면 key 기준 자동 정렬. 넣은 순서가 아니라 key의 오름차순.

map의 시간 복잡도

• 검색, 삽입, 삭제 모두 O(log n)
• 이진 탐색 트리 (BST) 를 쓰기 때문. 작은값/큰 값 반갈 해서 탐색해서 검색범위 줄여 나감.
  • 정렬이 되어 있기에 가능. key 기준으로.

Map의 연산

연산	설명	시간 복잡도
m["key"] = value	삽입 또는 수정	$O(\log n)$
m["key"]	값 읽기 (주의!)	$O(\log n)$
m.count("key")	존재 여부 (0 또는 1)	$O(\log n)$
m.erase("key")	삭제	$O(\log n)$
for (auto& p : m)	순회 (p.first / p.second)	$O(n)$

[] 자동 생성 함정

• 없는 키를 []로 읽기만 해도 기본값 (int라면 0)으로 자동 생성. 의도치 않게 map 크기가 늘어나는 버그를 원인
• 검색 목적이라면 count 로 존재여부 확인 후 읽기!

countMap[n]++ -> 핵심 패턴

map<int, int> countMap;
for(int n: numbers)
{
countMap[n]++;
}

numbers 배열에 k가 몇개 들어가는지 체크를 할 때 이렇게 하면
1. 숫자 k 처음 만났을 때 countMap[k] 값 읽기 -> 값 없으니 초기값으로 생성 -> 0으로 생성 -> ++ 해서 1 됨.
2. 다음에 만났을 때 ++ -> 1개 추가.
이런 식으로 카운팅 가능함. 이후 countMap[k] 하면 갯수 확인 가능

Set: key만 있고 value는 없다.

• 이 값이 존재하는가? 에 대해 관심있을 때만 쓴다. map 이 사전이라면 set은 출석부
• 중복 제거, 자동 정렬 된다는 게 특징.
• insert, count, erase 가능

map vs unordered_map

map	unordered_map
내부 구조: 이진 탐색 트리	내부 구조: 해시 테이블
검색 속도: $O(\log n)$	검색 속도: 평균 $O(1)$
순회 순서: key 정렬 순	순회 순서: 보장 없음
용도: 정렬이 필요할 때	용도: 빠른 검색만 필요할 때

• 알고리즘 풀 때나 이럴 때 unordered map 자주 쓴다. 빠른 검색 때문에 (O(1)!!)
• 사용법 자체는 map/set과 거의 동일.

코드 예제

예제 2

• 삽입의 경우

1. fruits["apple"] = 1500; 식으로 [] 쓰기.
2. fruits.insert({"apple", 9999}); 식으로 쓰기. 덮어쓰기 하지 않는다.

• 검색의 경우
  • 안전한 검색: count()로 확인 후 [] 로 검색하기.
  • count()는 해당 key가 있으면 1, 없으면 0 반환
• 삭제/ 순회
  • 항상 자동 정렬. erase() 는 키 지정해서 삭제.

예제 3

카운팅 패턴

• 숫자 빈도 세기, 단어 빈도 세기 할 때

예제 4

• 아이템 DB 관리
• ID로 "바로 찾기" 하기 위해 vector보다 map이 효율적. 아이템 ID 번호가 1001, 2000, 4999 처럼 불연속적일 경우가 많기 때문. 정렬해주고 - 즉시 검색

O(1) 검색

• v[3] 하면 메모리에서 바로 3번 칸 찾아냄. 숫자 인덱스로 바로 접근하기 때문.
• 김철수 같은 문자열도 숫자라면 가능 -> 이것이 해시 함수(어떤 데이터든 고정 크기의 숫자(해시값) 출력)
• key는 다른데 해시값은 같은 경우가 있다 = 해시 충돌
  • 이럴 땐 보통 리스트로 한 해시값 내부 값들을 여러 개 연결함.
    -이런 충돌 많아지면 O(n). 보통 충돌 드물어 평균 O(1)
• map 과 unordered_map 은 내부 구조가 이진 탐색 트리/해시 테이블로 다르다.

실전에서는

• 게임에서 데이터 관리의 핵심
• 아이템 DB는 map, 퀘스트 완료 여부 set...
• UE5에선 TMap TSet 제공. 태그가 보통 Map이다.