Algorithm197 [실전 알고리즘] 큐 정의와 성질 큐: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 큐의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 상단의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 직접 구현 #include using namespace std; const int MX = 1000005; int dat[MX]; int head = 0, tail = 0; void push(int x){ dat[tail++] = x; } void pop(){ head++; } int front(){ return dat[head]; } int back(){ return dat[tail-1]; } void test(){ push(10); push(20); push.. 2022. 8. 12. [실전 알고리즘] 스택 정의와 성질 스택: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 스택의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 상단의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 코드로 직접 구현 #include using namespace std; const int MX = 1000005; int dat[MX]; int pos = 0; void push(int x){ dat[pos++] = x; } void pop(){ pos--; } int top(){ return dat[pos-1]; } void test(){ push(5); push(4); push(3); cout 2022. 8. 11. [실전 알고리즘] 연결 리스트 정의와 성질 연결 리스트: 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결리스트의 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1) 3. 원소들이 메모리상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬움 배열 vs 연결리스트 기능과 구현 STL의 List가 이중 연결 리스트 STL List 예시 #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중 L.push_front(10); // 10 1 2 cout 2022. 8. 10. [백준 1406번] 에디터 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 배운것 연결리스트는 STL에서 List로 구현되어있음 #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중 L.push_front(10); // 10 1 2 cout 2022. 8. 10. [백준 11328번] Strfry 11328번: Strfry (acmicpc.net) 11328번: Strfry C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래 www.acmicpc.net 배운 것 string 2개 비교할 때 각각 빈 배열 하나씩 총 두개 만들어줄 생각만 했는데 같은지 아닌지를 비교하는 단순한 것이라면 하나 만들고 ++ -- 해서 0이 아닌것만 골라내는 방식을 쓰는 것이 더 간단함 정답 풀이 // Authored by : OceanShape // Co-authored by : BaaaaaaaaaaarkingDog // http://boj.kr/a3d03c0124.. 2022. 8. 10. [백준 3273] 두 수의 합 3273번: 두 수의 합 (acmicpc.net) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 정답 풀이 // Authored by : BaaaaaaaaaaarkingDog // Co-authored by : - // http://boj.kr/fc842a288ef843e49e2fe5b6a8bbcf5e #include using namespace std; int a[1000001]={}; // 각 자연수의 존재 여부를 저장하는 배열, 아래에서 x-a[i.. 2022. 8. 9. 이전 1 ··· 16 17 18 19 20 21 22 ··· 33 다음
