문제 링크 문제 풀이 이 문제는 사과 리스트를 정렬 후, 박스 별 최저 가격의 사과를 찾아 답에 반영해주면 된다. 예를 들어 [1, 2, 3, 1, 2, 3, 1]의 사과 리스트에서 사과 4개씩 상자로 만든다면, 먼저 리스트 정렬을 내림차순으로 해준다. [3, 3, 2, 2, 1, 1, 1]로 정렬된 사과 상자에서 크기 순으로 4개씩 자르면, [3, 3, 2, 2]로 사과 상자를 만들 수 있을 것이고, 이 경우 사과의 최저 가격인 2를 반영해 2 * 4 = 8이라는 사과 상자 가격의 답이 나오게 된다. 여기서, 규칙을 찾을 수 있는데, 4개씩 자를 경우, 인덱스는 3, 7, 11 ... 순으로 사과 상자가 나뉘게 될 것이다. 이 점을 참고하면, 반복문을 통해 문제를 해결할 수 있다. 정답 코드 C++ #..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 이중 반복문을 사용해서 자신보다 앞에있는 문자들과 비교한 뒤, 같은 문자가 있다면 그 문자와의 거리를, 같은 문자가 없다면 -1을 추가한 뒤 반환시키면 된다. 정답 코드 C++ #include #include using namespace std; vector solution(string s) { vector answer; for (int i = 0; i -1; j-..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 문자열 t에서 p와 길이가 같은 부분 문자열을 추출한 뒤, 값을 비교해서 부분 문자열의 크기가 더 작은 경우를 뽑는 문제이다. C++의 경우, p의 길이에 따라 int형의 범위를 넘어가는 부분 문자열이 추출될 수 있으므로, stoll을 사용해 long long형으로 받아와야한다. python의 경우, 문자열 슬라이싱을 통해 부분 문자열을 추출할 수 있다. 정답 코드 C++ #include #include using namespace std; int solution(string ..
문제 링크 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개의 줄에는..
문제 링크 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 풀이 이 문제는 세 문자열 사이에 공통적으로 존재하는 부분 문자열 중, 가장 길이가 긴 문자열을 찾는 문제이다. 이 문제를 풀기 위해서는 LCS 알고리즘을 사용해야 한다. 이 문제는 공통 부분 문자열과 비슷하지만 약간 다르다. 문자열이 2개가 아닌 3개라는 점 가장 길이가 긴 연속하는 부분 문자열(STRING)이 아닌 연속하지 않은 부분 문자열(SUBSEQUENCE) 이 두개의 특징때문에 문제 풀이가 약간 달라진다. 연속하는 부분 문자열을 찾았을 때는 문자열1..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이번 문제는 " ( ) " 의 꼴인 문자열이 발견된다면, 올바르게 짝지어진 괄호라고 판단해서 True를 반환할 수 있어야 하는 문제이다. 즉, 올바른 괄호들을 찾아서 제거해주다보면, 올바른 괄호로만 이루어진 문자열은 모든 괄호들이 삭제될 것이다. 따라서, " ( ) "의 꼴인 문자열을 찾아 계속 제거해주면 된다. C++과 python에서 find와 replace같은 함수들로 반복문을 만들어서 해결할 수도 있겠으나.. find와 replace는 반복할때마다 처음부터 끝까지 탐색을 하기 때문..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 문자열에서 조건에 맞게 각각의 문자들을 판별하고, 변환된 문자열을 반환하면 된다. 조건은 다음과 같다. 숫자, 알파벳, 공백으로 이루어진 문자열이 있다. 단어의 첫 문자가 알파멧이면, 대문자여야한다. 단어의 첫 문자를 제외한 나머지 문자 중 알파벳은 소문자여야 한다. 단어는 공백으로 구분된다. 숫자는 그대로 출력된다. 이 조건에 맞도록 알파벳을 변환시켜주었다. C++은 아스키코드 값을 활용해서 문자를 변환해주었고, python에서는 upper()와 lower()함수를 통해 변환..
