Hello World!

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 아주 전형적인 LIS 문제였다. LIS는 Longest Increasing Subsequence의 준말로, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 부분 수열은 연속적일 필요가 없다는 것을 명심하자. 만약, 부분 문자열(substring)이었다..

문제 링크: https://leetcode.com/problems/max-consecutive-ones-iii/ Max Consecutive Ones III - 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 학교 실습에서도 슬라이딩 윈도우 문제가 등장했기 때문에 더 중요성을 체감하는 중이다. 이 문제는 학교 실습 문제보다는 훨씬 간단한 슬라이딩 윈도우 문제였다. 두 포인터 start와 end는 모두 인덱스 0을 가리키는 상태에서 시작한다. 만약 end포인터가 가..

문제 링크: https://leetcode.com/problems/minimum-size-subarray-sum/ Minimum Size Subarray Sum - 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 투 포인터는 빠삭하게 공부해야 할 알고리즘 중 하나이다. 한동안 관련 문제들 많이 풀었었는데 요즘 또 소홀해졌다. 이 문제의 경우 주어진 배열의 값이 모두 양의 정수이기 때문에 포인터 start와 end 모두 0부터 시작하여 누적합이 target s값 이..

문제 링크: https://leetcode.com/problems/two-city-scheduling/ Two City Scheduling - 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 easy 문제로 분류되어 있지만 꽤나 머리를 많이 썼던 문제다. 그래도 AC을 받고서 엄청 뿌듯했다. 역시 그리디는 아직도 어렵다. 최소의 비용으로 A, B 두 도시에 각각 N명의 사람들이 방문할 수 있는 방법을 찾는 문제다. 따라서 주어진 입력에 대해 A 방문 비용과 B 방..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹에 거의 정형화되어 있는 재귀 함수를 짜는 연습하기에 좋은 문제였다. 단, 문제에서 암호를 사전 순으로 출력하라 했으므로 재귀 함수를 호출하기 전에 문자들을 정렬해주었다. /* 20200401 baekjoon 1759번 암호 만들기 */ #include #include using namespace std; char arr[15]; char ans[15]; bool isC..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 입력받은 N에 대해 자릿수를 계산한 뒤 해당 자릿수를 제외한 자릿수를 가지는 수의 개수를 arr배열에 미리 저장해둔 값을 이용해 계산해주었다. 그리고 해당 자릿수의 값들은 개수를 직접 계산해서 더해주었다. 예시로 N = 12인 경우를 간단히 살펴보자. 12는 두 자릿수이므로 len = 2이다. 한 자릿수의 수들(1~9)는 arr [1] 개이고 각 수는 한 자릿수이므로 총 9자리이다. 두 자릿수는 12 - 10 + 1 = 3개이고, 각 수는 두 자릿수이므로 총 3*2 = 6자리이다. 따라서 총 15자리..