Algorithm/알고리즘 개념 정리21 해시 테이블 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. [실전 알고리즘] 투 포인터 알고리즘 설명 투 포인터 = 배열에서 원래 이중 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. [실전 알고리즘] 그리디 그리디 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 연습문제1 - 동전 0 [백준 11047] 동전 0 (tistory.com) 연습문제2 - 회의실 배정 [백준 1931] 회의실 배정 (tistory.com) 연습문제3 - 로프 [백준 2217] 로프 (tistory.com) 연습문제4 - 보물 [백준 1026] 보물 (tistory.com) 참고 BaaaaaaaarkingDog | [실전 알고리즘] 0x11강 - 그리디 (encrypted.gg) 2022. 10. 12. [실전 알고리즘] 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming, DP) 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘 ex. 피보나치 ex. DP 피보나치 문제를 DP로 해결하면 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워가는 방식으로 해결할 수 있고 N+1칸을 채우고 나면 답을 알 수 있으니 O(N)에 답을 알아낼 수 있다. 중간 결과를 저장해서 이용하는지 그렇지 않은지에 따라 극적인 시간복잡도의 차이가 발생 DP를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 연습 문제 BOJ 1463: 1로 만들기 [백준 1463] 1로 만들기 (tistory.com) BOJ 9095: 1,2,3 더하기 [백준 9095] 1,2,3 더하기 (tis.. 2022. 10. 10. [알고리즘 오답노트] 정렬 정렬 유형 * 문자열에 많이 쓰이는 함수 reverse begin과 end를 통해 전체를 바꿔도 되고 dopa.begin(), dopa.begin() + 3 이런식으로 부분만 바꿀 수 있음 substr 시작지점으로부터 몇개의 문자열을 뽑아냄 (시작지점, 몇개) 만약 시작지점만 넣게 되면 마지막까지 문자열을 뽑음 find 어떠한 문자열이 들어있나 찾음 만약 찾지 못한다면 문자열의 끝 위치인 string::npos를 반환 string dopa = "amumu is best"; int main(){ cout 2022. 10. 5. [알고리즘 오답노트] BFS BFS 유형 뽀개기 * 2차원 배열 입력 * 1. 하나씩 띄어서 입력할 때 cin >> n >> m; for(int i = 0; i > board[i][j]; 2. 붙어서 입력 cin >> n >> m; for(int i = 0; i > board[i]; int a[10][10], n, m; int main(){ cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%1d", &a[i][j]); } } * reset 할 때 fill 함수 * for(int i = 0; i < n; i++){ fill(board[i], b.. 2022. 10. 5. 이전 1 2 3 4 다음
