엥아오

이번 글에서는 최단 경로 문제집 안에 있는 바이러스라는 문제를 해결해보도록 하겠습니다. 알고리즘 설계는 다음과 같이 하였습니다. 함수를 재귀적으로 호출하여 전파되어 있는 컴퓨터의 수를 찾는 방식입니다. 코드는 다음과 같습니다 #include #include bool a[1000][1000]; //컴퓨터 정보 배열 bool visited[1000]; //방문 정보 배열 int cnt = 0; void f(int start, int comcnt) { //함수 visited[start] = true; //방문 정보 확인 cnt++; //카운트 증가 for (int i = 1; i

파스칼 삼각형을 출력하는 문제입니다. 이 문제도 왠지 재귀함수를 이용하여 풀면 좋을 것 같습니다. 다음과 같이 반복문을 활용하여 여러 숫자를 출력할 것인데요. 삼각형의 가장자리? 부분은 모두 1이기 때문에 i=1 or i=j 조건을 사용하여 1을 출력하여 줍니다. 그리고 배열을 선언하여 각 부분의 수들을 배열에 저장하여 아래로 내려갔을때 위의 수 두개를 합한것을 계산할 수 있도록 합니다. 코드는 다음과 같습니다. #include int main(){ long long arr[100][100]; //배열 선언 int n; scanf("%d",&n); //삼각형 층 입력 for(int i=1;i

n번째에 해당하는 피보나치 수를 구하는 문제입니다. 피보나치 수열의 개념을 알고리즘으로 표현하여 코드를 구현하면 될 것 같네요. 재귀함수를 이용하였습니다. #include int f(int n){ if(n

이전 게시글과 비슷한 느낌의 문제를 하나 풀어보겠습니다. 계단을 오르는 경우의 수를 계산하는 문제인데요. 1칸, 2칸, 3칸씩 오를 수 있지만 3칸을 오른뒤에 두번은 1칸 또는 2칸 밖에 오르지 못하는 조건이 붙어있네요. 이번 문제도 재귀함수를 이용하여 풀면 좋을 것 같다고 생각하였습니다. 우선 올라가야할 계단의 수를 입력 받고 올라간 계단의 수와 3칸 올라가는 것에 대한 조건을 판별해줄 변수를 인자로 갖는 함수를 만들어 줍니다. 3칸씩 올라가는 경우의 수를 우선적으로 세줍니다. 그러나 3칸을 갈때에는 조건이 있으므로 m인자에 3이라는 값을 줍니다. 그럼 다음 함수 호출부터 m의 값을 1씩 줄이게 될텐데 m의 값이 0보다 클때 3칸을 가지 못하도록 하여 이 조건을 만족시킬 수 있습니다. 3칸씩 올라가고 ..

이번 글에서는 코드업 2608번 문제인 동아리 회장 선거 문제를 해결해 봅시다. 문제의 내용은 다음과 같은데요 다음과 같이 알고리즘을 설계해 보았습니다. 사람 수 n이 주어지면 배열에 우선 O부터 저장하기 시작합니다. O를 계속 저장하다 보면 사람 수 만큼 O가 배열에 저장되었을 것입니다. 그러면 그것이 하나의 경우의 수가 완성된 것이고 이제부터는 O의 갯수를 하나씩 줄여가며 그 자리에 X를 추가해주는 것입니다. 또 그다음은 O를 저장하고 다음은 O를 제거하고 X를 추가하고... 이러한 작업을 반복하다 보면 모든 경우의 수가 나오게 될것입니다. 이러한 반복적인 작업은 재귀적으로 표현할 수 있을 것 같아 재귀함수로 표현해 보았습니다. #include char arr[7]; //문자열 저장 배열 void f..

이번에는 Up 2라는 문제인데요. 이 문제는 영화 '업'과 관련이 있어 보여서 풀게 되었습니다. 영화 '업'을 제가 되게 재미있게 본 기억이 있어서요 ㅎㅎ;; 문제 설명 입니다. 이차원 배열을 만들어서 탐색하여 같은 숫자가 최대 몇개 연결되어 있는지를 알아봐야 할 것 같습니다. 알고리즘 모식도 입니다. k=0 부터 9까지 모든 배열을 탐색하면서 k값과 같은 [i][j]에서부터 주변을 재귀함수로 탐색하면서 이어져 있는 부분이 몇개인지를 알 수 있습니다. 그리고 이 이어져 있는 부분의 최댓값을 구하여 출력하면 문제 해결! #include int arr[20][20]; //지붕 배열 int max[10]={0}; //최댓값 저장 배열 int m,n; //지붕 크기 int pang(int i, int j, in..

이번에는 코드업 2699번 문제를 해결해 봅시다. 알고리즘에 대해 구상을 해봅시다. 배열에 탐색 시작부터 지금까지 공통적으로 몇개의 문자가 공통인지를 arr 배열에 저장하게 됩니다. 이러한 방식으로 끝까지 탐색을 마치면 arr의 끝에 총 공통 부분이 얼마인지를 보여주게 됩니다. 약간 경우의 수 구하는것과 느낌이 비슷하네요.. 그럼 코드를 봐봅시다. #include #include int arr[1001][1001]; //공통 문자열 길이 저장 배열 int max(int a,int b){ //둘중 큰값이 무엇인지 반환하는 함수 return a>b? a:b; } int main() { char s1[1001],s2[1001]; scanf("%s %s",s1,s2); //문자열 두개 입력 int len1= s..

코드업 2834번을 해결해 봅시다! 출처 문제는 위와 같은데요. 코딩을 하기에 앞서 먼저 어떤식으로 알고리즘을 설계해야할지에 대해 생각해 보겠습니다. 이 문제에서 문제를 해결할때 생각해야할 두개의 데이터는 몇번째 계단을 밟았는지와 몇번째로 밟은 계단인지 입니다. n번째 계단을 밟기 위해서는 n-1번째 계단에서 올라오거나 n-2번째 계단에서 올라오는 방법이 있는데 그 둘은 동시에 일어나는 사건이 아니기 때문에 경우의 수를 더해주어야 합니다. 저는 이 두 데이터를 하나의 배열로 묶어서 경우의 수를 계산하기로 하였습니다. 우선 출발하는 경우의 수는 당연히 1개 겠지요. 그리고 첫번째 칸에 올라가는 경우의 수는 출발칸에서 가는 경우의 수밖에 없습니다. 그래서 이 두가지 경우는 예외로 처리하고 나머지 계단에서는 ..