본문 바로가기

분류 전체보기106

[Design Patterns] Strategy Pattern Strategy Pattern 알고리즘을 동적으로 선택할 수 있게 하는 디자인 패턴 behavioral software design pattern that enables selecting an algorithm at runtime. Purpose 특정 행위를 하기 위해 교환할 수 있는 알고리즘을 정의할 수 있도록 합니다. Defines a set of encapsulated algorithms that can be swapped to carry out a specific behavior. Use When 행위기반적인 클래스들 간의 차이가 필요할 때 The only difference between many related classes is their behavior. 알고리즘의 다양한 버전, 변형이 필요.. 2021. 7. 30.
[Design Patterns] Composite Pattern Composite Pattern 클라이언트에서 단일 객체와 복합 객체 모두 동일하게 다루기 위해 사용하는 디자인 패턴 A design pattern used by clients to treat both single and complex objects the same. Purpose 각각의 객체는 독립적으로 동일한 인터페이스를 통해 중첩된 객체로 구현되어 계층구조 객체를 쉽게 만들수 있도록 합니다. Facilitates the creation of object hierarchies where each object can be treated independently or as a set of nested objects through the same interface. Use When 객체가 계층적으로 표현될.. 2021. 7. 26.
<Algorithm,C++> Merge Sort (병합 정렬, 합병 정렬) 개념, 구현예제 Merge Sort 는 유명한 정렬 알고리즘 중에 하나입니다. 최악의 시간복잡도가 O(n log n)라는 점 때문에 실제 알고리즘 문제에서도 많이 사용됩니다. stable sort(안정 정렬, 같은 우선순위의 값에 대해 정렬 전후 순서 동일) , 메모리가 2배로 든다는 점이 특징입니다. 다른 개념적인 설명은 뒤로하고 여기선 오로지 외워서 사용하기 편한 방법을 하나 소개합니다. 톱다운으로 구현한 방법입니다. #include #define MAX 10 int tmp[MAX]; using namespace std; void mergeSort(int arr[], int s, int e) { //base condition if (s >= e) return; //divide int m = (s + e) / 2; /.. 2021. 2. 16.
[C++, 세그먼트 트리, 데이터추가 반영] 백준 2042번 구간 합 구하기 www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 21.02.17 데이터 추가 반영하였습니다. 세그먼트 트리의 입문문제라고 할 수 있다. 따라서 세그먼트 트리 초보자에게 구현이 간편한 방법을 소개하고자 한다. update함수와 query함수 단 2개의 함수만 이용해서 해결할 수 있는 방법이다. 세그먼트 트리 초기화를 update문을 이용해서 구현하면 실행시간은 늘어나지만 구현이 간편해진다는 장점이 있다.. 2020. 11. 22.
프로그래머스 SQL 문제 총정리 https://programmers.co.kr/learn/challenges 코딩테스트 연습 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr SELECT 모든 레코드 조회하기 동물 보호소에 들어온 모든 동물의 정보를 ANIMAL_ID순으로 조회하는 SQL문을 작성해주세요. SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID 역순 정렬하기 동물 보호소에 들어온 모든 동물의 이름과 보호 시작일을 조회하는 SQL문을 작성해주세요. SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC 아픈 동물 찾기 동물 보호소에 들어온 동물 중 아픈 동물1의 아이디와 이름을 조회하는 SQL 문을 작성해주세요. .. 2020. 6. 4.
[C++,구현, 중복 순열] 백준 17825번 주사위 윷놀이 문제풀이 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위 윷놀이, 구현에서도 어려운 축에 속한다고 생각한다. 주사위에서 나올 수 있는 10개의 수 순서에 각각 4개의 말들을 매칭 시킨다고 하면 중복 순열이다. 전체의 경우의 수는 4^10 가지가 나온다. 처음에는 아래와 같이 풀이하였다. #include #include using namespace std; typedef struct lo { int x, y; }; int pan[4][30] = { { -1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 3.. 2020. 6. 1.
최소 신장 트리 (MST , Minium Spanning Tree) 최소 신장 트리(MST, Minium Spanning Tree) 신장 트리 중에서 간선의 가중치의 합이 최소인 것 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 연결한 트리 신장 트리의 특징 모든 노드는 서로 연결되어 있다. 간선(edge)의 수 E는 노드의 수 V에서 1을 뺀 것과 같다. 트리(Tree) 그래프의 일종으로 사이클이 없는 연결그래프이다. 트리의 특징 root node를 제외한 모든 node는 단 하나의 부모 node만 가진다. 임의의 노드에서 다른 노드로 가는 경로는 유일하다. 회로(cycle)가 존재하지 않는다. 간선(edge)를 하나 자르면 트리가 두 개로 분리된다. 최소 신장 트리 구현 방법 Kruskal 알고리즘 탐욕적인 방법(greedy method)을 이용해 M.. 2020. 5. 25.
[Error,C++]Expression must be a modifiable lvalue 해결법 코딩하다 "Expression must be a modifiable lvalue" 오류가 가끔 뜬다. 직역하면 "표현식은 수정할 수 있는 lvaue이어야만 한다."라는 뜻이다. 여기까지 찾아왔다면 무슨 소리인가??? 무엇을 잘 못 썼다는 말인 거 같은데 난 잘 못 쓴 게 없다는 분들이 대다수라 생각한다. 하지만 결론적으로 잘못 쓰셨다. 표현식을 하나하나 찬찬히 뜯어보시길 바란다. 저 또한 같은 생각을 했고 다시 실수하지 않기 위해 이글을 쓴다.. 그래도 여기서 바로 알고싶다는 분들을 위해 stackoverflow에 있는 사례를 하나 들겠다. int M = 3; int C = 5; int match = 3; for ( int k =0; k < C; k ++ ) { match --; if ( match ==.. 2020. 5. 25.
windows 10 가상 데스크톱 단축키 windows 10 가상 데스크톱 단축키를 소개한다. 생성 : Ctrl + Window() + D 삭제 : Ctrl + Window() + F4 이동 : Ctrl + Window() + ←, → 전체 보기 : Window() + Tab 2020. 5. 18.
빅-오 표기법 (Big-Oh Natation), 시간 복잡도(Time Complexity) 시간 복잡도란?문제를 해결하는데 걸리는 시간과 입력의 함수 관계해당 알고리즘이 얼마나 효율적인지 정량화해 나타내는 지표빅-오 표기법이란?입력값에 따른 알고리즘의 실행 시간 성장률(시간 복잡도)을 점근적 상한선으로 나타낸 수학적 표기법 해당 알고리즘의 성능을 나타내기 위해선 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다.입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아볼 필요성이 있습니다. 이것을 실행 시간의 성장률(rate of growth)이라 합니다.성장률에서 상수 계수와 중요하지 않은 항목을 제거한 것을 점근적 표기법(asymptotic notation)이라 합니다.big-Θ중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실.. 2020. 5. 14.
vector, unordered_map 전체 순회 알고리즘 속도 비교 vector는 배열을, unordered_map은 hash_table를 사용해 hash를 구현한 모두 유명한 자료구조 컨테이너이다. unordered_map의 탐색 시간 복잡도는 O(1)이다. 그렇다면 전체 순회의 경우 vector와 비교할 때는 어떻게 될까? 단순히 시간복잡도만을 계산하면 둘 다 O(n)인데 어떤 것이 더 빠를까? 직접 해보자 #include #include #include #include #define COUNTER 1000000 int main() { using namespace std::chrono; // std::chrono::milliseconds is an instatiation of std::chrono::duration: int tmp; std::vector v; std:.. 2020. 5. 3.
[Python, hash] map, BOJ 1920번 수 찾기 문제 풀이 python의 map 함수란? map(function, iterable, ...) 첫번째 인자로 함수의 이름이 들어온다. 두번째 인자로 iterable한 데이터(ex list, dictionary)가 위치한다. 즉 두번째 인자를 하나씩 첫번째 함수의 인자로 넣어 list 형태로 반환하는 함수이다. hash 개념을 구현한 함수이다. BOJ 1920번 수 찾기 문제풀이 위 문제의 의도는 원래 이분탐색을 통해 풀이하는 것이 정해이지만 파이썬의 map함수를 이용하여 hash 개념으로도 풀 수 있다. N, A = int(input()), {i: 1 for i in map(int, input().split())} M = input() for i in map(int, input().split()): print(A.g.. 2020. 1. 5.

티스토리툴바