염딩코

풀이를 생각해낸 과정 이 문제는 예전에 알고리즘 과제와 유사하다는 느낌을 받았다. (그래서 예전 알고리즘 수업 자료도 보면서 다시 공부를 했다.) 목적지에 도달을 하면 경우의 수에 1을 더하는 방식을 생각을 했었고, 그 과정에서 지나온 경로들을 모두 처리해줘야 했었다. 지나온 경로는 상하좌우를 따지면서 내리막길인 경우에 다른 표기를 해야한다고 생각했다. 그렇게 목적지에 도달하면 해당 경우의 수를 1씩 증가시키면서 답을 구하려고 했다. 오렌지 부분에서 고민을 많이 했고, 시간이 너무 지체되어서 참고를 하면서 구현을 했다. 풀이에 대한 설명 세부적인 내용은 주석을 통해서 간단하게 설명을 했고 핵심적인 내용 위주로 설명을 하면 각각의 노드에 왔을 때, 상하좌우를 따지면서 범위를 벗어났다면 continue를 하..

이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다. DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다. DP에 대해서 간단하게 말씀드리면 DP는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다. DP는 재귀와 매우 유사합니다. 하지만, 가장 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 점입니다. DP를 사용하기 위한 조건으로는 크게 두 가지가 있습니다. 1. Overlapping Subproblems(겹치는 부분 문제) 동일한 작은 문제들이 반복하여 나타나는 경우 2. Optimal Substructure(최적 부분 구조) 부분 문..

문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다. merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

문제 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다. #include #include int recursion(const char *s, int l, int r){ if(l >= r) return 1; else if(s[l..

문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N(0 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 N!을 출력한다. 풀이 이 문제는 재귀에 대한 기본적인 내용을 담고 있다. 다만 주의할 점은 입력의 범위를 확인하고 int로 표현할 수 있는 수의 범위를 넘어가는 것을 알아야 한다.

[문제] & [결과] [해설] 이 문제는 두 수를 입력받고 그 두 수 사이에서 소수를 골라서 소수들의 합과 소수들의 최솟값을 구하는 문제이다. 아래의 코드의 메커니즘은 이렇다. 먼저 두 수를 입력받으면 두 수 사이에서 반복문을 시행한다. 이중반복문을 이용하여 i 변수를 j 변수로 나눠서 나머지가 0이라면 cnt값을 증가시켜준다. 이유는 간단하다. 소수는 나누어서 나머지가 0인 수가 자기자신 밖에 없기 때문이다. 1은 기본적으로 소수가 아니기 때문에 제외시켰다. 그래서 j도 2부터 시작하는 것이다. 2부터 시작했기 때문에 cnt가 1일 때, sum 변수에 값들을 더해준다. 그리고 이전에 초기화해놓았던 min 변수와 비교하면서 min보다 더 작은 수라면 min변수를 계속 업데이트 시켜준다. 그렇게 sum이 ..

[문제] & [결과] [해설] 이 문제는 제목에서 알 수 있듯이 어떤 특정 수의 약수를 구하는 문제이다. 문제에서 보면 약수의 특성을 알려주는데, 바로 특정한 수를 특정한 수의 약수로 나누면 나머지가 0인 것이다. 그런데, 문제는 단순히 약수가 무엇인지 묻는 것이 아니라 K번째로 작은 수를 출력하도록 원한다. K번째로 작은 수를 출력하기 위해서는 데이터가 정렬되어있거나 약수를 작은 순서대로 저장해놓는 방법이있다. 필자는 두 번째 방법을 이용했다. 그래서 vector을 이용해 반복문 i=1부터 비교해가면서 vector에 값을 저장했다. if(n%i==0)을 보면 이 조건을 만족할 때, vector에 저장하는 것을 알 수 있다. cnt는 출력의 세부 조건에 특정한 수의 약수의 개수가 K보다 작을 때 0을 출..

[문제] & [결과] [해결] 이 문제는 벡터를 이용해서 홀수를 만족했을 때, 벡터에 넣어준다. 그리고 홀수가 없을 경우를 대비해, cnt라는 변수를 만들어줘 cnt가 0이면 -1을 출력한다. algorithm 라이브러리에 있는 min함수를 이용해 최솟값을 구한다.

[문제] & [결과] [해설] 이 문제는 별 찍에서 층이 홀수일 때와 짝수일 때를 나눠서 해결하면 쉽습니다. 홀수일 때는 앞에 공백이 없고, 짝수일 때는 앞에 공백이 있는 별을 만들어주면 됩니다.

[문제] & [결과] [해설] 이 문제는 피보나치 수열을 구현하는 문제입니다. 피보나치 수열에 대한 간단한 설명은 위의 문제 설명에 있습니다. 그럼 바로 아래의 코드를 보시면, FIbo라는 함수에 첫 번째, 두 번째 값들은 초기화해주었습니다. 그리고 첫 번째, 두 번째일 때는 각각의 값들을 반환하도록 적어주었습니다. num까지의 수중에서 첫 번째와 두 번째를 제외한 부분은 반복문을 통해서 하나씩 옮겨가면서 처리해줍니다. c언어를 공부하면 자주 연습했던 swap이랑 비슷하지만 n2=n1+n2으로 처리해줬기 때문에 조금 다릅니다. 그렇게 하고 마지막에 n2를 반환해주면 끝! 참고로 Fibo함수에 주석처리되어 있는 부분은 반복문이 아니라 재귀함수로 풀은 것입니다. 재귀함수를 이용하면 코드의 길이는 더 짧아지고..