전체 글
C++ map vs unordered_map 비교
1. 핵심 차이 요약항목map (ordered)unordered_map 항목map (ordered)unordered_map내부 구현Red-Black Tree (균형 이진 탐색 트리)Hash Table (체이닝 방식)시간 복잡도 (평균)O(log n)O(1)시간 복잡도 (최악)O(log n)O(n)키 순서정렬됨 (operator정렬 안 됨 (해시 순서)메모리 사용량적음많음 (버킷 배열 + 빈 슬롯)키 요구사항hash + == 연산자이터레이터 무효화삽입/삭제 시 해당 노드만rehash 시 모든 이터레이터 무효화헤더 (C++11~) 2. 내부 구현 자세히std::map — Red-Black Treemap은 거의 모든 표준 라이브러리 구현체(libstdc++, libc++, MSVC STL)에서 레드-블랙 트리..
Red-Black Tree
1. 트리(Tree)란?트리는 데이터를 계층적으로 저장하는 자료구조예요. 우리가 잘 아는 배열이나 연결 리스트는 데이터가 한 줄로 쭉 이어져 있는 선형 구조인데, 트리는 부모-자식 관계를 가지면서 가지를 뻗어 나가는 비선형 구조입니다.이름은 "나무"인데 실제로 그림을 그릴 때는 거꾸로 된 나무 모양이에요. 가장 위에 뿌리(root)가 있고, 아래로 가지가 뻗어나가죠. 회사 조직도, 컴퓨터의 폴더 구조, 가계도를 떠올리면 됩니다.용어 몇 가지를 먼저 익혀두면 이후 설명이 훨씬 편해집니다. 루트(root) 는 가장 위에 있는 시작 노드, 리프(leaf) 는 더 이상 자식이 없는 끝 노드, 간선(edge) 은 부모와 자식을 연결하는 선이에요. 그리고 높이(height) 는 루트에서 가장 깊은 리프까지의 거리를..
네이버 입사한지 2년 7개월이 흐르며
2023년 7월에 입사하고치지직 BE 개발팀에 합류하여 어느덧 2년 7개월이라는 시간이 지났다. 유저수가 늘어나고, 신규 기능들을 출시하며 여러 경험들을 했는데,생각 나는 것들에 대한 회고를 간략하게 적어볼까 싶기도하고그냥 개인적으로 공부하는 내용들도 겸사겸사 정리할까 해서 다시 블로그를 시작해볼까 한다.
[백준] 수 정렬하기 2
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 100만개 이하의 숫자를 입력 받아서 sorting해서 출력하면 되는 문제입니다. 사실 c++ 에서의 algorithm에서는 자동으로 최악의 pivot 설정을 피하면서 퀵정렬을 해주는 sort() 함수를 제공합니다. 이 함수를 이용해서 구현하면 됩니다. #include #include using namespace std; int numArray[1000..
[백준] 스도미노쿠
https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 우선 문제부터 요약하면, 스도미노쿠라는 게임을 풀어야하는 문제입니다. 초기상태가 주어지면, 해당 게임을 모두 푼 결과를 출력해야 합니다. https://life318.tistory.com/211 [백준] 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재..
[백준] N-Queen
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 우선 문제부터 요약하면, NxN의 체스판에 Queen을 놓는 경우의 수를 구하는 문제입니다. 이전에 python으로 두 번 해결한 적이 있습니다. https://life318.tistory.com/91 [백준] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이..
[leetcode] Rotate List
https://leetcode.com/problems/rotate-list/ Rotate List - LeetCode Can you solve this real interview question? Rotate List - Given the head of a linked list, rotate the list to the right by k places. Example 1: [https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg] Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1 leetcode.com 우선 문제부터 간단하게 요약하면, single linked list를 k회 회전 시켰을 때의 head를 출력해야 하는 ..