알고리즘39 [C++] 데이터 구조(1) - Dynamic arrays(vector, string) 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. 데이터 구조는 컴퓨터 메모리에 데이터를 저장하는 방법이다. 문제에 적합한 데이터 구조를 선택하는 것은 중요하다. 왜냐하면 각각의 데이터 구조는 고유의 장단점을 지니기 때문이다. 가장 중요한 질문은 "어떤 작업이 선택된 데이터 구조에서 효율적인가?" 이다. Dynamic arrays(동적 배열) 동적 배열은 작업 실행 동안 크기를 바꿀 수 있는 배열을 말한다. C++에서 가장 유명한 동적 배열은 vector 구조이다. 1. vector 구조 1.1 빈 벡터 생성과 요소 추가 vector v; v.push_back(3); // [3] v.push_back(2); // [3,2] v.push.. 2021. 6. 12. [C++] 정렬 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. 정렬은 기본적인 알고리즘 설계 문제이다. 다양한 효율적인 알고리즘은 서브루틴으로서 정렬을 채택한다. 왜냐하면 요소들이 정렬되어 있다면, 데이터를 다루기 쉬워지기 때문이다. 효율적인 일반 알고리즘은 O(nlogn)시간에서 작동한다. O(n^2) 알고리즘 대표적인 O(n^2) 정렬 알고리즘은 "버블 정렬"이다. 버블 정렬은 n라운드로 구성되며, 각 라운드마다 알고리즘을 반복한다. 1. 두 연속 원소가 올바른 정렬이 아닐 시, 순서를 바꾼다. for(int i=0; i 2021. 6. 6. [C++][BOJ/백준][단계별로 풀어보기] 5. 1차원 배열 1. (10818번) 1차원 배열 단계 - 일반 풀이 #include using namespace std; int main() { int N; cin >> N; int *array; array = new int[N]; int Min, Max; for(int i = 0; i > array[i]; } Min = array[0]; Max = array[0]; for(int i = 0; i = array[i]) Min = array[i]; else if(Max score[i]; } sort(score, score+n); double s[n]; // 조작된 점수 double sum; for(int i = 0; i s; for(int j = 0; j.. 2021. 6. 6. 그래프 탐색 알고리즘 전체 탐색의 경우 for 반복문으로 구현이 가능하다. 하지만, 배열을 단순히 살펴보는 것으로 문제를 풀 수 없는 경우가 있다. 이를 해결하기 위해 효과적인 그래프 탐색 알고리즘이 필요하다. 1. 그래프 탐색 알고리즘 이름에서 알 수 있듯이, 주어진 상황을 그래프로 표현하여 효율적인 탐색을 한다. 이때, 효율적인 탐색으로 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 그림 출처 : 위키백과(wikipedia) 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 용어 설명 노드(정점): 그림의 동그라미들 엣지(변) : 동그라미를 잇는 선 그래프 : 정점과 변으로 표현되는 구조 트리 구조 : 정점과 변에 루프(한 바퀴 돌 수 있는 부분)가 없는 구조 탐색 : 정점을 하나씩 확인하는 것 2. .. 2021. 6. 4. [C++] 기초 문법 1. if else 예시) 짝수 판별 : 짝수 = 1, 홀수 = 0 #include using namespace std; int main(int a) { cin >> a; if (a % 2 == 0) cout a; for(int i = 0; i s[i]; m[s[i]]++; } map::iterator iter = m.begin(); while(iter != m.end()) { cout 2021. 6. 3. 이전 1 ··· 3 4 5 6 7 8 다음 728x90 반응형
