알고리즘 학습!!! 가보자구!! 😊
STL
다 중요하지만 내가 잘 모르는 분야인 vector와 deque에 대해서만 살짝 정리!
vector
메모리상에서 데이터가 연속적으로 위치하는 배열!
array는 안되는데 vector는 런타임에서 크기 조절 가능
포인터 세개로 구현
할당된 배열의 시작 주소
다음에 데이터가 삽입될 위치
할당된 배열의 끝 주소
주의사항
보통 push_back 하면 상수 시간복잡도를 가지지만 할당 공간 다 찼을 때 reallocation 이 발생해 시간이 많이 소요됨
deque
Container 앞, 뒤에 데이터를 빠르게 넣고 뺄 수 있는 double-ended queue이다.
여러개의 버퍼에 데이터를 나눠서 저장
vector는 할당된 공간이 전부 차면 배열을 통째로 새로 할당하는 반면, deque 는 버퍼 하나만 할당하면 되므로, 데이터 삽입이 언제든 O(1)임!
앞, 뒤에 삽입/삭제 기능이 동시에 필요한 경우 deque!
Vector vs Deque
vector에는 deque에는 없는 또 다른 차별점
Vector의 요소들은 메모리 상에 연속적으로 존재하는 것이 보장된다!
BUT deque는 메모리에서 요소들이 연속적이지 않다!
SO C 배열의 라이브러리와 상호작용 하거나, 공간지역성을 고려해야하는 상황에서는 deque가 불리하다!
비트 연산
AND &
OR |
XOR ^
NOT ~
왼쪽 Shift <<
오른쪽 Shift >>
사람 A 의 친구 목록이 {0, 3, 6, 7, 10, 13, 28}
B 의 친구 목록이 {0, 1, 4, 5, 6, 17, 21, 28}
A, B 모두와 친구인 사람은??
A 또는 B 와 친구인 사람은?
만약에 비트마스킹을 몰랐으면 2중 포문 돌려야 함
그리고 배열로 표현을 할 때 (마스킹 배열)
32칸에 0과 1을 놓고 표현해야 하는데 아니 이 한칸에 21억까지 표현할 수 있는데 0 아니면 1 쓰는게 말이 됨? 겁나 비효율적이네
그래서 그냥 이 배열을 그냥 하나의 숫자로 표현하면 어떨까? 2진수로 표현
근데 제한은 10만까지임 왜냐하면 2의 10만 승은 말이 안됨 ㅋㅋ
친구가 10만명이 넘어가면 비트마스킹은 포기합시다..
이제 이걸 응용해보자! 두가지 방법이 있음
- Shift 연산
왼쪽 - 오른쪽에 0 추가하면서 밀기
오른쪽 - 오른쪽 사라지면서 오른쪽으로 밀기
ex) A가 4번이랑 친구가 되었다면?
4번째 칸에 있는 0을 1로 바꾸어야 하는데 어떻게 해야 할까
2의 4승 더하기 말고 이샛기야 1 << 4 4번 시프트한 걸 더해주는 거지 1 0 0 0 0 을 만들어서
ex) A가 4번이랑 친구면 손절, 0이면 1로 하면 이렇게 반전시킬려면 어떻게 해야할까
1 << 4 랑 XOR 해보면 어때 4번째 칸 말고는 다 0이랑 연산되니깐 그대로 1은 1 0은 0이 나오는데 4번째 칸만 반전됨!!!
ex) A가 0~31 모두와 친한가?
A랑 모든 비트가 1인 수랑 똑같은지 확인해보자 A == (1 << 32) -1 32번 시프트 하면 100000~ 이렇게 되는데 1을 빼면 1111111(32개) 이렇게 되는데 이거랑 같은지 == 연산해준다!
💡 and 연산 시 0은 초기화 1은 그대로 보여주기가 된다!
응용 방법 추가
AND &, OR |
교집합, 합집합을 구하기 쉬움!
XOR ^
스위치를 구현하기 쉬움!
🔔 몇개의 bit를 바꿔서 대응되는 수를 구할 수 있음! (신기..)
char case_convert(char alphabet){
return alphabet^32;
}같은 값끼리 XOR하면 0이 되는 특징이 많은 곳에 적용 가능! 생각해보기!
🔔 직사각형의 세꼭짓점을 XOR연산 하면 남은 한 점의 좌표가 됨.. (미친..)
🔔 생각해보니 같은 값 말고 하나의 다른 값을 구하면 되는 문제라 3개중에 2개는 같은 값인데 나머지 한 값을 찾고 싶으면 XOR 연산을 3개 취해주면 같은건 0 되고 0이랑 XOR하면 그대로 나머지 값이 나옴.. (소름..)
NOT ~
비트 집합에 사용하면 가지고 있지 않은 원소들을 구할 수 있음! (뭔소리..)
음의 인덱스로 사용할 수 있음 (잘 보고 사용해야 할듯.. ㅋㅋ)
SHIFT << >>
2의 거듭제곱 곱셈/나눗셈
데이터 압축
만약 문자열 두 개를 비교할 때 대문자로만 이루어져 있다면 01000001 이 'A' 이고 01001100 이 'L'이다 대문자라면 앞에 3비트는 생략하고 뒤에 5비트만 int형 배열에 저장하여
연결 리스트
추천 공부 방법
자료구조가 한가지가 아님!
자료를 저장하는 방법이 여러개인 이유는?
장단점이 각자 다 다르기 때문!
그래서 장단점을 잘 파악하고 있는 것이 중요!
알고리즘은 자료구조를 선택하는 것이 중요하다!!!
Array VS LinkedList
이걸 직접 짤 줄 알아야 하나요..?
STL 도움을 받자.. ㅎㅎ 는 무슨
무조건 짤 줄 알아야 한다..!!
STL의 한계 진짜 기본적인 도구밖에 없음!!
LinkedList를 직접 짤 수 있어야 한다..!!!
😲 이 문제를 어떻게 풀어야 할까?
ex) 커서 문제 -> 내가 보고 있는 위치에 삽입 삭제가 이루어져야 한다! => LinkedList
LinkedList의 경우 삽입/삭제 속도가 O(1) 이지만 연산을 위해 인덱스에 접근을 하는 속도가 O(n)이다 그래서 전체 삽입/삭제 속도가 O(n)이지만 이런 경우는 내가 위치를 보고 있지 않을 때!!!
그러나 커서 문제 같이 내가 보고 있는 (커서가 위치하고 있는 곳) 에 대한 위치를 알고 있을 때 삽입 삭제가 O(1)으로 이루어져 굉장히 효율적인 자료구조가 된다!!!!
정리
비트마스킹과 연결리스트 부분에서 학습하고 정리하였는데 정말 중요하고 재밌는 시간이었다!!
이해가 안되면 직접 다 적어서 이해하고 직접 코드작성까지 진행해서 다 내 걸로 만들고 넘어가자
너무 좋은 시간이었다!
숙제
연결리스트 구현해서 암호문3 풀기
비트마스킹 연습문제 다 풀면서 익히기 (동아리실 관리하기)
연결리스트, 비트마스킹 마스터 하기
velog 정리해서 올리기
