본문 바로가기

전체 글133

[기초] 정렬(sort) 알고리즘 정렬 정렬은 어떤 자료를 순서대로 배열하는 것을 의미합니다. 많은 알고리즘 문제에서 정렬을 사용하여 문제를 해결합니다. 정렬은 직접 구현하기 보다는 STL에 있는 sort를 사용하는 것이 좋습니다. (STL sort는 intro sort를 사용한다고 합니다. 매우 빠름) 참고 링크 https://www.acmicpc.net/board/view/16770 글 읽기 - stl의 sort 로는 시간초과가뜨는데 제가 틀린건가요? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net Introsort - Wikipedia Hybrid sorting algorithm Introsort or introspective sort is a hybrid sorting algorithm that provides .. 2022. 8. 8.
[기초] 알고리즘 수학2 4. 진법 변환 (Base Conversion) 4-1. 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될때 까지 나머지를 계속 구하면 됩니다. 예를 들어 11을 3진법으로 바꾸는 방법은 11/3 = 3 나머지는2 3/3 = 1 나머지는0 1/3 = 0 나머지는1 그래서 위로 보면 따라서 11은 3진법으로 102 입니다. 백준 진법 변환문제 10진법 수 N을 B진법으로 바꿔 출력하는 문제입니다. https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc... 2022. 8. 2.
[기초] 알고리즘 수학1 알고리즘을 풀 때 필요한 수학 내용을 다루고자 합니다. 1. 나머지 연산 (Modular Arthmetic) 첫번째로 자주 사용하는 내용입니다. (A+B) % C = ( (A%C) + (B%C) ) % C A+B에서 나머지 연산으로 위와 같은 식이 성립합니다. 증명은 아래 링크 참고 모듈러 연산의 성질과 증명 모듈러 연산의 성질과 증명 위와 같이 모듈러 연산은 나머지를 구하는 연산자이며 다음의 분배법칙이 모두 성립한다. 왜 이런지 궁금해서 계속 찾아보다가 간신히 찾은게 칸 아카데미에서 증명 sexycoder.tistory.com 다이나믹 프로그래밍 문제 중에 경우의 수를 구하는 문제일 때 경우의 수가 너무 큰 경우 또는 정수 범위를 넘어가는 경우 이 연산을 이용하여 풀이가 가능합니다. - 컴퓨터의 정수는.. 2022. 8. 1.
C++ 백준 BOJ 10870 피보나치 수 5 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하는 문제입니다. 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; int fibo(int num) { int result = num; if (result == 0) { return 0; } else if (result == 1) { return 1; } else { return fibo(result - 1) + fibo(result - 2); } } int .. 2022. 7. 27.
[기초] 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 동적 계획법이라고도 합니다. 동적 계획법 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아래 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있습니다. 1. Overlapping Subproblem : 겹치는 부분 문제 2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem 겹치는 작은 부분 문제로 나눠서 푸는 것이 핵심입니다. 문제 작은 문제 - 작은 문제 (두 작은 문제가 겹쳐야 됨) 먼저 피보나치 수를 예시로 들어 알아보면, - 피보나치 수 - F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2.. 2022. 7. 27.
[기초] 자료구조 / 큐(queue)와 덱(deque), 문자열 큐(queue) 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 합니다. - push : 큐에 자료를 넣는 연산 - pop : 큐에서 자료를 빼는 연산 - front : 큐의 가장 앞에 있는 자료를 보는 연산 - back : 큐의 가장 뒤에 있는 자료를 보는 연산 - empty : 큐가 비어있는지 아닌지를 알아보는 연산 - size : 큐에 저장되어있는 자료의 개수를 알아보는 연산 그림에서 빨간색 1번이 front로 가장 앞에 있는 자료이고 빨간색 3번이 back으로 가장 뒤에 있는 자료입니다. 큐도 스택과 같이 이미 구현된 라이브러리를 사용할 수있습니다. C++의 경우 STL의 queue .. 2022. 7. 26.
[기초] 자료구조 / 스택(stack) 스택(stack) 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO) 라고도 합니다. - push : 스택에 자료를 넣는 연산 - pop : 스택에서 자료를 빼는 연산 - top : 스택의 가장 위에 있는 자료를 보는 연산 - empty : 스택이 비어있는지 아닌지를 알아보는 연산 - size : 스택에 저장되어있는 자료의 개수를 알아보는 연산 그림에서 top은 6이고 4가 push 되면 top은 4가 됩니다. 빨간색 숫자가 자료가 들어온 순서를 나타냅니다. 스택은 이미 구현된 라이브러리를 사용할 수있습니다. C++의 경우 STL의 stack JAVA의 경우 java.util.Stack 직접 구현할 경우 배열을 이용해.. 2022. 7. 26.
C++ 백준 BOJ 9012 괄호 입력받은 문자열이 바르게 구성된 괄호 문자열(VPS)인지 판단하는 문제입니다. 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net #include #include using namespace std; void checkVPS(string p){ stack checkP; for(int i = 0; i < p.size(); i++){ if(p[i]=='('){ checkP.push('('); } else{ if(checkP.empty()){ checkP.push(')'); } else .. 2022. 7. 25.
[기초] 알고리즘과 입출력 (+시간 복잡도) 알고리즘이란? 어떠한 문제를 해결하기 위한 여러 동작들의 모임, 절차입니다. 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 ko.wikipedia.org '시간 복잡도' 시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸릴지 예상할 수 있다. 표기법으로 대문자 O를 사용한다. 영어로는 Big O Notation 입력의 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법 최악의 경우에 시간이 얼마나 걸릴지 나타내야한다. 만약 1부터 N까지의 합을 계산하면, 시간 복잡도: O(N) int sum = 0; for.. 2022. 7. 25.

티스토리툴바