문제풀이
BaekJoon(1003)::피보나치 함수
문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제파악 피보나치수열 아마 쉽게 알 수 있는 문제일 것이다. 피보나치 수열이란? 첫째 및 둘째 항이 1이며 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열 그렇다면, 이 문제는 피보나치수열에서 무엇을 원하는 건지 알아봐야 한다. 피보나치수열의 점화식은 다음과 같다 $$f(n) = f(n-1)+f(n-2) \quad and \quad n \geqq 2$$ 정의상 n은 3 이상일 수 있지만 편의상 0번째 항의 값을 0으로 생각한다면 2 이상으로 생각해도 무관하다. 그리고 피보나치를 재귀로 구현하면 다음과 같다. int fibonacci(int n) { if..
BaekJoon(1010)::다리놓기
문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제파악 문제를 읽어보면 강을 중심으로 왼쪽 영역 N개에서 오른쪽 영역 M개의 영역으로 다리를 연결하게 되는데 그 때 가능한 케이스의 갯수를 구하는 문제이다. 이경우 다음과 같이 한영역에 다리가 겹쳐지거다 교차될 수 없다고 한다. 다음 그림을 보면 좀더 이해가 쉬울 거 같다. 이렇게 봤을 때...문제를 어떻게 해결할 수 있을까 생각해보면, M영역 즉, 우측지역의 영역에서 N(좌측)영역의 지역의 갯수만큼 선택해서 순서대로 연결해주면 교차하지도 않고 겹치지도 ..
BaekJoon(9461)::파도반 수열
문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제파악 파도반 수열은 리처드 파도반에 의해 이름이 붙여졌으며, 오른쪽 그림과 같이 삼각형들이 한변의 길이를 공유한 상태로 나선형으로 계속해서 이어지는 삼각형이다. 해당 수열이 진행을 보면 다음과 같다 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 수열과 같은 문제를 풀다보면 대부분 점화식을 찾아내면 쉽게 해결할 수 있다. 파도반 수열의 점화식은 다음과 같다 $$f(n)=\begin{cases}1 & \mbox{if }n..
LeetCode(977)::Squares of a Sorted Array
문제 Squares of a Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. 배열에 저장된 수들을 제곱하여 다시 정렬하면되는 문제로 파악된다. 1
LeetCode(344)::Reverse String
문제 Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. in-place로 문제 해결. 즉, 추가 메모리(공간복잡도)는..
LeetCode(344)::Reverse String
문제 Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory. in-place로 문제 해결. 즉, 추가 메모리(공간복잡도)는..
LeetCode(448)::Find All Numbers Disappeared in an Array
문제 Find All Numbers Disappeared in an Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. n == nums.length 1
LeetCode(189)::Rotate Array
문제 Rotate Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Given an array, rotate the array to the right by k steps, where k is non-negative. 배열의 값이 k스텝 마다 한칸씩 오른쪽으로 넘기면 될 거 같습니다. 문제풀이 해당 문제는 여러가지 풀이 기준이 존재하는데 인덱스 기준으로 생각할 수도 있으며, 시프트 방식으로 in-place로 문제를 해결할 수도 있다. 해결책 1..
LeetCode(43)::Multiply Strings
문제 Multiply Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제파악 Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. → 즉, 2개의 문자열로 표현된 양수가 들었을때 두스의 곱을 문자열로 표현하라~!! 1 = 0; j--){ int int_nu..
BaekJoon(2447)::별찍기-10
문제 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제파악 재귀적인 패턴으로 별이 찍혀있음(N은 3의 거듭제곱) 크기 3의 패턴은 가운데 공백이있음. 해당 패턴이 재귀에 따라서 커지면서 반복됨. 문제의 기본이 되는 가장작은 사이즈는 우측그림에서 보다시피 초록색영역으로 출력이 된다. 다만 재귀의 형태를 좀더 자세히 보고자 N=9로 확장해보면 파랑색영역으로 보이는것을 알 수 있고 그보다 크 27일때는 빨강의 영역이다. 그리고 별찍기의 특성상 별이 그려지면 탈출을 시켜주고 해당영역이 ..
BaekJoon(9020)::골드바흐의 추측
문제 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 파악 해당 문제는 제목에서도 말하듯이 골드바흐의 추측을 통해 해결할 수 있다. 골드바흐의 추측은 2보다 큰 짝수는 두소수의 합으로 나타낼수 있다는 추측으로 해당 수를 골드바흐 수라고 한다. 주어진 골드바흐의 수는 두 소수의 합들로 나타낼 수 있다. 여러 소수쌍중 해당 값의 차이가 가장 작은 것을 출력한다. 위 정리에서 알 수 있듯 우선 소수판별을 위해 에라테토스테네스의 체를 먼저 작성한다. 문제풀이 #include #include ..
BaekJoon(1850)::최대공약수
문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 파악 : 1로 이루어진 수의 최대공약수는 두 수의 길이의 최대공약수가 해당 공약수의 길이가 되며 그 공약수 또한 1로 이루어지게 된다. : 왜냐하면 두 수는 1로 이루어져 있기 때문에 위와 같은 이해가 만들어진다. 예시 1, 11, 111, 1111 → 1 11, 1111, 111111 → 11, 1111 문제풀이 : 두 수의 길이의 최대공약수를 구하면 그 값이 주어진 두수의 최대공약수의 길이가 된다. #include #inclu..