태연한 컴공생

• 포인터 프로그래밍에서 메모리의 특정 위치를 가리키는 변수이다. 포인터는 Linked representation으로 사용된다. Linked representation은 데이터를 연결된 노드의 집합으로 나타내는 방법이다. 각 노드는 데이터를 저장하는 부분과 다음 노드를 가리키는 포인터로 구성된다. 변수는 dot 연산자( . ), 포인터는 화살표 연산자( - > )를 통해 접근한다. • Self-referential Class(자기 참조 클래스) 동일한 클래스 유형의 다른 객체를 가리키는 포인터를 멤버 변수로 포함하는 클래스이다. link라는 포인터에다가 Node라는 주소값을 넣어주면 그 Node를 가리킨다 라고 생각하면 쉽다. • Pros & Cons (vs 배열) 장점 중간에 아이템 삽입이 용이하다. ..

• STL Queue STL Queue의 API는 다음과 같다. #include std :: queue name; // Queue 선언 void name.push(data_type x); // enqueue data_type name.front(); // peek void name.pop(); // dequeue int name.size(); bool name.empty(); • 미로 탐색 문제 문제 정의 Input : 2차원 배열의 미로 Output : 성공 or 실패 즉 s에서 t로 갈 수 있냐는 문제이다. 길찾기 방법 DFS(Depth First Search) : 깊이 우선 탐색 - 스택 기반 동작 BFS(Breadth First Search) : 넓이 우선 탐색 - 큐 기반 동작 주의할 점 갔던 ..

• Queue 큐는 '대기열'을 뜻한다. 큐의 가장 큰 특징은 'FIFO'(First In, Firtst Out) 이다. 먼저 온 순서대로 결제하는 계산대를 생각하면 쉽다. 큐의 구조 front(앞단) & rear(끝단) 주요 연산자 Enqueue(인큐) : 큐의 끝단에 아이템을 삽입한다. Dequeue(디큐) : 큐의 앞단에서 아이템을 제거한다. • 부가 연산자 empty() : 큐가 비어있으면 true를 반환한다. 그렇지 않으면 false. full() : 큐가 가득차면 true를 반환한다. 그렇지 않으면 false. peek() : 맨 앞단에 있는 아이템의 값을 반환한다.(삭제하지는 않는다.) size() : 큐에 있는 원소의 개수를 반환한다. • 배열로 구현한 Queue 몇번의 연산 이후에 앞단에..

• STL Vector 우선 STL이란 Standard Template Library(표준 템플릿 라이브러리)의 약자이다. C++ 언어로 프로그래밍 하는데 필요한 자료구조와 알고리즘을 제공해준다. Vector는 STL의 컨테이너 중 하나로, 동적 배열을 나타낸다. Vector의 연산은 다음과 같다.#include std :: vector name; // vector 선언 std :: vector name(size); name.size() // std::vector의 요수 수 반환 name.empty() // name이 비어있는지 확인 name.push_back() // name 끝에 요소 추가 name.pop_back() // name 끝에 있는 요소 제거 • STL Stack 용량 제한이 없고 템플릿 ..

• Stack 스택은 말 그대로 '쌓아놓은 더미'를 뜻한다. 스택의 가장 큰 특징은 'LIFO'(Last In First Out) 이다. 다시 말해, 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미이다. 스택의 연산은 top(상단)에서만 진행된다. 주요 연산자 push : 삽입 연산 pop : 삭제 연산(삭제&반환) • Function call stack 반복적으로 함수를 호출하는 무한 루프가 있는 경우 스택 오버플로우가 발생할 수 있다. • 부가연산자 peek() : 스택의 맨 위에 있는 데이터를 제거하지 않고 반환한다. empty() : 할당된 공간에 삽입된 아이템이 없을 때 반환한다. / 아이템이 한개라도 있으면 false. full() : 할당된 공간이 모두 채워졌을때 반환한다. / 공간이 ..

• OOP(Object-Oriented Programming) 객체 지향 프로그래밍 '객체 관점'으로 데이터와 함수를 동시에 관리할 수 있다. 데이터와 함수가 서로 떨어져 있으면 생산성이 떨어지기 때문에 하나로 합치기 위해 우리는 객체 지향 프로그래밍을 알아야 한다! • 클래스를 정의하는 방법 class 키워드를 이용해 클래스를 정의한다. 클래스에는 멤버 점근자가 포함된다. 1. private : 외부 접근 불가능 2. protected(상속) : 상속 구조 상황에서의 접근지정자 3. public : 외부와 내부 모두 접근 가능 일반적으로 데이터는 일관성 유지와 개발자가 의도한 방향성을 위해 private, 메소드는 외부에서 함수를 호출하기 위해 public이 사용된다. class Name { // Na..

• 입력과 출력을 C와 C++에서 정의하는 방식 C C++ Header #include #include Input scanf() std::cin >> Output printf() std::cout num; // 입력 받은 정수 출력 std::cout

1. Big-O Notation Big-O Notaion은 Worst Case에 대한 상한을 제시하여 주어진 입력 크기에 대해 알고리즘이 Big-O로 표현된 함수보다 더 나빠질 수 없다는 것을 의미한다. 즉, 우리가 관심있는 시간복잡도가 Big-O 집합 안에 속해야 한다. (작게 수행되어야 한다.) 정의를 이용해서 어떤 시간복잡도가 Big-O에 속하는 것을 증명하는 문제가 자주 출제되는데, 이때 우리는 상수C와 n0를 찾아야 한다. 예를 들어 T(n) = 5n²이고 이때 T(n) ∈ O(n²)이라면, C(T(n)의 상수라고 가정)는 6, n0는 1이 되어야 한다.(여러 정답중 1개) Basic Operation에서 n0가 1일때 보통 '상수시간 걸린다' 라고 한다. • Tight Bound & Loose..

• 알고리즘 알고리즘 : Input(입력)에서 Output(출력)으로 가는 논리적인 절차 • 알고리즘 표현 방식 Natural language(자연어) : 일상적인 언어로 표현Pseudo-code(슈도 코드) : 유사 코드(자연어와 프로그래밍 언어를 적절하게 섞는다.)Programming language(C++) • 알고리즘의 효율성 어떤 알고리즘이 가장 효율적일까? : 빠르면서 가벼운 것이 가장 효율적이다! 그렇다면 가장 효율적인 것을 판단해내기 위한 방법은 무엇일까? 자원측정법 : Time(시간), Space(공간) Empirical(정량적인 시간) : 실제로 재는 것을 의미한다. - 장점 : 실질적인 수치를 가지고 비교가 가능하다. - 단점 : 환경에 따라서 달라지며, 실제로 실험하지 않는 이상 모..