c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공 용도: 찾으려는 key 값보다 같거나 큰 숫자가 배열의 몇 번째 index에서 처음 발견되는지 찾기 위함임(반드시 오름차순 정렬 되어 있어야 함)#include #include using namespace std;int main() { int arr[6] = { 1,2,3,4,5,6 }; cout #include #include using namespace std;int main() { vector arr = { 1,2,3,4,5,6 }; cout 이럴때 사용하자!! 1. 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색할 때2. 특정한 숫자가 몇 번 나오는지 탐색할 때
자료구조 및 알고리즘
https://ashtonsw.tistory.com/26 [자료구조] 그래프 총 정리 그래프를 표현하는 방법은 여러가지가 있다. 정점은 Vertex이고, 간선은 Edge이다. 첫번째는 인접행렬을 이용한 방식이고, 두번째는 인접리스트를 활용한 방식이다. 코딩테스트를 볼 때 보통 입력 ashtonsw.tistory.com 이전 글에서 그래프에 대한 내용을 정리했다. 이번에는 그래프에서 BFS와 DFS를 통해서 순회를 해보는 알고리즘을 구현해 보자. 그래프에서도 시작점에서 다른 모든 점으로의 최단 경로를 찾을 때 BFS를 활용할 수가 있다. BFS의 과정 중에서 현재 보는 정점으로부터 추가되는 인접한 정점은 시작점으로부터 1만큼 떨어져 있다고 가정한다. 즉, 모든 간선의 길이가 동일할 때 두 지점 사이의 거리..
그래프를 표현하는 방법은 여러가지가 있다. 정점은 Vertex이고, 간선은 Edge이다. 첫번째는 인접행렬을 이용한 방식이고, 두번째는 인접리스트를 활용한 방식이다. 코딩테스트를 볼 때 보통 입력의 경우 아래와 같이 주어진다. 5 7 3 1 2 3 4 1 5 2 5 4 3 5 2 4 우리는 이 입력을 통해 그래프를 코드로 작성할 수 있어야한다. 먼저 인접행렬을 통해서 구현해보자. 방향 그래프 (Directed Graph) int adjMatrix[10][10] = {}; int v, e; cin >> v >> e; for(int i = 0; i > u >> v; adjMatrix[u][v] = 1; } 우선 방향그래프는 인접 매트릭스 배열을 선언한 뒤 간선을..
자바 공부해야하는데 C++로 백준 풀다가 이런 함수를 알게됐다. 궁금한 건 못참으니.. 최대한 빠르게 가볍게 확인해보자.. :D 일단 unique 함수를 사용해서 vector 원소 중복 제거를 할 수 있었다. #include #include #include using namespace std; int main() { vector v = { 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 8 }; cout
시간복잡도: O(logN) 선형탐색은 O(N)에 동작하지만, 이분탐색은 O(logN)에 동작하므로, N이 커지면 커질수록 둘은 아주 큰 속도 차이가 발생한다. 이분탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해서 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가면서 찾는 탐색 방법이다. STL sort 함수를 사용해서 정렬시킨 후에 st와 en을 각각 배열의 처음과 끝으로 두고, mid = (st+en)/2를 하여 mid를 설정한다. 이후 찾고 싶은 데이터를 찾아 보고 없으면 st = mid + 1 or en = mid - 1로 변경해서 범위를 절반으로 줄이도록 한다. 다시 mid = (st+en)/2를 하고, target을 찾아나가는 것을 반복한다. 백준 1920번: 수..
해쉬 자료구조는 키에 대응되는 값을 저장하는 자료구조이다. Key 값이 특정 인물의 카드 번호라고 가정하고, value 값은 사람 이름이라고 하자. 그래서 특정 카드 번호가 누구의 것인지를 찾고자 한다. 가장 간단하게 쉬운방법으로 구현한다고 한다면, 배열에 모든 데이터를 넣고 탐색을 하는 방법이 있을 것이다. 다만 특정 데이터를 지우는 건 O(N)이고, 특정 카드번호가 누구의 것인지 찾을 때는 배열의 원소를 하나씩 살펴봐야하니 O(N)이 된다. 그런데 해쉬(Hash) 자료구조에서는 insert, erase, find, update 등의 모든 연산이 전부 O(1)이다. 배열에서 인덱스를 가지고 특정 원소를 O(1)에 찾지만, 삽입과 삭제의 경우 O(N)의 시간복잡도를 가진다. 또한 연결 리스트에서는..
주요 Sorting Algorithm을 정리해보자. Selection Sort - O(N2) 전체 배열에서 가장 큰 수를 찾고 뽑아서 처음이나 끝에 정렬하는 방법 Bubble Sort - O(N2) 앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복하면 자연스럽게 제일 큰 것부터 오른쪽에 쌓음. Merge sort - O(NlogN) 분할 정복 알고리즘의 하나 이다. - 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음..
언젠가부터 투 포인터는 코딩테스트에서 한 문제씩 나오기 시작했다고 한다. 투 포인터는 알고리즘이 적당히 이론적이고, 인덱스 하나 차이로 정답과 런타임 에러를 왔다갔다하기 때문에 구현에서의 디테일이 필요한 알고리즘이다. 투 포인터(two pointer)는 배열에서 원래 이중 for문으로 O(N2)에 처리하는 부분을 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. C언어에서의 포인터 개념은 아니고, 적당히 커서 정도로 생각하면 된다. 이렇게 시간복잡도를 줄일 수 있는 이유는 이중 for문에서 i=0일 때 j=0부터 n-1까지 돌고, i=1일때 j가 0부터 n-1까지 돈다. 이처럼 각 i에 대해서 j가 0부터 n-1까지 도는데, 이 과정에서 i=0일 때 계산하며 얻은 정보가 i=1일 때에 전혀 쓰이지 않..
