코후닝

개요 대규모 데이터셋에서 원하는 정보를 효율적으로 저장하고 검색하는 것은 시스템 성능에 매우 중요하다.가령, 웹사이트에 사용자가 로그인했을 때 서버는 해당 사용자의 로그인 상태나 장바구니 정보 같은 걸 기억해야 한다고 가정해보자.사용자가 페이지를 이동할 때마다 이 정보를 빠르게 찾아야 하는데,배열이나 연결 리스트를 이용한 순차 탐색은 데이터 크기에 비례하여 탐색 시간(O(n))이 증가하며, 이진 탐색 트리(O(log n))도 한계가 있다.만약 로그인 시 발급된 고유한 세션ID(Key)에 해당하는 사용자의 정보(사용자 객체, 장바구니 정보 등)를 값(Value)로 저장한다면, 사용자의 요청에 세션ID로 바로 조회해서 사용자 정보를 순식간에 꺼내 쓸 수 있을 것이다.이를 통해 데이터 양과 관계없이 거의 일정..

알고리즘 분류: 수학, 자료 구조, 조합론, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 【 풀이 】 조합에 대한 수학적 사고력과 이를 해시맵으로 해결하는 능력을 묻는 문제이다. 조합(Combination)에 대해서 깊게 생각해 봤지만, 간단한 아이디어 하나로 풀 수 있는 문제였다. 같은 종류의 의상을 2개 이상..

알고리즘 분류: 그리디 알고리즘, 정렬 문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 【 풀이 】 그리디 기초 문제 중 하나이다. 이 문제의 경우에는 정렬했을 때의 각 요소의 값이 최적의 경우가 되기 때문에 먼저 정렬을 해주고 계산을 해주는 것이 중요하다. 【 코드 】 #include #include using namespace std; int main(void) { int human[1001]; int n; int sum=0; cin >> n; for (in..

알고리즘 분류: 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 【 풀이 】 그리디 알고리즘을 활용하는 그리디 기초 문제이다. 동전 거스름돈은 항상 가장 큰 금액의 동전부터 거슬러 주는 것이 최적해이기 때문에 n개의 동전들을 배열에 저장해 주고 배열의 맨 뒤에서부터 계산해 주면 된다. 【 코드 】 #include using namespace std; i..

알고리즘 분류: 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 【 풀이 】 반복자를 생성하고 map의 멤버 함수 중 하나인 find로 key 값을 저장한다. map.find(key)는 찾고자 하는 값이 없으면 map.end()를 반환하기 때문에, 이를 이용해 개수와 key의 value를 1씩 증가시킨다. 그 후 map을 순회하면서, value값이 1인 key를 출력해 주면 된..

알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 【 풀이 】 2023.04.09 - [백준 [BAEKJOON]] - [백준] 10845번: 큐 [C++] [백준] 10845번: 큐 [C++] 알고리즘 분류: 자료 구조, 큐 문제 링크: https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,..