본문 바로가기

분류 전체보기199

[0x04] 연결리스트 정의와 성질 성질 임의의 위치에 있는 원소를 확인/변경 : O(N) (불연속이기 때문에 그 원소까지 찾아가야 함) 임의의 위치에 원소를 추가/제거 : O(1) 원소들이 메모리 상에 연결되어 있지 않아 cache hit rate가 낮지만 할당이 다소 쉬움 종류 단일 연결 리스트 single linked list 이중 연결 리스트 doubly linked list 원형 연결 리스트 circular linked list 배열 vs 연결 리스트 overhead : 앞, 뒤 원소의 주소값을 가지고 있어야 한다 (2^n byte이면 n만큼 추가로 필요) 구현 struct Node { struct Node *prev, *next; int data; } 야매 연결리스트 const int MAX = 1000005; in.. 2023. 6. 20.

[0x03] 배열 배열 정의 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양 overhead가 거의 없음 메모리가 붙어있으므로 cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 연산 임의의 위치 원소 확인/변경 : O(1) 원소를 끝에 추가 / 마지막 원소 변경 : O(1) 임의의 위치에 원소 추가/제거 : O(N) → 뒤에 원소들 한 칸 뒤로 밀어야 함 초기화 전역변수로 선언할 경우 int는 0으로 초기화 지역변수는 쓰레기값 들어가기 때문에 { } 등으로 초기화해야 함 int a[21]; int b[21][21]; memset (비추천) memset(a, 0, sizeof a); memset(b, 0, .. 2023. 6. 20.

[0x02] 기초 코드 작성 요령 2 함수 인자 배열을 인자로 넘기면 주소값이 넘어간다 변수를 인자로 넘기면 복사된 값이 들어간다 & (reference)를 사용하면 참조 대상의 주소 정보만 넘어감 STL standard template library STL을 함수 인자로 넘길 때 그냥 STL을 함수 인자로 실어보내면 복사본을 넘기는 것 // 크기가 n인 vector 2개를 비교한다고 했을 때 // n만큼 복사하고 보내야 하기 때문에 O(N) 시간 복잡도 bool cmp1(vector v1, vector v2, int idx){ return v1[idx] > v2[idx] } 표준 입출력 공백 포함 문자열 입력 scanf와 cin 모두 공백 포함 문자열 입력이 까다롭다 해결 방법 scanf의 옵션 char a1[10]; scanf("%[^\.. 2023. 6. 20.

[0x01] 기초 코드 작성 요령 1 공간복잡도 512 MB = 1.2억개 int ( 1 int = 4B) ⇒ 이렇게 풀이되면 틀린 것! 정수 자료형 char (1 byte) : 2^7 - 1(127) short (2 byte) : 2^15 - 1(32767) int (4 byte) : 2^31 - 1 = 2.1 * 10^9 (21억) long long (8 byte) : 2^63 - 1 = 9.2 * 10^18 실수 자료형 2의 음수 승을 이용해 이진수로 나타낼 수 있음 float (4byte) double (8byte) 실수의 저장/연산 과정에서 반드시 오차가 발생할 수밖에 없다fraction field의 사이즈가 유한하기 때문에 무한소수를 완벽하게 표현할 수 없고 자료형에 따라 반올림해야 함 float : 유효숫자 6자리 double .. 2023. 6. 20.

이전 1 ··· 4 5 6 7 8 9 10 ··· 50 다음

티스토리툴바