🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근dp 배열을 새로 만들고, 각 숫자로 향하는 경로의 합 중 최댓값만을 저장한다. 예를 들어, 동그라미 친 8 위치의 dp 배열에는 8을 도착 지점으로 한 경로 최대값을 저장하고 있다. 또한, 최대값을 삼각형 아래에서 위 방향으로 구한다면 더욱 쉽게 구현할 수 있다.(위 -> 아래, 아래 -> 위 모두 아이디어는 동일하게 구현할 수 있는데 아래 -> 위 코드가 배열 범위 부분에서 예외 처리 수고가 없어진다.)아래에서 위 방향으..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12900 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근규칙을 찾아 점화식을 완성하여 코드에 그대로 구현하면 된다. n = k일때 만들 수 있는 타일 조합은 다음과 같다.k-1일때 만들 수 있는 타일 목록에 각각 세로 타일을 하나 더한 것 k-2일때 만들 수 있는 타일 목록에 각각 가로 타일을 하나 더한 것.따라서 n = k 일 때 만들 수 있는 타일 조합의 경우의 수는 (k-1일때 경우의 수) + (k-2일때 경우의 수)이다. 🔵 전체 코드#include #include us..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근n이 최대 10만이므로 재귀 함수를 사용하면 스택 오버 플로우가 발생할 수 있다. 재귀 함수를 사용하지 않고 푸는 방법은 메모이제이션을 이용하는 것이다. (dp 기본 개념) 또한 피보나치 수는 급격하게 증가하기 때문에 (a + b) % m 식으로 계산하게 되면 오버플로우가 발생한다.a + b가 int의 최대값을 넘을 수 있기 때문이다. 따라서 위 모듈러 연산의 분배 법칙을 사용하여 큰 수의 합을 오버플로우 없이 계산해야 한..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근규칙을 찾아서 풀이하였다.순간 이동(2배 이동) 시 발생하는 비용은 0이다.최대한 순간 이동하고, 순간 이동으로 갈 수 없는 경우 이동한다.따라서 N을 몫이 0이 될 때까지 2로 나누고, 나머지가 생길 때마다 count + 1 한다. 🔵 전체 코드using namespace std;int solution(int n){ int ans = 0; while (n != 0) { int r = n % 2; n /= 2; ..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근카펫의 가로 세로 크기를 반환하는 문제이다.문제의 조건에서, w>=h이므로 하나의 답이 확정되어 이차방정식으로 풀이하였다. * 관련식 전체 카펫의 가로, 높이를 w, h라 할 때. w * h = 노란 영역 + 갈색 영역(w - 2) + (h - 2) = (갈색 영역 - 4) / 2이므로, w + h = ((갈색 영역 - 4) / 2) + 4(참고로 w - 2, h - 2는 노랑 영역의 w', h'이다.)위 두 식을 이용하여 ..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/132265 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근topping의 길이가 최대 100만이므로 O(N^2)으론 풀 수 없다.그 이하 시간 복잡도 알고리즘을 생각해내야 한다. (내가 풀어 봤을 땐) 토핑을 철수와 동생에게 그때마다 갈라서 나눠주는 것은 대체로 O(N^2) 시간 복잡도이다.하지만 토핑을 한쪽에게 모두 주고, 그 다음 하나씩 다른 사람에게 나눠 주며 비교하는 것은 O(N)으로 풀 수 있다. unorered_map을 이용하여 위 아이디어를 그대로 구현하였다. 🔵 ..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근문제에서 제시한 대로 구현하면 된다.참고로 0과 1의 개수를 셀 때 algorithm 헤더의 count함수를, 정수를 이진 변환할 때 bitset 헤더를 쓰면 간편하게 할 수 있다. 🔵 전체 코드#include #include #include #include using namespace std;vector solution(string s) { vector answer; int binaryCnt = 0; i..
🔵 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🔵 문제 접근 (프림 알고리즘 기반) 위 그림에서 빨간색 화살표 방향 (4 -> 8)로 바로 이동하려면 사다리를 놓아야 하지만, 파란색 화살표 방향 (4 -> 5 -> 5 -> 8)으로 가면 사다리 비용 없이 8로 이동할 수 있다.문제에서 요구하는 것은 사다리 비용을 최소로 하여 모든 좌표를 방문할 때, 최소 cost이다.따라서 위 예를 생각하면서 문제를 풀어 보자. BFS 방식으로 그래프 탐색을 진행하되, 일반 큐가 아닌 현재 좌표와 ..
