level3
-
[프로그래머스] 정수 삼각형알고리즘/프로그래머스 2021. 9. 15. 19:53
문제 링크 풀이 점화식 d[i][j]는 왼쪽 대각선 위인 d[i-1][j-1]와 오른쪽 대각선 위인 d[i-1][j] 중에서 큰 값을 triangle[i][j]와 더해준 값입니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + t[i][j] 코드 #include #include using namespace std; int wrap(int a) { return a < 0 ? 0 : a; } int solution(vector triangle) { int answer = 0; int size = triangle.size(); vector d(size, vector(size, 0)); for (int i = 0; i < triangle.size(); ++i) for (int j = 0..
-
[프로그래머스] N으로 표현알고리즘/프로그래머스 2021. 8. 17. 21:18
문제 링크 풀이 많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다. d[1] = {5} d[2] = {55, 5+5, 5-5, 5*5, 5/5} d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5} 3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요. d[2]를 보..
-
[프로그래머스] 추석 트래픽알고리즘/프로그래머스 2021. 8. 15. 19:58
문제 링크 풀이 문자열로 되어 있는 시간 로그를 실제 숫자로 변경해 주어진 로그에서 시작 시간을 구해, 시작 시간과 완료 시간을 pair로 가지는 벡터에 넣습니다. 1초 동안 최대로 걸려 있는 처리량을 구하는 것이 답입니다. 문제를 보면 lines 배열은 응답완료시간을 오름차순 정렬이 되어 있습니다. 이 말은 n번째 로그의 완료시간은 무조건 n-1보다 늦다는 이야기가 됩니다. 즉 시작 시간을 기준하면 됩니다. 예제 2를 보면 첫 번째 로그가 끝나는 시점과 두 번째 로그의 시작 지점이 1초에 같이 속하기 때문에, 최대 2개가 카운트 된다는 것이 힌트입니다. 1초라는 간격을 적용했을 때 카운트할 수 있는 최대값을 찾는 것이 목표입니다. 즉 n번째의 시작 시간이 n-1번째의 완료시간 + 999ms보다 같거나 ..
-
[프로그래머스] 네트워크알고리즘/프로그래머스 2021. 5. 21. 17:07
문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..