[PCCP] Lv1: 모의고사(42840) 해설
문제- 문제 링크: 모의고사 해설- 자료구조: - 시간복잡도: (풀이과정)1) 수포자별 패턴 정의2) 수포자별 맞힌 문제 개수 기록3) 가장 많은 문제를 맞힌 수포자 기록 코드(C언어) (C++) solution 1)- N: answers의 길이- 각 수포자들 패턴과 정답 비교: O(N)- scores 순회하며 가장 높은 점수 탐색하여 수포자 추가 연산: O(1)- 최종 시간 복잡도: O(N)더보기#include #include #include using namespace std;// 각 수포자 패턴 정의vector first = {1, 2, 3, 4, 5};vector second = {2, 1, 2, 3, 2, 4, 2, 5};vector third = {3, 3, 1, 1, 2, 2, 4, 4,..
2024. 12. 23.
[PCCP] 자료구조 - 집합
1. 이론- 집합(set): 순서와 중복이 없는 원소를 갖는 자료구조- 집합 종류: 유한집합, 무한집합, 공집합, 상호배타적 집합- 상호배타적 집합: 교집합이 없는 집합 관계- 상호배타적 집합 활용분야: 이미지 분할, 도로네트워크 교차로, 최소신장트리의 사이클 확인, 게임개발시 물체 충돌 문제, 클러스터링 방지- 집합의 연산: 합치기, 탐색- 집합 표현: 배열을 활용한 트리 사용. 배열의 인덱스는 자신, 배열값은 부모 노드를 의미. 루트노드는 인덱스와 값이 동일- 루트 노드의 개수는 집합의 개수- Union-Find 알고리즘: union(합치기), find(탐색).- find 연산: 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합인지 확인. 재귀로 구현+) find 연산 비용은 ..
2024. 12. 14.
[PCCP] 자료구조 - 큐
1. 이론- 큐(queue): 먼저 들어간 데이터가 먼저 나오는 자료구조(FIFO: First In First Out)- 삽입 연산을 enqueue, 꺼내는 연산을 dequeue- 큐 ADT: push(삽입), pop(꺼내기), isFull(), isEmpty(), front(오래된 삽입 데이터), rear(최근 삽입 데이터), data(데이터 저장공간)- 큐 활용 분야: 작업 대기열, 로드밸런서, 이벤트 처리 (시간복잡도)- 임의 접근: - 삽입: - 삭제: (선택시 고려할 점)- 2. 프로그램 언어별 문법- 큐 선언 및 초기화- 큐 접근: 맨 앞(front), 맨 뒤(rear)- 큐 제어: 삽입(push), 삭제(pop) 더보기#include /* 큐 생성 및 초기화 */std::queue ..
2024. 12. 14.
