노는 게 제일 좋아

우선순위 큐에 들어가는 비교함수와 그냥 우리가 sort 할 때 쓰는 비교함수는 쓰는 모양이 다르다. //구조체 함수자 struct cmp{ bool operator()(int a, int b){ return a > b; } }; //그냥 비교함수 bool comp(int x, int y){ return x < y; } 그래서 이용하는 방법도 다르다. vector vec; for(int i = 0; i

많은 수학 문제들이 있지만 가장 자주 나오는 문제부터 살펴보고 나머지는 교양으로 알아보자 나머지 나머지는 특히 답에 xxx로 나눈 나머지를 구하시오와 같은 문제로 많이 나오는데 이건 범위를 제한하기 위해서다. 즉, 기본 자료형의 범위를 초과한다고 생각하면 이런 문제가 나온다. 나머지에는 특징이 있는데 덧셈, 곱셈, 뺄셈은 이 법칙이 적용이 되고 나눗셈은 안된다. 1. 합을 나눈 것은 각자의 나머지의 합의 나머지를 구하는 것과 같다 2. 곱을 나눈 것은 각자의 나머지를 곱해서 나머지를 구하는 것과 같다. 3. 뺄셈을 나눈 것은 각자의 나머지를 뺀 것의 나머지를 구하는 것과 같다. **다만 뺄셈은 음수가 나올 수 있기 때문에 M을 한 번 더해준다. 마치 분배법칙을 이용한 것과 같다. 하지만 조금 다르다. 분..

사실 스택을 이용하는 문제는 수없이 많다. 글 하나로 정리를 할 수 없다는 것은 안다. 하지만 스택이 가리키는 것은 단 하나 밖에 없고 그 개념을 조금이라도 감을 잡고자 글을 쓴다. 실전 개념 1. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 2. Push, Pop은 O(1)의 시간복잡도를 가진다. 3. Stack에 최근에 들어간 것만 뺄 수 있다. => 가장 마지막에 들어간 것만 뺄 수 있다. 확장 3. 연속된 원소를 집어넣으면 뺄 때는 역순으로 나온다. 문제를 풀면서 저 1,2,3번의 개념이 어디에 들어가나 보자 1. 단어 뒤집기 사실 어려운 문제다. https://www.acmicpc.net/problem/9093 #include using namespace std; int n; int main..

우리가 BFS나 DFS를 사용하는 것은 알아봤다. 응용이 어떻게 될 수 있으며어떤 개념을 알고 가야하는지 고찰해보자. (대부분 BFS를 요구하고 DFS는 재귀를 이용하는 문제가 많다) 우리는 그렇다면 어떤 문제가 DFS고 BFS인지 알 수 있어야 한다. 이 문제를 보자 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 1926번 C++ [CPP] 딱히 BFS인지는 모르겠으나 BFS로 해도 될 것 같은 느낌이 든다. 다음 문제를 보자 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] 최소의 칸 수를 구하란다. 즉, 탈출까지 최단거리를 구하란다. 그래서 BFS를 쓴다. 솔루션을 찾았을 때 BFS..

우선 Python 에서의 split 함수를 보자 2개의 인자를 받는다 1. delimiter, 구분자 2. 해당 문자열 알아봤다면 시작해보자 그렇다면 우리는 우선 가장 흔한 공백을 기준으로 만들어보자 막연하게 드는 생각은 공백을 만나면 공백을 만나기 전까지의 모든 문자열을 어떠한 컨테이너에 넣고 문자열을 다시 진행하면 될 것 같다. 즉, 문자열을 하나하나 조사한다는 말이다. 공백을 만나면 그때까지의 문자열을 다시 집어넣고 다시 공백이 나오지 않을 때까지 탐색한 후 다시 반복한다. 만약 문자열이 끝나면 끝나게 된다. 대충 이런 생각으로 짠다. 위에서 아이디어를 뽑아보자면 1. 문자열을 하나하나 조사할 것임 2. 공백만났을 때 하는 행동 3. 문자열의 끝에 닿았을 때 하는 행동 C++에서 알다시피 문자열은 ..

