알고리즘 공부 및 문제 풀이/프로그래머스(PRO) (81) 썸네일형 리스트형 [pro] 프로그래머스 level4 42897 도둑질 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 스티커 모으기2 문제와 똑같다! 1. 집이 원형으로 배열되어있으므로 첫번째 집을 터는 경우(마지막 집을 털 수 없음)와 안터는 경우로 나눈다. 2. dp[i]는 도둑이 i번째 집까지 왔을 때 훔칠 수 있는 돈의 최대값. 따라서 i번째 집을 터는 경우와 털지 않는 경우로 나눌 수 있다. 터는 경우 이전 집에 경보가 울리므로 dp[i-2] + money[i]가 될 것이고, 털지 않는.. [pro] 프로그래머스 level3 42627 디스크 컨트롤러 (Java) - 힙(우선순위 큐) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 1. 소요시간이 짧은 순서대로 처리해야 평균 대기 시간이 최소가 될 것이다. 2. 소요시간이 짧더라도 요청 시점이 터무니없이 뒤에 있다면 평균 대기 시간은 늘어날 것이다. 따라서 현재 작업이 끝나는 시점보다 앞서 들어온 요청에 대해서 수행시간이 짧은 작업을 처리한다. 이때 우선순위큐를 이용한다. [코드] import java.util.*; class Solution { publi.. [pro] 프로그래머스 level3 12942 최적의 행렬 곱셈 - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12942 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] https://stritegdc.tistory.com/180 [boj] 백준 11049 행렬 곱셈 순서 (c++) - dp [문제] https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, striteg.. [pro] 프로그래머스 level3 42579 베스트앨범 (Java) - 해쉬 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42579https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] HashMap을 이용한 연산을 통해 해결 가능. [코드] import java.util.*; class Solution { Map hs = new HashMap(); //장르별 총 재생횟수 Map music = new HashMap(); //장르별 고유번호와 재생횟수 .. [pro] 프로그래머스 level3 12987 숫자 게임 (Java) - 그리디, 투포인터 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] A의 각 값들을 B의 값이 최소한의 차이로 이기도록 하면 B의 최종 승점을 가장 높이는 방법이 될 것이다. 이를 위해 A와 B 배열을 모두 정렬한 후 포인터 2개를 두고 각 배열을 가리키도록 한다. A 값보다 B 값이 더 크다면(A와 B 배열을 모두 오름차순 정렬했으므로 가장 근소하게 A보다 B가 더 큰 경우가 될 것임) 승점을 높이고, A 인덱스와 B 인덱스 모두 증가시킨다. .. [pro] 프로그래머스 level3 12971 스티커 모으기2 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] dp[i]애는 i번째 인덱스에서의 숫자 합의 최대값을 저장한다. 고려해야 할 부분은 다음과 같다. 1. 스티커를 뗄 것인지, 떼지 않을 것인지? i번째 스티커를 떼어낸다면, i-1번 스티커를 떼어낼 수 없으므로 dp[i-2]+sticker[i]가 될 것이다. i번째 스티커를 떼어내지 않는다면, i-1번 스티커를 뗄 수 있으므로 i-1번에서의 최대값은 dp[i-1]이 될 것이다. .. [pro] 프로그래머스 level3 1836 리틀 프렌즈 사천성 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/1836 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 모든 tile들을 사전순으로 list에 넣어놓고 반복문을 돌며 제거 가능한 타일은 제거(제거 후 '.'으로 바꿔서 넣어줌)하도록 한다. 제거 못한 타일이 있으면 IMPOSSIBLE을, 모든 타일에 대해 제거가 가능하다면 정답 문자열을 반환한다. 이 문제에서 고려해야 할 점은 타일을 제거하는 방법이다. 경로를 한 번 이하로 꺾을 수 있다고 문제 조건에 제시되어 있기 때문에 DFS 등.. [pro] 프로그래머스 level3 1832 보행자 천국 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 처음 i-1, j-1에 대해서 배열 범위 오류가 나지 않도록 dp 배열에 패딩을 넣어준다. 이에 따라 cityMap의 (0,0)이 dp 배열의 (1,1)과 매핑된다는 것을 헷갈리지 않도록 주의해야 한다. cityMap이 2인 경우, 왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다. 이 조건을 판단하기 위해서는 왼쪽에서 오던 차인지, 위에서 오던 차인지.. 이전 1 ··· 4 5 6 7 8 9 10 11 다음
