https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법최대 50만 길이의 배열이 input으로 들어온다. 즉 O(nlogn) 이하의 알고리즘이 가능하다입력 배열에 각각 [1,-1,1,-1 ,1,-1...] [-1,1 -1,1, -1,1...]을 곱한 두가지 케이스에서 최대 부분수열의 max값을 찾아야한다따라서 dp 배열에 0번 열에는 +값만, 1번 열에는 -값을 저장한다즉, (i,0) 에는 (i-1,1) + seq[i]값이 0보다 크면 들어온다. (i,1) 에는 (i-1,0) - se..
https://school.programmers.co.kr/learn/courses/30/lessons/12899 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법5*10^7 이하의 자연수가 주어질때, 1,2,4만을 이용해서 숫자를 표현해야한다기본적으로 n진법을 구할때와 비슷하게 풀이했다다만 n이 3의 배수일때, 4를 추가해주고, n = n/3-1을 해주어야했다.코드class Solution { public String solution(int n) { StringBuilder answer = new StringBuilder(); while (n > 0) { ..
https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법데이터 범위가 n이 10억 이하, k가 50만 이하, enemy배열의 길이가 100만 이하 이다.따라서 enemy배열을 O(n^2)미만의 알고리즘으로 순회하며 답을 찾아야한다이전 공격을 저장했다가 가장 낮은 데미지의 공격과 현재 공격을 비교해가며 답을 찾았다.우선 k의 수만큼 pq(== 무적권 스킬을 쓸 라운드의 공격력들)에 담는다가장 낮은 공격력과 현재 공격력을 비교한다현재 공격력이 높다면 이걸 무적권을 써야하므로 pq에 넣는다아니..
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..
