전체 글

c++ 알고리즘 공부 4 - 연결리스트

연결 리스트가 무엇인가 하면, 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조입니다. 원소들은 이곳 저곳에 흩어져있습니다. 첫 번째로 연결 리스트에서는 k번째 원소를 찾기 위해 O(k)의 시간이 필요합니다. 뭔가 좀 의아할 수 있는데, 연결 리스트의 구조 상 어쩔 수가 없습니다. 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문입니다. 두 번째로 연결 리스트에서는 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1)입니다. 이 성질이 배열과 비교했을 때 큰 차이가 있는 성질이고, 연결 리스트의 굉장히 큰 장점이기도 합니다. 세 번째로 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할당이 쉽습니다. 물론 이 성..

c++ 알고리즘 공부 3 - 배열

첫 번째로 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이라서 k번째 원소의 위치를 바로 계산할 수 있게 됩니다. 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문입니다. 그렇기 때문에 k번째 원소를 O(1)에 확인하거나 변경할 수 있습니다. 두 번째로 메모리는 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없습니다. 아직 다른 자료구조를 배우지 않아서 비교를 할 수가 없는데, 다른 자료구조들을 배우고 나면 지금 이 소리가 무슨 의미인지 알 수 있을 것입니다. 세 번째로 메모리 상에 데이터들이 붙어있으니까 Cache hit rate가 높습니다. 네 번째로 메모리 상에 연속한 구간을 잡아야 하니 할당에서 다소 제약이 있습니다. 제일 짤막한건 cstring 헤더에 있는 memset 함..

c++ 알고리즘 공부2 - STL SORT

헤더를 include하여 그 안에 있는 sort()함수를 사용하시면 간편하게 정렬을 할 수 있습니다. sort() 함수는 C++ STL에서 제공하는 함수로써 각종 알고리즘 문제를 풀 때도 활용할 수 있어 자주 쓰이는데, 이 함수의 시간 복잡도는 nlogn입니다. 사용법은 헤더를 include한 뒤 sort(begin,end)로 이용. 내림차순도 공부할것.

c++ 알고리즘 공부 1 - 기초코드 작성

원래 C++에서는 배열을 선언할 때 크기를 명시해야 하고 무조건 해당 크기 안에서만 사용을 해야 합니다. 그런데 vector는 일종의 가변배열로 크기를 마음대로 늘렸다 줄였다 할 수 있습니다. 참고로 vector는 vector 헤더에 선언되어있습니다 자 이제 우리가 살펴볼 것은 STL을 함수 인자로 넘길 때 어떤 일이 생기는지에 대한 것입니다. STL도 구조체랑 비슷하게 함수 인자로 실어 보내면 복사본을 만들어서 보내기 때문에 함수에서 바꾼건 원본에 영향을 주지 않습니다. 그냥 STL을 쌩으로 함수 인자에 넣으면 복사해서 보낸다는걸 꼭 유의하셔야 합니다. 이 사실을 머릿속에 넣어둡시다. 그리고 scanf를 쓰든 cin을 쓰든 주의해야 할 것이 있는데, scanf와 cin 모두 공백을 포함한 문자열을 입력..