Astercle

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr ㅎㅎㅎㅎㅎㅎㅎ어려운 문제였다. 해당 문제는 "누적합"이라는 개념을 변형한 문제이다. 먼저 누적합은 아래와 같다. 1. 1차원기존의 배열이 아래와 같다면12345 누적합은 아래와 같이 된다.1361015 보기에도 알 수 있듯이 그저 앞의 값에 자기 자신을 더하면 된다.따라서 arr 라는 배열의 길이가 n이라면const n = arr.length;// 누적합 배열 선언 후 0으로 초기화const prefixArr = A..

https://school.programmers.co.kr/learn/courses/30/lessons/389481 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 시간 복잡도는 비슷하지만코드 길이를 줄일 수 있는 문제였다. 그리고 C++로 풀지 않음에 감사했다. (Python이 더 좋다.)다시 JS로 돌아와서!제약조건에 있는 수로는 오버풀로가 일어난다.(Number는 -(2^53 -1) ~ 2^53 - 1까지 이므로 약 10^16까지 된다.) 따라서 안전하게 BigInt로 바꾸었다.(여기서 알아둘 것은 Number + BigInt하면 자동으로 형을 변환하지 않기 때문에 TypeError가 발생한다.)..

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를 반환하도록 구현하였다. 비트마스킹의 경우 정수를 사용한다. (배열 - 공간복잡도 초과, 문자열 - 문자열은 바꿀 수 없음 -> ..