알고리즘13 [C#/Unity][디자인패턴] 템플릿 메서드 패턴(Template Method Pattern) 1. 템플릿 메서드 패턴이란? - 기능의 뼈대(템플릿)와 실제 구현을 분리하는 패턴. - 알고리즘의 구조를 메서드에 정의하고, 하위 클래스에서 알고리즘 구조의 변경헚이 알고리즘을 재정의하는 패턴. - 상속을 통해 슈퍼클래스의 기능을 확장할 때 사용하는 가장 대표적인 방법. - 변하지 않는 기능을 슈퍼클래스에 만들어두고, 자주 변경되면 확장할 기능은 서브클래스에 만든다. 2. 템플릿 메서드 패턴을 사용하는 경우 - 알고리즘이 단계별로 나누어 지거나, 같은 역할을 하는 메서드이지만 여러곳에서 다른 형태로 사용이 필요한 경우 사용. - 알고리즘의 특정 단계들만 확장할 수 있도록 하고 싶지만 알고리즘의 구조는 확장하지 못하도록 하고 싶은 경우 3. 템플릿 메서드 패턴의 장점 - 중복을 줄이고, 코드의 재사용성을.. 2023. 12. 28. [C#/Unity][디자인패턴] 전략 패턴(Strategy Pattern) 1. 전략 패턴이란? - 정책 패턴(Policy Pattern)이라고도 불리며 특정 알고리즘을 별도로 분리하여 설계하는 방법을 말함. - 알고리즘군을 정의하고 캡슐화해서 각각의 알고리즘군을 수정해서 사용할 수 있게 해줌. - 실행 중에 알고리즘(전략)을 선택하여 객체 동작을 실시간으로 바뀌도록 할 수 있게 하는 행위 디자인 패턴. - 객체의 행위를 변경하고 싶을 때, 직접 수정하지 않고 전략이라 불리는 캡슐화된 알고리즘을 변경. - 특정한 계열의 알고리즘들을 정의하고, 각 알고리즘을 캡슐화하며, 이 알고리즘들을 해당 계열 안에서 상호 교체가 가능하도록 만든다. - 객체들이 할 수 있는 각각의 행위에 대해 전략 클래스를 생성하고, 유사한 행위들을 캡슐화하는 인터페이스를 정의하여 객체의 행위를 동적으로 바꾸.. 2023. 12. 28. [프로그래머스][C++] 최댓값과 최솟값 #include #include #include using namespace std; string solution(string s) { string answer = ""; vector nums; for(int i = 0; i < s.size(); i++) { int addNum = 0; bool isMinus = false; while(s[i] != ' ' && i < s.size()) { int curNum = s[i] - '0'; // 음수인 경우 if(s[i] == '-') { isMinus = true; i++; continue; } addNum = addNum * 10 + curNum; i++; } if(isMinus) addNum *= -1; nums.push_back(addNum); } so.. 2023. 10. 30. [프로그래머스][C++] 할 일 목록 1 #include #include using namespace std; vector solution(vector todo_list, vector finished) { vector answer; for(int i = 0; i < todo_list.size(); i++) { if(!finished[i]) { // 일을 못 마침 answer.push_back(todo_list[i]); } } return answer; } 1. finished와 todo_list에서 같은 인덱스를 사용하므로 어느 한쪽의 크기를 받아 반복문을 진행하며 원소에 접근한다. 2. todo_list의 각 값을 finished를 이용해 체크하고, 일을 마치지 못 한 경우 라면 answer에 todo_list의 해당 원소를 넣어줌. 3... 2023. 10. 30. [알고리즘] DFS와 BFS 1. DFS(Depth-First Search) - 깊이 우선 탐색 - 루트 노드나 임의 노드에서 "다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색"하는 방법 - 스택이나 재귀함수를 이용해 구현 - 모든 경로를 방문해야 할 경우 적합 - 인접 행렬 : O(V^2) - 인접 리스트 : O(V+E) // V는 접점, E는 간선 2. BFS(Breadth-First Search) - 너비 우선 탐색 - 루트 노드나 임의 노드에서 "인접한 노드부터 먼저 탐색"하는 방법 - 큐를 이용해 구현 - 최소 비용으로 탐색을 진행할 때 적합\ - 인접 행렬 : O(V^2) - 인접 리스트 : O(V+E) 3. 소스코드(C++) // DFS #include #include using namespace std; int .. 2023. 10. 30. [알고리즘] 해시 테이블(Hash Table) 1. 해시 테이블 - 완전 탐색(브루트 포스)으로 시간초과에 빠지게 되는 문제들을 풀기 위해 필요함 - Key, Value로 데이터를 저장하는 자료구조 - 데이터를 빠르게 검색할 수 있음 - 각 key에 따라 고유한 index를 생성하고 이 index 값을 활용해 값을 저장하거나 검색한다. - 미리 key값으로 데이터들을 저장해 놓으면 데이터를 찾기 쉽다. - 평균 시간복잡도 : O(1) 2. 해시 함수에서 고유 인덱스 값을 설정하는 방법 1) Division Method - 나눗셈을 이용하는 방법 - 입력값을 테이블의 크기로 나누어 계산 - 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려짐 2) Digit Folding - 각 key의 문자열을 ASCII 코드로 바꾸고.. 2023. 10. 24. [알고리즘] 이분 탐색(Binary Search) 1. 이분 탐색 - 정렬된 배열에서 찾고자 하는 수를 찾는 방법 - 계속해서 두가지 경우로 나누면서 탐색 - 인덱스를 이용해 탐색 - 시간복잡도 : O(logN) 2. 탐색 방법 1. 배열의 첫번째 인덱스와 마지막 인덱스 번호를 각각 left, right로 저장 2. left와 right의 중간지점인 mid의 인덱스를 (left+right)/2 를 이용해 구함 3. left가 right보다 커지는 시점까지 반복 -> left보다 right가 커지면 찾고자 하는 수가 없는 경우임 4. 배열의 mid번째 값과 내가 찾고자 하는 값을 비교 4-1. 내가 찾고자 하는 값이 mid보다 작은 경우 - 최소한 mid - 1번째 인덱스의 값보다는 작거나 같기 때문에 right를 mid-1로 변경시켜 최대값을 바꿔줌(구.. 2023. 10. 18. [백준 2750번][C++] 수 정렬하기 - 5. 삽입 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void InsertionSort(vector& v) { for (int i = 1; i = 0; j--) { if (insertVal swap 아님 // -> 뒤의 원소에 앞의 원소의 값을 넣음 v[j + 1] = v[j]; insertIndex--; } else { /.. 2023. 7. 18. [백준 2750번][C++] 수 정렬하기 - 4. 힙 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void MakeMaxHeap(vector& v) { // 최대힙을 생성하는 함수 // 완전이진트리의 노드번호는 1번부터 시작하기때문에 0번 인덱스를 1번으로 취급해야함 // 0번을 시작으로할때 // 자식노드번호가 홀수인 경우, 부모인덱스 = 자식 인덱스 / 2 // 자식노드번호가 짝수인 경우, 부모인덱스 = 자식 인덱스 / 2 - 1 for (int i = 1; i 가장 큰 수라면 밑 부터 차례.. 2023. 7. 17. [백준 2750번][C++] 수 정렬하기 - 3. 퀵 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int Partition(vector& v, int left, int right) { // left번 인덱스부터 right번 인덱스를 pivot번 인덱스의 원소를 기준으로 큰 값, 작은 값을 나눔 int pivot = left; // 기준 인덱스 값(고정) int swap = left; // 중간중간 swap에 사용될 인덱스 값 for (int i = left + 1; i v[i]) { swap++; // swap(i swap) int temp = v[i]; v[i] = v[swap]; v[swap] = te.. 2023. 7. 16. [백준 2750번][C++] 수 정렬하기 - 2. 선택 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; vector v; // 원소 입력 while (N > 0) { int x; cin >> x; v.push_back(x); N--; } // 2. 선택정렬 for (int i = 0; i < v.size() - 1; i++) // 마지막 원소는 정렬할 필요없음(이미정렬되어있으므로) { // 최소값의 인덱스와 값을 저장할 공간 생성 int minVal = v[i]; int minIndex = i; for (int j = i + 1; j < v.size(); j.. 2023. 7. 16. [백준 2750번][C++] 수 정렬하기 - 1. 버블 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; vector v; // 원소 입력 while (N > 0) { int x; cin >> x; v.push_back(x); N--; } // 1. 버블 정렬 for (int i = v.size() - 1; i > 0; i--) { for (int j = 0; j v[j + 1]) { int temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } // 원소 출력 for (int i.. 2023. 7. 15. 이전 1 2 다음
