coding tasty house

LCS 문제설명 주어진 두 문자열에서 최장 부분 수열을 구해 출력 시킨다. 알고리즘 값을 각각 입력받고 입력 받은 문자열에 편의를 위해 0을 추가해서 붙인다. 각 첫행 첫열은 0으로 초기화한다. 비교하는 기준 문자열에서 같으면 해당 칸의 대각선 값 +1을 표에 넣는다. 비교하는 기준 문자열에서 다르면 왼쪽, 또는 위의 값 중에 더 큰 값을 찾아서 넣는다. 해당 테이블이 가장 오른쪽 아래 값이 정답이 될 수 있다. #include #include #include #include #define MAX 1001 using namespace std; int lcs[MAX][MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string A,B; cin >..

곱셈 문제설명 주어진 수 A,B,C가 입력되면 A를 B번 곱한 수를 C로 나눈 나머지를 출력하자 알고리즘 값을 각각 입력받고 POW함수에 인자를 전달해준다. B(제곱 수)가 0이면 1을 반환하고 1이면 A%C를 준다. 위의 두 경우가 아니면 B를 2로 나누고 그 함수의 나머지를 구한다. 위의 값을 짝수일때는 제곱해서 나머지를 구한다. 홀수인 경우 다시 A를 곱해서 제곱수를 짝수로 만들어서 나머지를 구해준다. #include #include //modular 연산 XYmodM=(XmodM*YmodM)mod M using namespace std; long long A, B, C; long long int POW(long long A, long long B, long long C) { if (B == 0) ..

인구 이동 문제설명 각 도시간의 인구이동이 일어나는 데 필요한 일자를 구하자 알고리즘 값을 각각 graph 이차원 배열에 입력 받는다. 무한루프 안에서 여러번 인구이동을 확인하기 위해서 visited 를 초기화하고, 방문 여부 체크를 초기화한다. 방문한적 없는 도시를 만나면 그 도시의 인구수, 현재 연합된 도시의 수, 그리고 도시의 좌표를 저장한다. bfs함수를 실행한다. bfs함수에서는 4방향 다 방문해보고 gap이 L과 R사이에 있는 경우 방문하고 인구수를 구하고 방문 표시를 한다. bfs함수를 돌고 난 뒤 총 나라가 2개이상이면 연합이 결성되었다는 의미로 인구 재분배를 해준다. 연합이 결성되면 결과를 1 증가시키기 위해서 checker를 true해준다. 각 점을 다 돌고 나오면 checker여부를 ..

최소비용 구하기 문제설명 각 도시들의 정보를 입력받고, 출발도시에서 도착도시까지 가는데 드는 최소 비용을 구하자. 알고리즘 값을 각각 입력 받는다. pair형태의 백터 배열에 시작점, 도착점 ,cost를 입력받는다. dist 배열을 INF로 초기화 시켜준다. priority_queue를 사용하여 현재 비용, 시작 도시를 넣어준다. 우선순위 큐에서 비용을 끄내는데 부호를 음수로 설정하고, 현재 도시를 꺼낸뒤 큐에서 지운다. 현재 거리비용이 만약 지금 꺼낸 거리의 비용보다 작으면 넘어간다. 반복문으로 이웃한 부분의 비용과 값을 확인한다. 확인한 값이 최소경로인 경우 거리를 갱신해주고 다시 큐에 넣는다. #include #include #include #include #include #define MAX 10..

나무 자르기 문제설명 나무의 수, 최소 필요한 나무의 길이, 그리고 각 나무의 길이를 입력 받는다. 그리고 톱의 최대 높이를 설정해서 필요한 나무의 길이를 구할 수 있게 되는 값을 구하자. 알고리즘 값을 각각 입력 받는다. 이때 long long 타입으로 입력 받는다. 나무의 각 길이를 입력 받은 벡터를 정렬하고, 이분 탐색을 하기위해 0부터 나무의 최대 값을 매개변수로 넣는다. 이분 탐색 과정에서 나무를 잘랐을 때 얻을 수 있는 양을 구한다. 얻을 수 있는 양이 최소 조건에 도달 할 수 있는지 확인하고 도달 할 수 있는 경우 max함수로 그 톱의 길이를 갱신한다. 도달할 수 없는 경우는 end-1을 해서 범위를 좁혀준다. 위의 과정을 반복해서 result 변수에 담긴 값을 출력한다. #include #..

