싱이의 devlog

1. 정의와 성질 정의 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조. 구조적으로 먼저 들어간 원소가 제일 나중에 나오는 구조(FILO) 🎯 참고로 스택, 큐, 덱은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 있으며 이들은 묶어 Restricted Structure이라고 함! 성질 - 원소의 추가/제거/상단 원소 확인 및 변경 1) 원소의 추가 시간복잡도는 O(1) 2) 원소의 제거 시간복잡도는 O(1) 3) 제일 상단의 원소 확인 시간복잡도는 O(1) 4) 제일 상단이 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능함! 물론 스택을 구현할 때 가장 상단이 아닌 나머지 원소들을 확인하거나 변경할 수도 있겠지만, 애초에 스택은 그런 의미로 만들어진 것이 아님! 실제 스택의 용례를 보아도 ..

1. 정의와 성질 연결리스트란? 원소들을 저장할 때 그 다음 원소가 있는 위치 정보까지 포함시키는 방식으로 데이터를 저장하는 자료구조 연결리스트 성질 k번째 원소를 확인/변경하기 위한 시간복잡도는 O(k) 3 --- 73 ---- 88 로 연결된 연결리스트에서 3번째 원소 88을 찾고 확인하고 싶다면 3을 거치고 73을 거쳐 쭉 가야하므로 시간복잡도가 O(3)임을 알 수 있음 임의의 위치에 원소를 추가하거나 제거하는 데 시간복잡도는 O(1) 메모리 상에 원소들이 불연속적으로 배치되어 있어 Cache hit rate이 낮지만 할당은 쉬움 연결리스트 종류 참고로 STL에서 제공하는 연결 리스트 컨테이너 list에서 구현하는 연결 리스트는 이중 연결 리스트임! 그리고 세 번째 원형 연결 리스트에서 그림은 단일..

1. 배열의 정의 및 성질 배열이란? 메모리 상에 원소를 연속하게 배치한 자료구조 원래 C++에서는 배열을 선언한 이후 배열의 길이를 변경하는 게 불가능하다고 하지만, 자료구조에서 배열을 이해할 때는 배열의 길이는 유동적이라고 생각하자! 배열의 성질 - 코테에는 영향이 없지만 그래도 알아두자! O(1)에 k번째 원소를 확인/변경이 가능함 배열은 메모리 상에 연속적으로 값을 저장하기 때문에 k번째 원소의 위치를 바로 계산할 수 있음. 따라서 시간복잡도는 O(1) 추가적으로 소모되는 메모리 양, 즉 오버헤드가 거의 없음 오버헤드: 프로그램 실행 중 추가적으로 사용해야 하는 시간, 메모리, 자원을 의미 Cache Hit Rate가 높음 메모리 상에 데이터 값들이 서로 붙어있으니깐 hit rate이 높음 컴구...

1. STL과 함수 인자 함수 인자 첫 번째 코드에서는 int를 함수 인자로 보내면 값이 복사되는 형태로 함수로 들어가기 때문에, main에 있는 원본 값은 변하지 않음! 두 번째 코드에서는 C++에서 배열을 함수로 넘겨주는 경우 배열의 주소를 넘겨주는 것이기 때문에 함수 인자를 받은 함수 내에서 값을 변화시키면 원본 값에도 영향을 줌. 세 번째 코드에서는 구조체의 경우를 볼 수 있는데, 첫 번째 코드와 비슷하게 구조체를 넘겨줄 때도 값이 복사되는 형태로 넘어가기 때문에 구조체 원본 값에는 영향을 주지 못함. 참조자(reference) 만약 두 값을 바꾸는 swap 함수를 구현해야됐다면 C에서는 포인터를 활용하여 swap 함수를 만들었음. (위에와 같은 맥락으로, 값만 함수 인자로 보내는 건 원본 함수에..

1. 시간 / 공간복잡도 - 시간복잡도(Time Complexity) 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 - 빅오표기법(Big-O Notation) 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 보통 시간복잡도를 표기할 때 빅오표기법을 이용 ex) O(N) : 5n+3, 2n+10logN, 10N 시간복잡도를 그래프로 나타내었을 때 우리가 유념해야 할 점! 무작정 코드를 짜지 않고, 문제를 제한 시간 내에 통과할 수 있는지 생각해봐야함 - 공간복잡도 코테 때 크게 신경쓰지 않아도 괜찮은 부분이긴 함! 512MB = 1.2억개의 int (int 하나가 4바이트니깐) 인 정도만 기억해도 좋음:) 2. 정수 자료형 short는 딱히 쓸 필요가 없음! int 자료형이 속도나 메모리..