Google DSC Sookmyung

1. Map 1) map 이란? 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열이라고 생각하면 쉬움 각 노드가 unique한 key와 value의 쌍으로 이루어진 트리 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중 하나인 레드 블랙 트리로 구현되어 있음 key를 기즌으로 정렬되어 있기 때문에 검색 속도가 빠름 연관 있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우에 주로 사용 2) c++에서 map 사용하기 include 을 해야 사용 가능 map은 중복 불가한 key와 values 쌍으로 이루어진 노드의 트리이므로 같은 key 값을 같은 노드에 추가하면 원래 노드의 values 값에 덮어씌워짐 ex) (2, 3)인 노드 A가 이미 존재하는 map에 (..

그래프 탐색이란 하나의 정점으로 부터 시작하여 모든 정점을 한번씩 방문하는것이다. 이때 너비를 우선으로 탐색하느냐 깊이를 우선으로 탐색하느냐에 따라 BFS와 DFS로 나눈다. ✅ BFS는 큐를 이용해 구현한다. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 큐에서 원소를 꺼내어 그 칸에 대해 상하좌우로 인접한 칸에 대해 (3)을 진행한다. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다. 큐가 빌때까지 (2), (3) 반복한다. ✅ DFS는 위의 BFS와 비슷하지만 스택을 이용해 구현하거나, 혹은 재귀를 이용해 구현하는 방법이 있다. 1️⃣ 스택을 이용해 구현하는 방법 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다. 스택에..

이분 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 단계마다 탐색 범위를 절반씩 줄이기 때문에 시간복잡도는 O(log N)이다. (순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데리터를 하나씩 확인하는 방법.) 파라매트릭 탐색 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 된다. 즉, 주어진 상황에서 최솟값, 최댓값 등의 특정 값을 구하는 문제를 특정 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바뀐다는 의미이다. c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bo..

Dynamic Programming 다이나믹 프로그래밍(DP) 즉, 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 기법이다. DP는 재귀와 유사하지만 재귀는 사용하면 동일한 계산이 여러번 반복되어 비효율적인 계산이 될 수 있다는 점이 DP와 큰 차이점이다. DP는 재귀의 이러한 단점을 개선해준다. DP를 구현하는 방법 중 가장 많이 사용하는 방법은 `Memoization(메모이제이션)`이다. Memoization은 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. 값을 기록한다는 점에서 `Cashing(캐싱)`이라고도 한다. DP는 주어진 문제가 DP유형인지 파악하는 것이 중요하..

Queue 메모리 안 데이터를 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식. 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 (First in First out) 큐에서는 추가되는 곳을 뒤쪽(rear)이라고 하고 제거되는 쪽을 앞쪽(front)이라고 한다. 제일 앞, 뒤가 아닌 나머지 원소들의 확인/변경이 불가능하다. 시간복잡도 연산 시간복잡도 삽입 O(1) 제거 O(1) 앞/뒤 원소 확인 O(1) Deque 양쪽 끝에서 삽입과 삭제가 전부 가능하며 Double Ended Queue라는 뜻을 가지고 있다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 불가능하지만 STL deque에서는 인덱스로 원소에 접근이 가능하다. 시간복잡도 연산 시간복잡도 삽입 O(1) 제거 O(1..

https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 오른쪽에서 바라보았을때 보이는 막대기의 수를 구하는 문제이다. 자신의 오른쪽에 있는 막대기 중 자신보다 높은 막대기가 하나도 없다면 그 막대기는 보일것이다. 즉, 현재 해당 막대기가 자신의 오른쪽에 있는 막대기의 최대값보다 크다면 그 막대기는 보인다. 따라서 주어진 막대기 높이들을 스택에 넣고 제일 상위에서 부터 (즉, 오른쪽 막대기부터) 하나씩 pop하여 현재 해당 막대기와 현재 까지의 막대기 최대값..

주제 : 정렬 (sort) c++의 sort() 함수 C++ STL 함수의 sort() 함수는 quick sort 알고리즘을 바탕으로 만들어졌다. 최악의 경우에 대해서도 어느 정도 개선된 quick sort 알고리즘이라고 할 수 있다. 따라서 대부분의 경우 O(n*logn) 의 시간복잡도를 가진다. sort() 함수 사용법 C++의 algorithm 헤더에 sort() 함수가 포함되어 있다. 사용 방법은 다음과 같다. #include #include using namespace std; int main() { int a[10] = {9, 3, 5, 4, 1, 10, 8, 5, 7, 2}; sort(a, a + 10); for (int i = 0; i < 10; i++) { cout

주제 : 시간복잡도와 Big-O 표기법, 브루트 포스와 백트래킹 Big-O 표기법 알고리즘의 성능을 수학적으로 표기해주는 방법. 시간과 공간 복잡도를 표기할 수 있다. O (1) > O (logn) > O (n) > O (nlogn) > O (n^2) > O (n^3) > O (2^n) 위와 같은 성능 순서를 가지고 있다. 브루트 포스 가능한 모든 경우를 다 파악하는 경우 보통 브루트 포스라고 한다. (for문으로 전수조사..) 반복문이 쌓일 수록 지수의 성능을 가지게 된다. 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 이름 그대로 이 경우가 아니다 싶으면 다시 돌아가서 다른 경우를 찾는 것. 브루트 포스보다 경우의 수가 줄어들 수 있지만, 최악의 경우 성능이 브루트 포..