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/81302# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법탐색 범위가 5*5*5 이므로 맘편히 완탐하면된다.구현 단계도 굉장히 심플하다 각 격자 탐색체크 및 배열 저장배열 반환체크 구현먼저 맨해튼 거리 2 이하인 위치를 사전에 정해놓았다 (checkLoc)전체 격자를 순회하며 !OOB이고 checkLoc 배열로 움직인 r2,c2 또한 P일때 검사를 수행한다거리가 1이하면 거리 두지 않았다2이상일때, 사람 사이 경로가 모두 파티션이어야한다[구현시 놓쳤던 것]왼쪽 아래 위치를 빼먹고 5개의 위..
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이를 다시 재귀로 돌린다올바르지 않다면출력 문자열..
