Astercle

[JS] 프로그래머스 보물 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/468378 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 어렵다. 해당 문제는 "최소의 비용"으로 보물을 찾는 문제였다.먼저 그리디, 이분 탐색 모두 실행해봤지만 실패였다. (최악의 경우를 대비하지 못한다.) 따라서 미리 최악의 비용을 계산한 뒤에최악의 비용이 최소인 곳으로 검사하는 방향으로 설계해야 한다.그 말인 즉슨 dp를 사용했다. dp를 3차원으로 설계하고dp[구간 시작점][구간 끝점] = [최악의 비용, 최악의 비용일 때의 인덱스]로 초기화했다. 1. 구간의 길이가 0일 때 초기화했다. dp[sta..

https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr dp 문제이다.자세한 것은 주석에 적어 놓았다.(그래도 짧게 설명하자면,삼각형을 기준으로 이전 삼각형의 오른쪽 아래 마름모가 있는지 없는지 분기처리 해서 풀었다.)그리고 코드가 짧아보이는 것은 먼저 분기처리를 한 뒤에 하나로 합쳤다. 추가로 공간복잡도를 더 줄인다면이전 오른쪽 아래 마름모 있는 개수, 이전 오른쪽 아래 마름모 없는 개수두 개의 변수를 사용하면 된다. 참고로 10007로 항상 나눠 줘야 한다. (잘 못하면 오버플로 일어날 수 있다.) /..

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=python3 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr python 비트마스킹으로 가져왔습니다.가지치기를 도입했다. 이미 방문한 노드를 또 방문한다면 early return하는 방향으로 설계. 주석에 설명을 적어 놓았습니다. 주석을 참고해 주세요! # 설계# 가지치기 도입 (지금까지 방문한 노드의 비트마스킹) -> set으로 관리# 지금까지 방문한 노드의 경우 넣기 전에 표시하고 넣어야 하기 때문에# 먼저 표시하고 -> dfs돌리는 형태# 이와는 반대로 후보 노드들의 경우 순서..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해당 문제는 우리가 알고 있는 bfs/dfs 문제와 달리 방문한 노드를 또 방문할 수 있었다.따라서 이 부분을 어떻게 고려할까 고민을 많이 했다. 정답은 후보 노드 배열을 생성하는 것이었다.후보 노드 배열을 백트래킹으로 만들어서 관리하는 것도 시도해 보았지만 실패했다.(js는 shift()를 사용하면 시간복잡도가 O(n)이 나오기 때문에 head를 사용해야 하고 head 관리가 복잡해진다. 등등)그나마 다행인 것은 노드의 최대 수가 17개이므로 후보 노..

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 역시 사람은 많이 시도할수록 빨리 성장한다. 원래는 lv3여서 어렵게 가려고 했다.왕복 횟수와 최단 거리로 가는 횟수를 구해서 그 두 개가 양수이면 계속 가는 것으로 했다.그리고 왕복 횟수를 줄일 때 왕복 배열에 기록해서 다시 되돌아오도록 했다.그러나 너무 복잡해져서 (왕복횟수랑 최단 거리로 가는 횟수를 어떻게 구분? 저 왕복 배열 관리 등 등) 검색했다. 답은 간단했다.그 다음으로 가는 위치 ~ 목표 지점까지의 거리 이동(왕복 포함) 가능! 사전순..

https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 다시 풀어봐야 하는 문제이다.먼저 시간복잡도 때문에 이분탐색이라는 것을 추론해냈다. (주석에 보면 소거법으로 구했다.)그러고 나서 시간을 기준으로 풀어야 한다는 것도 파악했다.근데 그 안에 제한 시간이 주어진다면 그 안에 무엇을 해야 할지 알 수 없었다.(과정이 복잡했다. 금을 구해야 하는지 혹은 은만 구해야 하는지 혹은 둘 다 적절히 구해야 하는지 말이다.)따라서 찾아보니 이런 경우에는 금만 구하는 경우, 은만 구하는 경우, 둘 다 적절히 구하는 경우..

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 다익스트라였다. (가중치 1 이상, 양수, 최단 거리 혹은 최솟값 구하기.)따라서 JS만의 특징으로 인해 최소힙을 클래스로 구현하였다. (이게 최소이다. 꼭 외워두자) 기본적인 다익스트라와의 차이점은 이 문제는 거리를 기준으로 하는 것이 아니라 '가중치가 최대'인 값이 최소여야 했다.조금 헷갈릴 수 있지만 주석으로 정리해두었다. 그래서 결론1. MinHeap 외우기 (흐름을 기준으로 외우면 편하다)2. ..

https://school.programmers.co.kr/learn/courses/30/lessons/250134?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 참고로 방법 1은 dfs + 백트래킹이다.방법 1의 경우 2차원 배열을 두 개 만들어 놓고 false, true 왔다 갔다 백트래킹으로 풀면 되었다.그러나 방법 1은 무조건 완전 탐색이므로 시간이 좀 더 걸린다.따라서 방법 2의 무조건 빨간색, 파란색 수레 모두 도착하는 경우 바로 cnt를 반환하도록 구현하였다. 비트마스킹의 경우 정수를 사용한다. (배열 - 공간복잡도 초과, 문자열 - 문자열은 바꿀 수 없음 -> ..

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 구현 + 이진 탐색이었다.선형 탐색으로 level을 구하기에는 시간 복잡도가 초과될 거 같았다.(level 선택하는 경우 * 반복문 돌리면서 제한 시간 안에 되는지 확인) 따라서 start, end 변수를 사용해서 이진탐색을 이용 -> 로그로 시간 복잡도를 줄였다.추가로 start 즉, start === end의 경우도 구할 수 있다. 추가로 start start = mid 또는 end = mid라면 mi..

https://school.programmers.co.kr/learn/courses/30/lessons/214289 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 방법1 - 2차원 배열 [시간][실내온도]로 선언 후 시간 순서대로 넣기-> 왜 시간, 실내온도일까 (독립변수이기 때문. f(시간, 실내온도) = 소비전력)방법2 - 1차원 배열 [실내온도]로 선언 후, 새로운 배열 매번 선언방법3(현재 방식) - 1차원 배열 이전 온도, 현재 온도 배열 선언 후 매번 swap 1. dp로 판단한 이유 = 2^1000 (완전 탐색은 안된다 = dfs + 백트래킹 등등 불가)최적해 => 최적해!, 점화식 그릴 수 있어서..