FrontEnd/프로그래머스
[JS] N으로 표현
dp를 활용해서 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp[i] 는 N i개로 만들수 있는 숫자들의 모임이다. 처음에는 map 자료형을 통해서 { 숫자 -> 숫자를 만드는데 필요한 N의 개수 } 와 같은 방식으로 dp를 구현했었다. 이렇게 dp를 구현하니 문제가 있었다. 자, dp를 채우는 과정을 생각해 보자. 편의상 N이라는 말 대신 숫자 5를 써보겠다. 1. 5가 한개일때 만들 수 있는 수는 5 하나이다. => { 5..
![[JS] 산 모양 타일링 (카카오 겨울 인턴십)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FATUPg%2FbtsDETPskhs%2FSMEeiS9KlpaSlXx4YqAJK0%2Fimg.png)
[JS] 산 모양 타일링 (카카오 겨울 인턴십)
dp를 활용하여 해결할 수 있는 문제이다. https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이런 문제는 규칙을 찾는것이 중요하다. 해당문제와 같은 경우 조각이 추가되는 케이스가 2개다. 윗면이 있거나 없거나.. 잘생각해보면 윗면이 있는 경우는 이렇게 생각할 수 있다. 먼저 지금 추가되는 블럭을 i번째라고 생각해보자. 지금 추가한 3가지 블럭은 dp[i-1] 번째까지 블럭을 전혀 침범하지 않는다. 따라서 dp[i-1] * 3을 해주어서 경우의 ..
[JS] 이중우선순위큐
이분탐색을 활용해서 풀었다. https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 결국 문제에서 요구하는 것은 3개이다. 최소 , 최대를 바로바로 빼낼 수 있게 도와주는것 . 이분탐색을 활용하여 항상 정렬된 형태로 값을 넣는다면 문제를 해결할 수 있을것이라 생각했다. 이분탐색으로 정렬된 리스트에 값을 넣는것을 빠르게 했고 pop은 시간복잡도가 O(1) 이므로 괜찮을꺼라 생각했다. 조금 주의할점은 shift로 JS에서 shift는 O(n)의 시간복잡도..
[JS] 야근 지수
힙을 활용해서 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 야근지수를 가장 낮게 받는 방법은 생각보다 간단하다. 현재 남은 피로도 중에서 가장 큰값부터 피로도를 깎으면 된다. 문제 조건또한 1000000정도라서 시간도 충분할꺼라 생각했다. 이런 문제는 이분탐색을 활용해도 되고 힙을 활용해도 되는데 힙을 활용했다. 우선순위 큐를 활용하여 해결하였다. class MaxHeap { constructor(){ this.ary = [0]..
![[JS] 단속카메라](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbNp3aF%2FbtsDqNBSZy1%2FN42oaiUdr2P2av1QQ8VXb0%2Fimg.png)
[JS] 단속카메라
그리디 알고리즘을 활용하여 해결할 수 있는 문제이다. https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 이전에 2단계 문제중에서 상당히 유사한 문제가 하나 있던걸로 기억한다. [요격시스템] 풀이방법은 아래와 같다. 결국 과속카메라를 설치하는 것도 위 그림처럼 만드는 것이다. 한선분이 있다면 해당 선분은 무조건 포함되어야 한다. 따라서 시작점을 잡으면 그선의 끝점을 잡는다. 이 두점을 A,B라고 두자 다음 선분의 시작점이 B보다 뒤라면 무조건..
[JS] 도넛과 막대 그래프
그래프를 활용한 구현문제 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 처음에 문제에 대한 접근 자체가 힘들었었다. 선형, 도넛형 , 8자형 구분을 하란건 알겠는데 중심 노드가 주어지지 않았기 때문이다. 따라서 문제를 푸는 방식을 아래와 같이 단순화 해보았다. 1. 중심노드 찾기 (뻗어가는 노드 찾기) 2. 중심노드에서 뻗어나간 그래프들의 종류를 찾기 1. 중심노드 찾기 중심노드를 어떻게 찾을 수 있을까 고민했는데 중심노드는 자신에게 ..