본문 바로가기

Algorithm197

해시 테이블 map vs hash_map (C++ 표준 unordered_map) - map Red-Black Tree 추가, 탐색, 삭제 O(logN) 정렬되어있음 - hash_map(unordered_map) 추가, 탐색, 삭제 O(1) 충돌만 하지 않고 잘 동작하면 map보다 빠른 시간에 동작 원하는 키 값을 빠르게 찾아주는데 최적화 되어 있음 - 메모리를 내주고 속도를 취한다 ex. 1-999 user (userId = 1~999) [1][2][3][ ][ ][ ][999] 해시 테이블 '테이블' 키를 알면, 데이터를 단번에 찾을 수 있음 void TestTable() { struct User { int userId = 0; //1~999 string username; }; vector users; users.. 2022. 11. 20.
[백준 1920] 수 찾기 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답 코드 #include using namespace std; int a[100005]; int n; int binarysearch(int target){ int st = 0; int en = n-1; while(st target) en = mid-1; else return 1; } return 0; // st > en일 경우 while문을 탈출 } int main(.. 2022. 11. 1.
[백준 2003] 수들의 합 2 2003번: 수들의 합 2 (acmicpc.net) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 내 풀이 #include #include #include using namespace std; int n,m; int a[10004]; int en,tot; int cnt=0; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=0;i>a[i]; } en=0; tot=a[0]; for(in.. 2022. 11. 1.
[실전 알고리즘] 투 포인터 알고리즘 설명 투 포인터 = 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘 연습문제 1 - 수 고르기 [백준 2230] 수 고르기 (tistory.com) 연습문제 2 - 부분합 [백준 1806] 부분합 (tistory.com) 참고 BaaaaaaaarkingDog | [실전 알고리즘] 0x14강 - 투 포인터 (encrypted.gg) [실전 알고리즘] 0x14강 - 투 포인터 안녕하세요, 이게 강의 목차를 16진수로 붙이니까 혼동을 주는데 이번 강의가 0x14강이니까 오리엔테이션은 빼고 20번째입니다. 아직 갈길이 좀 멀긴 하지만 꽤 많이 온 것 같습니다. 여러분들도 blog.encrypted.gg 2022. 11. 1.
[백준 1806] 부분합 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N > n >> s; for(int i = 0; i > a[i]; tot = a[0]; int en = 0; for(int st .. 2022. 11. 1.
[백준 2230] 수 고르기 2230번: 수 고르기 (acmicpc.net) 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 정답 코드 #include using namespace std; int n, m; int a[100005]; int mn = 0x7fffffff; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > a[i]; sort(a, a+n); int en = 0; for(int s.. 2022. 11. 1.

티스토리툴바