차가운오미자님의 유리병

유클리드 호제법 2개의 정수의 최대 공약수와 최대 공배수를 구하는 방법이다. 두 개의 정수 A, B가 있을 때 (A>=B) A%B, 즉 A를 B로 나눴을 때 나머지 R가 있을 때, A와 B의 최대공약수가 B와 R의 최대공약수와 같다는 성질을 이용하는 것이다. 그래서 A와 B의 최대공약수를 구하기 위해서는 A%B, B%R을 반복하면 된다. int main(void) { int n1, n2; int max, min; int tmp; scanf("%d %d", &n1, &n2); if (n1 > n2) { max = n1; min = n2; } else { max = n2; min = n1; } while (min) { int tmp = max % min; max = min; min = tmp; } print..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀의 기본 of 기본인 하노이 탑 옮기기이다. #include #include using namespace std; int cnt; vector answer; void Hanoi(int from, int by, int to, int num){ if(num>0){ Hanoi(from, to, by, num-1); answer.push_back(make_pair(from, to)); c..

단축키 빌드할 때 자동으로 저장하지 않음. 저장 전 파일을 기반으로 빌드해버림. 그래서 저장을 하고 빌드하는 것이 필수이다. Ctrl + Shift+ S: 모든 파일 저장 Ctrl + Shift + W: 열러 있는 모든 파일 닫기 Ctrl + B : 빌드 all

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 저번에 풀었던 파싱 문제와 비슷한데, ()외에 []의 유효성도 검토해야 한다. 이건 기본적인 논리가 같아서 어렵지 않는데, 입력을 받는 과정이 오히려 신경쓰였다. 아래와 같은 입력 조건 중에 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 여러줄에 걸쳐서..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문자열 파싱 비슷한 문제이다. 스택을 사용해서 괄호를 넣었다가 빼는 동작으로 최종적으로 스택이 비어있지 않으면, 괄호가 짝이 안맞는다는 말이므로 NO를 출력하면 된다. 다음과 같은 규칙으로 구현했다. 1. '(' 이면 스택에 넣는다. 2. ')' 이면 스택에 '(' 이 있는지 확인한다. a. 스택이 비었다. -> push()한다. b. 스택 탑이 ')' 이다 -> p..

동적 계획법이란? 메모리를 사용해 수행시간의 효율성 향상시키는 방식 이미 계산된 결과를 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 한다. Top-Down 방식과 Bottom-Up 방식(전형적) 두 가지가 있다. - Dynamic Allocation에서 dynamic(실행 도중에 해결하는 방식)과 무관한 명칭이다. 조건 Optimal Substructure (최적 부분 구조) Overlapping Subproblem (중복되는 부분 문제) 예시 Fibonacci 수열 a₁ = 1, a₂ = 1 이고, a_n = a_n-1 + a_n-2 이라는 점화식으로 표현할 수 있다. 재귀함수를 사용해서 풀 수 있는 문제인데, 여기서 이 수열의 계산값들을 배열이나 리스트로 저장해두면 더 빠르게 해결 가능하다. ..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 www.acmicpc.net #include #include using namespace std; int main(void){ string s; getline(cin, s); int count = 0; for(int i = 0; i

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net alphabets[]라는 배열을 만들어서, 여기 a는 0, b는 1에 각 문자가 반복되는 횟수를 저장했다. 관건은 답을 프린트하는건데, alpahbet배열을 traverse 하며, biggest라는 int 값을 통해 가장 큰 횟수를 저장하고, 그 횟수에 해당하는 알파벳과 반복 횟수를 pair로 만들어서 벡터에 넣었다가, 만약 그거보다 큰 횟수의 알파벳이 있으면 answer 벡터를 비워버리고 새로운 알파벳 pair를 저장했다. 이렇..

https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net #include #include #include using namespace std; int main(void) { int t, r; string s; vector answer; cin >> t; for (int i = 0; i > r >> s; for (int j = 0; j < s.length(); j++) { for (i..