문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 연속한 자연수의 합으로 자연수 n을 표현하는 방법의 수를 구하는 문제이다. 예시인 n = 15인 경우는 다음과 같다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 이 숫자들의 합을 구하기 위해서는 자연수들의 합을 메모이제이션 해놓는 것이 좋다고 판단했다. 그 이유는 4 + 5 + 6이라는 값을 구할 때, 미리 구해놓은 1부터 6까지의 합(1 + 2 + 3 + 4 + 5 + 6)에서 1부터 3까지의 합(1 + 2 + 3)을..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 주어진 조건에 따라 문자열을 다시 만들어주는 문제이다. 두 문자열 s, skip과 자연수 index가 주어질 때, 조건은 다음과 같다. 문자열 s의 각 알파벳을 index만큼 뒤의 알파벳으로 바꿔준다. index만큼의 뒤의 알파벳이 z를 넘어갈 경우 다시 a로 돌아간다. skip에 있는 알파벳은 제외하고 건너뛴다. 이 조건을 보았을 때, 먼저 전체 소문자 알파벳 문자열을 만들어준 뒤, skip에 포함된 알파벳들을 제거해서 우리가 사용할 알파벳 배열을 만들어주어야 한다. alph..
문제 링크 문제 풀이 이 문제는 문자열 사이에서 미리 주어진 부분 문자열들을 찾아내는 것이다. 문자열 전체가 부분 문자열로 이루어져 있고, 같은 부분 문자열이 연속적으로 배치되지 않은 문자열을 찾아야한다. 각각의 문자열은 주어진 부분 문자열의 길이만큼 추출한 뒤 비교해서 같으면 그 부분을 삭제시키는 방식으로 풀었다. 만약 문자열이 주어진 부분 문자열로만 이루어져있다면, 반복문을 통해 완전히 제거가 될 것이다. 마지막에 길이가 0인 문자열일 경우, 부분 문자열로 이루어진 문자열로 판단할 수 있으므로 정답을 찾을 수 있다. 정답 코드 C++ #include #include using namespace std; int solution(vector babbling) { int answer = 0; for (in..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 1부터 number까지의 자연수들의 약수의 갯수를 구해야하는 문제이다. 자연수 n의 약수를 구하는 법은 쉽다. 반복문을 1부터 n까지 돌려 n을 i로 나누었을 때 나머지가 없을 경우, i를 약수라고 하기 때문에 반복문을 잘 써주면 된다. 하지만 이 문제에서는 시간복잡도가 중요하기 때문에 우리는 보다 적은 반복만으로 약수를 구해야만 한다. 대부분의 약수는 짝이 존재하기 때문에, 반복문을 반만 돌려도 약수를 찾는데에는 무리가 없을 것이다. 여기서, 더 나아가자면, 자연수 n의 약수..
문제 링크 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 문제 풀이 이 문제는 기본 DP문제의 형태를 띄고 있다. 이 문제도 동전 문제들과 비슷하다. 또, 2의 멱수의 합을 참고해도 좋을 것이다. [C++, python] BOJ, 백준 2410 - 2의 멱수의 합 문제 링크 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 이 문제는 기본 DP 문제라고 해도 될 정도 woongtech.ti..
문제 링크 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 이 문제는 기본 DP 문제라고 해도 될 정도로 많이 보이는 유형이다. 사람들이 정말 많이 푸는 동전 문제들과 비슷한 문제이기도 하다. 동전 1 동전 2 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 문자열에서 조건에 맞게 각각의 문자들을 판별하고, 변환된 문자열을 반환하면 된다. 조건은 다음과 같다. 숫자, 알파벳, 공백으로 이루어진 문자열이 있다. 단어의 첫 문자가 알파멧이면, 대문자여야한다. 단어의 첫 문자를 제외한 나머지 문자 중 알파벳은 소문자여야 한다. 단어는 공백으로 구분된다. 숫자는 그대로 출력된다. 이 조건에 맞도록 알파벳을 변환시켜주었다. C++은 아스키코드 값을 활용해서 문자를 변환해주었고, python에서는 upper()와 lower()함수를 통해 변환..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 숫자와 공백으로 이루어진 문자열에서 숫자를 뽑고, 최댓값과 최솟값을 찾는 문제이다. C++에서는 파이썬처럼 split 함수를 사용할 수 없기 때문에, split함수를 직접 구현하거나, 문자열에서 특정 문자를 구분자로 활용해 부분적인 문자열을 추출하는 방법으로 라이브러리와 getline을 활용해 공백을 분리해줄 수 있다. #include #include #include #include using namespace std; int main(){ // 공백 분리할 문자열 선언 str..
