코딩 공부하는 코딩류

DFS 문제인데... 문제 설명이 좀 더 추가되었으면 좋겠는 문제(제발 쿨병 자제 좀...) 문제의 조건 1. 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 2. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 3. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. => 여기가 정말 설명이 애매한 곳이라고 생각하는데, 차라리 프로그래..

피보나치 함수에서 0과 1이 출력되는 횟수를 구하는 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제의 조건 다음은 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fib..

강산이가 캠핑장에서 최대로 머무를 수 있는 일수를 구하는 문제 https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제의 조건 1. 강산이가 간 캠핑장은 연속된 P일 중에 L일만 머무를 수 있다. 20일 중에 10일만 머무를 수 있거나 8일 중에 5일만 머무를 수 있거나... 2. 강산이는 이제 막 V일짜리 휴가를 시작했다. 28일짜리 휴가를 시작했거나 15일짜리 휴가를 시작했거나... 3. 여러 테스트 케이스가 5(L) 8(P) 20(V) ..

N개의 숫자 묶음이 주어질 때 숫자 묶음들을 비교하려면 최소 몇 번만 비교하면 되는지 구하는 문제 문제의 조건 1. 정렬된 두 숫자 묶음이 있다. 두 묶음을 각각 A, B라 하면 두 묶음을 비교하는데 필요한 횟수는 A+B번이다. 2. 10장, 20장, 40장 처럼 2개보다 많은 숫자 묶음이 있을 때 2개씩 골라서 비교를 하는데 묶음들을 고르는 순서에 따라서 횟수가 달라진다. 10장과 20장을 먼저 합친 뒤(10+20=30), 남은 40장을 합치는 경우의 수를 더했을 때 (10+20)+(30+40)=100 총 100번의 비교가 필요하다. 하지만 10장과 40장을 합친 뒤(10+40=50), 남은 20장을 합치는 경우를 더하면 (10+40)+(50+20)=120 총 120번의 비교가 필요해서 100번보다는 ..

정수가 주어질 때 주어진 정수를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 문제 문제의 조건 1. 합을 나타낼 때엔 1개 이상의 수를 사용해야 한다. 정수 4를 1, 2, 3의 합으로 나타낸다면 다음과 같은 방법들로 나타낼 수 있다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 2. 주어지는 정수는 양수이며 11보다 작다. 즉 1 ~ 10 사이 숫자만 나온다. 3. 첫째줄에 테스트 케이스의 갯수 T가 주어지며 다음 줄부터 T 갯수만큼 한 줄마다 정수가 주어진다. 풀이 과정 DP를 연습하려고 푼 문제인데 아직 DP를 잘 못 해서 문제를 봤을 땐 당연히 풀이가 떠오르지 않았습니다. 그래서 또 구글링... 후 알게 된 이 문제의 풀이법 1-1. 정수 1을 만들 수 있는 ..

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제 문제의 조건 1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데 같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 2번의 경우에서 안전 영역의 갯수는 5개이다. 4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 이 때 안전 영역의 갯수는 4개이다. 이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 5...

알고리즘 문제 풀다가 급 궁금해져서 찾아본 find와 find_if의 차이점 1. find, find_if 둘 다 algorithm 헤더에 정의되어 vector 안에 특정 값이 존재하는지 찾아주는 함수입니다. 하지만 find는 찾고자 하는 값의 타입에 operator== 가 정의되어 있어야 사용가능하고 그렇지 않다면 find_if에 비교식을 만들어 넣어야 한다는 점이 다르다고 볼 수 있습니다. 이렇게만 적으면 무슨 소리인가 싶으실 테니 각 함수의 정의를 보겠습니다. find template InputIterator find(InputIterator first, InputIterator last, const T& val); 맨 마지막 val 인자의 타입 T에 operator== 가 정의되어 있어야 사용 가..

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 ..