https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법무방향 그래프가 주어지고, 그래프를 최소 가중치로 연결한 값을 구해야한다.최소 신장 트리(프림 or 크루스칼)로 풀 수 있다프림알고리즘을 설명해보자면 다음과 같다임의의 정점을 선택해 최소신장트리(MST)에 추가한다. -> 해당 정점과 연결된 모든 간선을 우선순위큐에 추가cost를 기준으로 오름차순 정렬하는 우선선순위 큐에서 간선을 poll한다만약 해당 간선이 MST에 포함된 두 정점을 연결한다면 Continue그렇지않고 MST에 포함된 ..
https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법격자의 크기가 1000 * 1000 이다.격자를 순환하며 격자의 크기를 탐색하는 방법 -> 3차원 배열로 해결할 수 있지만 10^9이므로 시간초과가 발생한다 따라서 O(n^2) 이하의 알고리즘을 사용해야한다dp를 사용해 현재 현재 정사각형의 크기를 기록하며 최대값을 비교하자현재 idx를 (r,c) 라고 할때, (r-1,c-1), (r-1,c), (r,c-1), 값과 (r,c)이 모두 1이면 한 변의 길이가 2인 정사각형이다따라서 0인경..
https://school.programmers.co.kr/learn/courses/30/lessons/147354 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법data배열의 길이는 최대 2500, 각 data의 원소인 배열의 길이는 최대 500따라서 시키는대로 구현하면 된다연산에 사용되는 index와 실제 저장되는 index의 차이를 잘 생각하면된다코드import java.util.*;class Solution { public int solution(int[][] data, int col, int row_begin, int row_end) { Arrays.sort(data..
https://school.programmers.co.kr/learn/courses/30/lessons/64062# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근방법건너는 사람은 무한대, 각 돌의 내구도는 1 ~ 2억, 돌 내구도 배열의 크기는 최대 20만따라서 돌 배열을 순회하며 O(nlogm) 이하의 알고리즘으로 풀이를 해야한다한명씩 건널때 마다 돌 내구도는 -1이된다이분탐색으로 1 ~ 2억의 범위에서 적당한 사람 수 를 구하기로한다먼저 돌 내구도의 max값을 구해 이분 탐색을 구현한다건넌사람이 mid 값으로 가정하고 돌 내구도 배열을 순회한다s-m 값이 0 이하인구간이 k이상 유지된다면 해당 ..
https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법결론은 문제에서 하란대로 하면된다 (근데 문제를 이해하기 힘들었다)문제의 핵심은 문자열을 받아 올바른 문자열로 바꾸는 메서드를 작성하는것이고 다음과 같은 흐름으로 구현할 수 있다입력 문자열이 비었다면 빈문자열을 반환한다입력 문자열을 u,v로 나눈다입력 문자열을 선형탐색하며 처음으로 "균형 잡힌 문자열"이 되는 구간 = u나머지 = vu 가 올바른 문자열이라면 출력 문자열에 u를 붙이고 v이를 다시 재귀로 돌린다올바르지 않다면출력 문자열..
https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법gems 배열의 크기는 10만 이하이므로 O(n^2)은 안된다.조건에 맞는 구간을 찾는 문제이므로 투포인터 생각구간내에 모든 보석 종류가 있는지 확인해야하므로 set에 보석을 담아 보석 종류 개수 저장투포인터 구현right 포인터를 움직이며 구간을 늘린다 => map에 보석종류별로 몇개 나왔는지 저장left 포인터를 움직이는 조건: 포인터가 있는 보석이 1개 초과인 경우 움직이며 구간을 좁힌다길이 저장 조건: map 사이즈 == 보석 ..
