문제 해결/프로그래머스4 [프로그래머스] 등산코스 - python https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라를 활용하여 풀 수 있는 문제입니다. 이 문제의 경우에는 출발 지점 -> 산봉우리 -> 출발지점으로 되돌아와야하지만 경로의 길이를 구하는 것이 아니라 최소의 intensity를 구하는 것이기 때문에 출발지점 -> 산봉우리에 대한 다익스트라로 봐도 무방합니다(산봉우리를 향해 올라갔던 경로 그대로 되돌아오면 되기 때문에). 현재의 지점에서 다음 지점으로 넘어가기 위해서는 두가지 중 하나를 .. 2022. 10. 1. [프로그래머스] 외벽 점검 - python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에는 그리디 방식으로 접근을 해보았는데 탐욕적 선택을 해야하는 상황을 정의하기가 쉽지 않아서 완전 탐색으로 풀이했습니다. weak의 최대 길이 15, dist 최대 길이 8인 것으로 보았을 때 완전 탐색으로 풀이가 가능합니다. 풀이 방식은 다음과 같습니다. 결국 목표는 '원형인 외벽의 취약점을 모두 방문하기' 이므로 취약점의 위치에 n을 더해서 weak 배열에 추가해주면 됩니다. .. 2022. 9. 27. [프로그래머스] 양과 늑대 - python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs를 활용해야 하는 문제인데 조금 특이한(?) dfs 방식을 적용해야하는 문제입니다. dfs 동작은 다음과 같이 일어나게 됩니다. 1. 현재 양의 수가 늑대의 수보다 많은지 체크 1-1. 늑대의 수가 더 많다면 탐색을 종료 2. 방문 가능한 노드 리스트에 현재 노드의 자식들을 추가 3. 노드 리스트들에 대해 탐색 시작 위와 같이 동작해야하는 이유는 다음과 같습니다. 방문 순서에 따.. 2022. 9. 26. [프로그래머스] 파괴되지 않은 건물 - python 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 일반적으로 skill이 적용되어야 하는 범위에 매번 (r1, c1) ~ (r2, c2)에 적용을 하면 최악의 경우 O(Skill의 개수 * 최대 가로 길이 * 최대 세로 길이) = O(250000 * 1000 * 1000)가 되어 시간 초과가 나게 됩니다. 매번 범위에 적용하지 않고 한번에 발생한 Skill을 적용하기 위하여 누적합 방식이 필요합니다. 1차원 배열을 기준으로 생각했을 .. 2022. 9. 25. 이전 1 다음