분수 합 문제설명 두 수를 입력 받는 데 각각 분자, 분모 순으로 입력 받는다. 두 분수의 합을 구해서 기약분수 형태로 구해서 결과 값의 분자와 분모를 출력한다. 알고리즘 두 수의 분자와 분모를 각각 입력 받는다. 통분을 위해서 각각의 분자에 다른 수의 분모 값을 곱하고 두 값을 더한다. 분모는 두 수의 분모를 곱한 값이다. 기약분수 형태로 나타내기 위해서 결과값의 분모와 분자 중에 어떤 값이 더 작은지 판단한다. 더 작은 값을 기준으로 1씩 줄여가면서 분자 분모의 나머지가 모두 0이 되는 값을 찾아 그 수로 나눈다. 결과 값을 출력한다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL..

분수 합 문제설명 카드의 동작을 수행하고 난 결과를 출력시킨다. 알고리즘 몇 장의 카드가 있는지 입력 받는다. queue에 값을 채워 넣는다. 문제에서 주어진 대로 동작을 하기위해 반복문 내에서 카드가 1장 남을 때 까지 반복한다. 맨 앞의 값을 지우고 그 다음 값을 꺼내서 맨 뒤에 넣는다. 가장 마지막에 1개 남은 카드의 값을 출력시킨다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); int N; cin >> N; queue q; for (int i = 0; i < N; i++)//값 입력 q.push(i + 1); while (q.size() != 1)//값을 ..

양 문제설명 행과 열을 입력 받은 다음, #은 울타리 .은 아무것도 없음, o는 양 그리고 v는 늑대를 의미한다. 이때 울타리 공간 안에 양의 수가 늑대의 수보다 많으면 양은 늑대를 밀어 낼 수 있다. 다른 말로는 늑대가 양의 수보다 많거나 같으면 늑대가 양을 처리한다. 따라서 다음 날의 존재하는 늑대와 양의 수를 출력시킨다. 알고리즘 문자열과 행과 열의 값을 입력 받는다. 각 값을 조회하는데, 그 칸을 방문 하지않았고, 울타리가 아닌 경우 DFS 함수로 조회한다. DFS 함수에서는 방문 표시를 하고 늑대, 양의 수를 세며, 울타리는 종료시킨다. 늑대나 양을 센 경우에는 그 구역 내의 다른 칸도 확인하기 위해서 상하좌우로 이동하며 다른 양이나 늑대의 수를 센다. DFS 함수에서 빠져나와서 해당 구역에 늑..

카드 정렬하기 문제설명 총 카드 묶음의 수를 입력 받은 뒤, 각 카드의 수를 입력 받는다. 이때 카드를 확인하는 수를 A+B라고 한다. 가장 적은 수의 카드를 확인하는 경우의 수를 출력시킨다. 알고리즘 카드 묶음의 수와 각 카드 묶음 당 카드의 수를 입력 받는다. priority_queue를 사용하여 수가 입력되면 자동으로 오름차순으로 정렬되도록 한다. 큐에서 가장 앞에있는 (가장 작은 두 값) 두 값을 꺼내서 ans 변수에 더한 값을 넣는다. 다시 더한 값을 queue 에 넣고, 원래의 두 값은 지운다. queue에 남은 수가 1개가 되면 반복을 멈추고 나와서 ans의 값을 출력한다. #include #include #include using namespace std; int main(void) { i..

괄호의 값 문제설명 첫 줄에 식을 입력 받는다. 이때 식은 (),[]로 이루어져 있다. ()는 2이고 []는 3이다. 주어진 식의 값을 알맞게 계산하여 값을 출력한다. 알고리즘 문자열을 입력받는다. 문자열을 각각 read 하고, 여는 괄호일 때는 계산의 편의를 위해서 괄호 그대로 넣지 않고 &#39;(&#39;일 때는 -1을 넣고 &#39;[&#39;일때는 -3을 넣는다 짝이 맞지 않는 경우 바로 0을 리턴하여 종료 시킨다. 닫는 괄호가 들어온 경우 stack의 맨 위값이 짝이 맞는지 확인하고 맞으면 (일 때 2를 넣고 [이면 3을 넣는다. 맨 위가 숫자이면 여는 괄호를 만날때 까지 전부 더한다. 전부 더한 뒤 다음 가장 위의 값이 짝이 맞으면 2나 3을 곱하고 그 값을 stack을 넣는다. 2-6의 과..