본문 바로가기
반응형
[PCCP] 기출문제 시험환경- 문항수: 3문항- 시간: 90분1회미로 탈출 명령어(150365) / 미로 탈출 명령어(150365) 해설택배 배달과 수거하기(150369) / 택배 배달과 수거하기(150369) 해설개인정보 수집 유효기간(150370) / 개인정보 수집 유효기간(150370) 해설2회110 옮기기(77886) / 110 옮기기(77886) 해설쿼드압축 후 개수 세기(68936) / 쿼드압축 후 개수 세기(68936) 해설없는 숫자 더하기(86051) / 없는 숫자 더하기(86051) 해설3회불량 사용자(64064) / 불량 사용자(64064) 해설k진수에서 소수 개수 구하기(92335) / k진수에서 소수 개수 구하기(92335) 해설거리두기 확인하기(81302) / 거리두기 확인하기(81302) 해설4회코.. 2024. 12. 26.
[PCCP] 알고리즘 - 동적계획법 1. 이론- Dynamic Programming은 전체 문제를 한 번에 해결하는 것이 아닌 작은 부분 문제들을 해결하여 이를 활용하여 전체 문제를 해결하는 것- DP 활용 조건    - Optimal Substructure(최적부분구조): 큰 문제를 작은 문제로 나누었을 떄 동일한 작은 문제 반복 등장    - Overlapping Subproblem(중복부분문제): 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성- 해결과정    1) 점화식 세우기    2) 메모이제이션 저장소 생성    3) 재귀함수 정의 && 종료조건- 최장증가부분수열(Long Increasing Subsequence)    - 부분수열: 주어진 수열 중 전후 관계를 유지하며 일부를 뽑아 새로 만든 수열    - LIS: 부분.. 2024. 12. 15.
[PCCP] 알고리즘 - 시뮬레이션 1. 이론- 구현에 중점- 접근 방식    - 하나의 문제를 여러개로 분리    - 예외처리가 필요시 독립함수로 구현- 기본 구현    - 행렬연산: 덧셈, 뺄셈, 곱셈    - 전치행렬: arr[i][j] = arr[j][i]    - 좌표연산: 이차원 배열 && 오프셋값(dx, dy)    - 좌우대칭: arr[i][j] = arr[i][(N-1)-j]    - 반시계 90도 회전연산: arr[i][j] = arr[j][(N-1)-i]- 예제: 배열 회전, 행렬곱, 전치행렬, 달팽이수열 2. 언어별 문법  3.  추천 문제 - Lv 2: 이진 변환 반복하기(70129) / 이진 변환 반복하기(70129) 해설- Lv 2: 롤케이크 자르기(132265) / 롤케이크 자르기(132265) 해설- Lv 2.. 2024. 12. 15.
[PCCP] 알고리즘 - 그리디 1. 이론- Greedy:    - 지역 최적해를 구함. 전역 최적해 장담 불가.    - 해결과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택을 번복하지 않음- 그리디 알고리즘 최적해 보장 조건    - Optimal Substructure(최적 부분 구조): 부분해 과정이 최적해 과정과 일치    - Greedy Selection Property(그리디 선택 속성): 선택과정이 다른 과정에 영향을 주지 않음- Spanning Tree    1) 모든 정점이 간선으로 연결    2) 간선의 개수는 (정점의 개수 - 1)과 동일- Minimum Spanning Tree(최소신장트리)    1) 모든 정점이 간선으로 연결    2) 간선의 개수는 (정점의 개수 - 1)과 동일    3) 간선.. 2024. 12. 15.
[PCCP] 자료구조 - 집합 1. 이론- 집합(set): 순서와 중복이 없는 원소를 갖는 자료구조- 집합 종류: 유한집합, 무한집합, 공집합, 상호배타적 집합- 상호배타적 집합: 교집합이 없는 집합 관계- 상호배타적 집합 활용분야: 이미지 분할, 도로네트워크 교차로, 최소신장트리의 사이클 확인, 게임개발시 물체 충돌 문제, 클러스터링 방지- 집합의 연산: 합치기, 탐색- 집합 표현: 배열을 활용한 트리 사용. 배열의 인덱스는 자신, 배열값은 부모 노드를 의미. 루트노드는 인덱스와 값이 동일- 루트 노드의 개수는 집합의 개수- Union-Find 알고리즘: union(합치기), find(탐색).- find 연산: 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합인지 확인. 재귀로 구현+) find 연산 비용은 .. 2024. 12. 14.
[PCCP] 자료구조 - 해시 1. 이론- 해시(hash): 해시함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조- 해시 특징: 단방향 동작(키를 통한 값 탐색만 가능). 키가 값의 인덱스이므로 값을 찾기 위한 탐색과정이 없음. 값을 인덱스로 사용하려면 변환 과정이 필요- 해시테이블: 키와 값이 저장되어 있는 공간- 버킷: 해시테이블의 각 데이터- 해시 ADT:  (시간복잡도)- 임의 접근(탐색): O(1)- 삽입:- 삭제: (선택시 고려할 점)- 단방향 검색이지만 빠른 검색이 필요한 경우 (해시함수 구현시 고려사항)- 해시함수 변환값은 해시테이블의 크기보다 작아야함- 변환값의 충돌이 최대한 적어야함+) 충돌: 서로 다른 두 키에 값을 적용시 동일한 결과를 의미 (주요 해시함수)- 나.. 2024. 12. 14.
[PCCP] 자료구조 - 덱 1. 이론- 덱(deque): 양쪽에서 삽입, 삭제가 일어나는 자료구조- - 덱 ADT:  (시간복잡도)- 임의 접근:- 삽입:- 삭제: (선택시 고려할 점)-   2. 프로그램 언어별 문법- 덱 선언 및 초기화- 덱 접근: 맨 앞(front), 맨 뒤(rear)- 덱 제어: 삽입, 삭제   더보기#include /* 덱 생성 및 초기화 */std::deque dq1;std::deque dq2(10); // 0으로 초기화된 10개의 원소std::deque dq3(10, 4); // 4로 초기화된 10개의 원소std::deque dq4(dq3); // dq3를 복사한 dq4 생성/* 삽입 */dq.push_front(값); // 맨 앞에 요소 삽입dq.insert(인덱스, 값); // 해당 위치에.. 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.
[PCCP] 자료구조 - 스택 1. 이론- 스택(stack): 먼저 입력한 데이터를 제일 나중에 꺼냄(FILO: First In Last Out)- 삽입 연산을 push, 꺼내는 연산을 pop- 스택 ADT: 삽입(push), 꺼내기/삭제(pop), isFull(), isEmpty(), top(최근 데이터 인덱스), data(데이터 저장공간) (시간복잡도)- - 삽입: O(1)- 삭제: O(1) (선택시 고려할 점)- 최근에 삽입한 데이터를 자주 사용하는 경우-  2. 프로그램 언어별 문법- 스택 선언 및 초기화- 스택 접근(top)- 스택 제어: 삽입(push), 삭제(pop)   더보기#include /* 스택 생성 및 초기화 */stack st;/* 삽입 */st.push(값); // 요소 삽입/* 삭제 */st.pop(); /.. 2024. 12. 14.
[PCCP] 자료구조 - 링크드리스트 1. 이론  2. 프로그램 언어별 문법더보기#include #include /* 1차원 동적배열 선언 및 초기화 */int* arr1 = (int*)malloc(sizeof(int) * 5);if (arr1 == NULL){ printf("[error]: malloc error\n");} /* 2차원 동적 배열 선언 및 초기화 */// 동적배열 해제free(arr1); (단방향 리스트: forward_list)더보기#include // 단방향 리스트 선언 및 초기화forward_list list1;forward_list list2(7); // 크기가 7forward_list list3(10, 5); // 크기가 10, 초기값은 5forward_list list4 = {1,2,3,4,5};// .. 2024. 12. 14.
반응형

티스토리툴바