언제쯔음

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 이 글을 읽는다면 문제는 이미 다 알고 있다고 생각합니다. 구해야하는 정답은 첫 번째 줄에서 뽑은 수와 두 번째에서 뽑은 수가 같은 집합의 최대 크기이다. 두번째 줄에서 주어진 수에서 인덱스번호가 없는 2와 7은 첫번째 줄에서 선택할 필요가 없다. -> 왜냐하면 2와 7을 뽑아봤자 2번째 줄에 2와 7이 없기 때문에 같은 수를 뽑을 수가 없기 때문이다. 일단 이해하기 쉽도록 그래프를 ..

일단 문제를 확인해보면 1부터 3까지 총 3 가지 수로 주어진 N의 더하기 경우의 수를 구하는 문제임을 알 수 있다. 조건이 있는데 연속된 수를 사용하면 안 된다란 조건이 있다. => 곧 힌트란 의미. 먼저 이를 어떻게 구하는 지 고민을 해보면 완전탐색을 생각할 수 있다. 각 경우의 수가 총 2개이다. 1 깊이에서 3개, 2 깊이에서 2개씩 총 6개, 3 깊이에서도 2개씩 총 6*2 12개이다. 4 깊이에서는 24개 결국 깊이에서의 경우의 수가 3, 6, 12, 24 순으로 늘어난다. 무슨 수열인지는 모르겠지만 자신의 앞의 수 * 2씩 늘어난다. 딱 봐도 엄청 느리다. 그래도 수식을 구해야하니까 수열에 공통적으로 3이 곱해져 있으니, 앞으로 빼보니 3*2^n 이다. 문제에서는 n이 100,000보다 작거..

이집트 알고리즘은 인류 최초로 기록된 알고리즘 중 하나다. 빠른 곱셈 알고리즘, 빠른 나눗셈 알고리즘이다. 먼저 알아둬야하는 상식은 고대 문명의 알고리즘이기 때문에 자릿수 개념과 0을 표현하는 방법이 없었다. 자릿수 개념이 없었다는 말이 나중에 나올 이진수와 비슷하다고 생각이 든다. 먼저 곱셈은 1) 1로 곱하기, 2) 1보다 큰 수로 곱하기, 2가지로 정의하여 나눌 수 있다. 1) 1a = a 2) (n+1)a = na+a 먼저 우리가 알고 있는 일반 상식? "곱셈은 덧셈을 여러번한 것이다"를 구현해보자. => 덧셈을 n-1번 반복해보는 알고리즘(n-1번 반복하니 시간 복잡도는 O(n)라고 알 수 있다.) 우리는 덧셈을 배울 때 결합 법칙을 배웠기 때문에 덧셈의 횟수를 줄일 수 있다. 중학교 때 배우는..

이전 글에서 스택의 고정 관념을 파쇄를 위해서 글을 쓴다고 했다. 이전글 먼저 백준의 괄호란 문제를 분석해보자! 9012 괄호 문제 괄호 문자열 Parenthesis String은 (, )로만 구성되어있는 문자열이다. 괄호의 모양이 올바르게 구성된 괄호문자열을 VPS라고 부르고, ( )은 기본 VPS이다.. 예를 들어 (())))() ((())), (() 은 VPS가 아니다. 선입후출! 먼저 넣고 빼면서 생각하는 방법으로 코딩을 한다면 어떻게 될까? 일단 위 문자열 사진처럼 읽으면서, 스택에 다 넣어두고 뒤에서부터 빼면서 쓴다면 내가 데이터를 읽는 흐름이 보라색 선과 같다. 이렇게 넣은 상태에서 넣은 값을 하나씩 빼면서 생각한다면 어떻게 생각하게 될까? 어떻게 코드를 짜야할지 감이 잡히지 않는다. 왜??..

"알고리즘 공부를 하면서 자료구조에 대해서 공부를 해야한다"란 말을 많이 듣는다. 자료구조 라이브러리는 이미 구현되어있는데, 실제 구현 방법에 대해 알고 있는 것이 좋다고 한다. 이유로는 어떻게 돌아가는지를 알기 때문에 실제 구현 시에 도움이 된다고 하는데, 조금 기분이 이상하다. 우리는 이미 배열이란 자료구조를 애용한다. "배열 없이 못 살아"란 말을 할 정도로 배열 자료구조를 많이 사용한다. 조금 코딩하다보면 배열을 찾게 된다. 이처럼 다른 자료구조들도 친근해야하는 것이 중요한 게 아닐까? 친근하다의 기준이 무엇일까? 많이 이용해봤기 때문에 그 자료구조를 적재적소로 이용할 수 있다는 뜻일 것이다. -> 적재적소로 이용하기 위해선 무엇이 필요할까? 어떻게 구현되어있는지 알고 있어야 가능하다. 스택의 개..

소수 Prime Number' 처음 소수를 판별하여 출력하라! 라고 한다면 소수의 정의를 따라간다. 소수는 1과 자기 자신을 약수로 갖는 값으로 1과 자기 자신외의 약수를 가지지 않는 1보다 큰 수라고 하는데 한번 꼬아놓은 말이라 개인적으로 싫어한다. 그냥 1보다 크고, 약수로 1과 자기 자신을 갖는 값이라고 직설적인 말을 쓰면 좋지 않을까? 하여튼 소수를 구하기 위해서는 자기 자신보다 작은 값들로 나누어서 나누어지면 안된다. = 나누어진다는 것은 배수라는 의미이기 때문이다. int number = 4; bool isPrime = true; for(int i=number-1; i>1; i++){ if(number%i==0){ isPrime = false; break; } } 내가 가진 수를 for문으로 ..

자료구조를 배우다보면 배우는 하노이의 탑 여전히 그때나 지금이나 직접 생각해서 짜려면 생각보다 곤란하다. 하노이의 탑은 재귀를 사용했지만 재귀를 사용할줄 아는 사람이 직접 구현하는 것보다 이미 구현되어있는 구현 순서를 쉽게 생각해내는 것이 더 빠르고 정확하다. 내가 원숭이라는 증명인걸까? 하노이의 탑은 A, B, C 의 봉 3개에서 A에서 C로 모든 원반을 옮기는 것을 목표로 한다. 각 규칙은 아래와 같다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이미 이 글까지 보러왔다면 다 알고 있는 내용이라고 생각한다.(문제에 적혀있으니까..) 하노이의 탑을 어떻게 구현하느냐 아니다. 어떻게 진행되는지 생각해보자. 원반이 총 3개인 경우로..

#include using namespace std; int T; bool check; int func(long long x, y, int k){ if(x == y-1){ return 1; } else if( x > y-1){ return 0; } int count = func(x+k+1, y, k+1); count += func(x+k, y, k ); return count; } int main(){ ios::sync_with_stdio(0); cin.tie(0); long long x,y; cin >> T; while(T--){ cin >> x >> y; check = false; if( y-x == 1) cout