다익스트라가 가중치가 양수일 때만 최단거리를 찾는 알고리즘이라면 이 벨만-포드 알고리즘은 음수의 가중치도 계산한다고 보면 되겠다. 어렵지 않고.. 그냥 다익스트라를 정점개수-1만큼 돌린다고 생각하면 된다. **일반적으로 음수의 가중치는 나오지 않으나 간선을 돌아감에도 비용이 줄어든다는 것은 예를 들어 신호가 x만큼 증폭되는 증폭기가 있다고 했을 때 증폭기가 우리가 갈 노드의 수를 줄여준다고도 볼 수 있겠다. 알아보자 다익스트라가 양수가중치만 있을 때 사용하는 알고리즘이라면 벨만 포드 알고리즘은 음수 가중치가 존재해야만 의미있는 알고리즘이다. 알아보자 #include #include #include using namespace std; //간선을 표현할 Edge typedef struct Edge { in..

우선 이 알고리즘을 쓰기 위해서는 몇가지 조건이 필요하다. 1. 각 간선에 대한 가중치가 음수여선 안된다. -> 양수여야만 한다. 2. 단일 시작점에 대한 최단 경로이다. -> 해당 시작점에 대해서만 최단경로고 다른 vertex는 다시 돌려야 한다. 3. 프림의 MST 알고리즘과 유사한 형태다. -> 프림 알고리즘은 경계로부터의 최소 거리를 정점의 거리 값으로 설정 -> 다익스트라에서는 시작 정점으로부터 각 정점까지의 전체거리 사용 -> 다익스트라에서는 목적 정점만 파악하면 종료 아무튼 조금 다르다. 우선 기본적으로 해야 할 것들을 알아보자 1. 모든 정점에 대해서 거리 값을 무한대로 초기화한다 -> 계산하지 않았음을 의미한다. 2. 시작정점 자기자신과의 거리는 0이므로 0으로 설정한다. 3. 모든 거리..

CPU 스케줄링에서도 엄청 많이 나오는데.. 우리는 동적으로 사람이 들어오진 않으니까 starving에 대한 걱정은 말고 풀어보자. 저런 알고리즘을 적용하는 이유는 평균 대기시간을 줄이기 위해서다. 앞사람이 길수록 뒷사람이 오래기다리는 것과 같은 이치다. ??? 무슨상관이냐고..? 대기는 각각 한다. 즉, 기다리는 사람의 수만큼 한다. 일이 끝난 사람은 대기를 하지 않는다. 그렇다면...? 일을 빨리 끝내서 기다리는 사람을 줄여야 한다. 그것을 위한 알고리즘이 바로 Shortest job first algorithm 이다. 구현해보자 사실 구현할 것은.. 실제로 대기시간이 줄어들었느냐? 확인만하면 된다. 즉, 대기시간만 알아내면 끝이다...ㅎㅎ 당연히 입력으로는 작업시간이 주어져야 한다. #include..

퀵정렬도 분할 정복을 이용한 정렬로 병합정렬에서 조금 더 조건이 추가된 정렬이라고 보면 된다. 또한 병합정렬이 대량의 데이터를 대상으로 한다면 퀵정렬은 빠른 시간을 위한 정렬이다. 그렇다면 무엇이 다르냐? 피벗이 있다는 것이다. 주어진 배열을 부분 배열로 나누고 각 부분 배열을 정렬하여 합치는 것과 같다. ??? 엥 그럼 피벗은 어디다 쓰는거야??? 피벗은 주어진 부분 배열을 나누는데 쓰이고 부분 배열을 정리하는데 쓰인다. 구현해보자 #include #include //분할하는 작업 template auto partition(typename std::vector::iterator begin, typename std::vector::iterator end) { //3개의 반복자를 사용한다. //1. 피벗,..

병합 정렬이란 잘 알려진 정렬 알고리즘 중 하나다. 분할 정복이라는 간단한 아이디어이다. 많은 원소를 가지고 있더라도 작은 크기로 쪼개서 각각을 정렬한 다음 정렬된 부분집합을 정렬상태를 유지하면서 합치는 방식이다. 코드로 구현해보자 #include #include //벡터를 임의의 원소가 들어가도 괜찮게 템플릿 선언후 //벡터 2개의 참조변수를 이용한다. template std::vector merge(std::vector &arr1, std::vector& arr2) { std::vector merged; auto iter1 = arr1.begin(); auto iter2 = arr2.begin(); //차례대로 원소를 비교해나간다. -> 2개의 벡터를 받아서 가장 첫번째 원소부터 비교한다. //결국 ..