개발자 쿠키

1. 문제연속된 부분 수열의 합 (프로그래머스 Lv.2)비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾는 문제입니다.기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 반환하면 됩니다. 인덱스는 0부터 시작합니다.https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스SW개발자를 위한 평가, 교육의 Total ..

문제N x N 보드에서 (0, 0)부터 (N-1, N-1)까지 도로를 건설하는 최소 비용을 구합니다.빈 칸 0, 벽 1이며 벽은 지날 수 없습니다직선 도로 1개당 100원코너 1개당 500원 추가접근비용 기준 다익스트라로 접근했습니다. 문제는 같은 칸에 더 싸게 도착해도 그때의 진입 방향이 나쁘면 이후에 500원이 더 붙어 손해가 될 수 있다는 점입니다. 비용만으로는 한 칸의 상태를 대표할 수 없습니다.그래서 dist[n][n][4]로 (좌표, 진입 방향)을 하나의 상태로 관리하고, 출발 지점은 직전 방향이 없으므로 direction = -1로 두었습니다. 마지막에는 도착 칸의 4방향 값 중 최솟값을 고릅니다.핵심 두 줄다익스트라에서 실제로 중요한 부분은 nCost 계산과 그 밑의 갱신 조건문입니다. 특..

SWEA / D41249. 보급로문제 정보https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 접근격자에서 시작점부터 도착점까지 가는 최소 비용을 구하는 문제다. 격자 + 최단거리라는 조건만 보고 처음엔 당연히 BFS라고 생각했다. 그래서 첫 두 번의 시도를 BFS로 최단거리를 구하려고 했는데, 답이 제대로 나오지 않았다. 원인을 찾다가 BFS의 전제 조건 자체를 잘못 알고 있었다는 걸 깨닫고, 다익스트라를 새로 공부해서 다시 풀었다.시도 기록1~2..