https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법문제를 읽으며, 일반 적인 브루트포스 기반의 구현을 생각했지만, 데이터의 크기 상 불가능했다.다른 방법을 시도했으나 시간 초과였고, 결국 해설을 읽고 문제를 풀었다. 해설에서는 누적합을 기반으로 문제를 해결했다.skill 배열을 순회하며 board에 적용할 마스크를 만들고 마지막에 더해주는 방법이다.1차원 배열에서 마스크를 만드는 방법[1,3,5,23,5,9]의 배열에서 1 ~ 3번 원소에 -4, 0 ~ 5번 원소에 +2를 한다고 가정..
https://school.programmers.co.kr/learn/courses/30/lessons/67259?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법보드의 크기 n 이 25이하이고 입력에서 걱정할 부분이 없기때문에 BFS를 생각했다.BFS를 하며 Cost를 기록하고, 이를 활용해서 최소값만을 계산하려고했다.하지만 문제가 있었다.(1,0)에서 2000코스트이고, (1,1)으로 직진 후 아래로 코너를 돈다(0,1)에서 1700코스트이고, (1,1)으로 아래로 코너를 돈 후 직진을 한다위 두가지 경우에서 1번이 (1,1)에 2100, 2번에 (1,1)이 2400코..
https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법임의의 노드에서 도착지까지의 최단거리를 구하면되므로 BFS를 떠올렸다.도착지를 기준으로 n개의 노드를 distMap에 기록하며 거리를 계산하고 출력했다.코드import java.util.*;class Solution { public int[] solution(int n, int[][] roads, int[] sources, int destination) { List> graph = new ArrayList(); ..
https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법팰린드롬이 되는 경우는 2가지가 있다.aaabbbaaacbbb위처럼 중간에 하나의 문자는 끼어있어도 팰린드롬 수이이다.따라서 s를 선형탐색하며 팰린드롬을 찾는 find함수를 실행했다.문자열 s범위내이고, l,r 포인터의 문자가 같을경우 좌우로 퍼져가며 탐색l,r 포인터가 한번 더 진행하므로 r-l+1-2 => r-l-1이 해당 팰린드롬 수의 길이가 된다.전역변수 ans를 대소비교를 통해 갱신한다코드class Solution{ in..
https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법재귀 알고리즘의 스테디 셀러 문제이며, 구현 과정은 다음과 같이 일반화를 통해 풀 수 있다.n-1개의 원판을 1번 기둥 -> 2번 기둥으로 옮긴다1개 (가장 큰) 원판을 1번 기둥 -> 3번 기둥으로 옮긴다.n-1개의 원판을 2번 기둥 -> 3번 기둥으로 옮긴다코드class Solution { int[][] ans; int idx = 0; public int[][] solution(int n) { ans = ..
https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법삼각형의 위에서 아래로 이어지는 경로의 값을 더할때, 최대값을 찾는 문제이다.DP가 직관적으로 생각났다.memo배열을 만들고 최대값을 기록하며 이동했고, 가장 아래행 원소의 값을 비교하면된다코드class Solution { public int solution(int[][] triangle) { int n = triangle.length; int[][] memo = new int[n][n]; m..
