14503번: 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 어제 오늘 이틀동안 붙잡고 있었던 문제다. 유사한 문제들이 많기 때문에 깊이 우선 탐색(DFS)를 이용하여 구현하였는데 답이 1~2개씩 차이가 나는 것 때문에 오늘까지 붙잡게 되었다. 이유는 문제를 잘못 이해한 것이었는데, 문제에서 후진을 못할 경우 멈추는 조건이 모든 방향을 탐색하여도 후진할 경로가 없을 때인줄 잘못 이해한 것이 문제였다. [문제 접근] 일단 DFS인지 BFS인지 부터 분류해보..
1010번: 다리놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [문제 접근] 이전에 놓은 다리가 다음에 놓을 다리의 경우의 수를 결정한다. 이전의 계산해둔 값을 이후에 써야하기 때문에 다이나믹 프로그래밍(DP)으로 접근해야 한다. 이중 배열인 DP[N][M]는 서쪽의 N번째 사이트를 동쪽의 M번째 사이트까지 연결할 때 가능한 경우의 수다. 즉 DP[1][1] = 1; DP[1][2] = 2; ... ; DP[1][M] = M;이다. N=2 이후에 다리를 놓을..
썸네일 DP_2748 문제 출처: https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net 우선 Fn = Fn-1 + Fn-2 (n>=2)의 식을 이용하여 재귀함수로 작성하면 아래와 같다. #include using namespace std; int Fib(int N) { if (N < 2) { if (N == 1) { return 1; } else { return 0; } } return Fib(N - 1) + Fib(N - 2);..
썸네일 while_10951 문제 출처: https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 간단한 문제지만, EOF의 개념을 모를 경우 틀리는 문제이기 때문에 백준 풀이모음에 작성하게 되었다. EOF란 파일의 끝을 의미하며, EOF를 만나면 특정 값을 리턴하도록 되어있다. 즉, 테스트 케이스가 없는 10951번 문제같은 경우에 파일의 끝에 도달했을 경우에 매크로로 정해져있는 값이 리턴되며 루프를 빠져나오게 되는 것이다. #include using namespace std; int main() { //10951번 int A, B; while (cin >> A >> B) { cout A..
썸네일 _1002 문제 출처: https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 케이스는 총 5가지로, 그 중 3개를 그리면 아래와 같다. [1]번 터렛의 류재명까지의 거리는 ro이고, 문제에서 주어진 r1과 같다. 이 범위를 그리면 원이 나온다. 원을 사용하는 이유는, 저 원이 [1]번 터렛의 정보로만 알 수 있는 류재명이 있을 경우의 수를 모아둔 집합이기 때문이다. 같은 논리로 [2]번 터렛에서의 거리는 rt이고, 문제에서 주어진 r2와 같다. 두 집합을 교집합 시키면 3가지 경우가 나오는데, 수학 관련 과목에서..
썸네일 _10871 문제 출처: https://www.acmicpc.net/problem/10871 10871번: X보다 작은 수 첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net 매우 간단한 기초 문제다. 루프(loop)를 돌려 N개 만큼 입력받으면서, 동시에 X보다 작은 수면 출력시켜주면 된다. 따로 배열을 선언할 필요가 없다. (입력과 출력 스트림을 각기 검사하므로) #include using namespace std; int main() { int N, X, V; cin >> N >> X; for (int i = 0; i < N; i++)..
썸네일 Brute Force_1436 문제 출처: https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 666이 들어간 string을 찾는 '탐색' 알고리즘이다. 무작정 시도해보는 브루트포스(Brute Force) 방식으로 풀 수 있는 문제다. 자세히 알고리즘을 설명해보면, 숫자를 문자열로 하나씩 변환해가며 '666'이 들어갔다면 순서 번호를 하나씩 증가시키고, 입력받은 N과 순서 번호가 같아졌을 경우 해당 숫자를 return 하는 방식으로 구현할 수 있다. 주의할 것은, 666, 1..
썸네일 _2775 문제출처: https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1
썸네일 recursive_11729 문제 출처: https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net void hanoi(int N, int from, int by, int to){ if(N==1){ printf("%d %d", from, to); } else { hanoi(N-1, from, by, to); printf("%d %d", from, to); hanoi(N-1, to, from, by); } } C++로 구현한 하노이 탑 알고리즘이다. 간단히 말로 설명하면 ..
라이브러리 브랜드 그룹 | CDOING

티스토리툴바