프로그래머스 행렬의 곱셈 c++ 풀이 Level 2 연습문제 행렬의 곱셈 문제 정리 2차원 행렬 arr1, arr2가 주어질때 두 행렬을 곱한 결과를 반환하는 함수를 작성하여라 행과 열의 길이는 2 이상 100 이하이다. (최대 100x100) 행렬의 원소는 -10 이상 20 이하의 자연수이다. 곱할 수 있는 배열만 주어진다. 문제 풀이 20^2 x 100 = 400 x 100 = 40000으로 int형으로 가능 이 문제는 단순히 행렬 곱셈의 개념만 알고 있다면 풀 수 있습니다. 2차원 벡터를 다루는 문제로 좋은 예제라고 생각합니다. (실제로 제가 그랬음) 왼쪽 행렬의 i행, 오른쪽 행려의 j열을 sumproduct 하면 새로운 행렬의 (i,j) 위치의 값이 됩니다. 예를들어 arr1의 1행, arr2의..

프로그래머스 피보나치 수 c++ 풀이 Level 2 연습문제 피보나치 수 문제 정리 n이 주어질 때 n번째 피보나치 수를 1234567로 나눈 나머지를 구하여라 n은 2이상 100000 이하이다. 문제 접근 피보나치 수를 알기 위해서는 이전의 2개의 수만 알면 된다. 그렇기 때문에 2개의 수만 관리한다. n이 최대 100,000이기 때문에 배열을 모두 만들면 낭비이다. 또한 계속 값을 더해나간 후 마지막에 모듈러 연산을 하면 값이 범위를 넘어 이상한 값이 나올 수 있다. 그렇기 때문에 모듈러 연산의 성질을 이용하면 간단히 풀 수 있다. 모듈러 연산의 성질 이 성질만 안다면 간단히 풀 수 있습니다. (a + b) % c = ((a % c) + (b % c)) % c 예를들어 (10 + 1) % 3 = (1..

프로그래머스 최댓값과 최솟값 c++ 풀이 Level 2 연습문제 최댓값과 최솟값 문제 정리 문자열 s에는 공백으로 구분된 숫자가 있다. str에 나타나는 숫자중 최대, 최소 값을 찾아 "(최소값) (최댓값)" 형태로 반환해라 문자열에는 둘 이상의 정수가 공백으로 구분되어 있다. 문제 풀이 문자를 공백을 기준으로 나눈다. 나눠진 수를 차례대로 하나씩 숫자로 변환해본다. min, max와 비교해서 업데이트 해준다. 최종 min, max 값을 string으로 변환하여 정답을 완성한다. c++ 문자열 split sstream 헤더에 있는 istringstream 을 이용해서 나눌 수 있다. istringstream ss(split할 문자열)을 선언한다 자를 문자를 담을 string buffer를 선언한다(str..

프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..

프로그래머스 다음 큰 숫자 c++ 풀이 Level 2 연습문제 다음 큰 숫자 문제 정리 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다. ``` n의 다음 큰 숫자는 n보다 큰 자연수 n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 n은 1,000,000 이하의 자연수이다. 문제 풀이 n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다. 이를 n이 2나 1이 될때까지 반복한다. 마지막..

프로그래머스 더 맵게 자바(java) 풀이 Level 2 힙 H-Index 문제 정리 모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하여라. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return 하여라. 힙, 우선순위 큐 이는 힙(Heap)을 이용하여 풀 수 있습니다. 그 중에서도 힙을 이용해 구현된 우선수위 큐(..