프로그래머스

[javascript] 프로그래머스 - 네트워크

🤔문제 해결 Lv3 | DFS 몇개의 싸이클이 있는 지 찾아야 한다. DFS(BFS)를 이용해도 무방하다. 전체 네트워크 중 하나를 차례로 선택한다. DFS로 visited를 체크하며 돌린다. DFS가 끝나면 그게 한 싸이클이 된다. (네트워크의 수) 아직 방문하지 않은 나머지 네트워크를 하나씩 차례로 선택하면서 위의 과정을 반복한다. 💻소스 코드 function solution(n, computers) { var answer = 0; let visited = Array(n).fill(0) let stack = [] for (let i = 0; i 0)..

[javascript] 프로그래머스 - 두 개 뽑아서 더하기

🤔문제 해결 1. 2중 포문을 이용하여 서로 다른 2 숫자를 더한 값을 배열에 담는다. 2. 중복을 제거한다 set 3. 정렬한다. 💨 💻소스 코드 function solution(numbers) { var answer = []; for ( var i = 0; i { return a-b }) return result; } 📕문제 확인 출처: 프로그래머스 링크: https://progra..

[python] 프로그래머스 - 풍선 터트리기(월간 코드 챌린지 시즌1)

🤔문제 해결 Lv3 풍선이 살아남을 수 있는 조건: 내 풍선 기준 왼쪽 풍선 크기가 클 때 내 풍선 기준 오른쪽 풍선 크기가 클 때 만약 왼쪽과 오른쪽 둘다 크기가 작으면 풍선은 죽는다 이 문제에서 핵심은 풍선의 크기가 가장 작은 녀석들을 하나씩 뽑아주면 되는 것! 값을 기준으로 정렬을 해주면 크기가 가장 작은 풍선(5)은 무조건 살아남는다. - (모두 다 터트릴 수 있다) 크기가 두번째로 작은 풍선(6)도 무조건 살아남는다. - (자신보다 작은 풍선(5)을 터트릴 찬스가 1번 있기 때문) 크기가 세번째로 작은 풍선(7) 부터는 인덱스의 상황에 따라 결정된다. 만약 7이 앞의 두 풍선 사이에 있을 경우 자신의 양쪽이 모두 작기 때문에 풍선은 죽는다. 하지만 두 풍선 사이가 아니라면 ( 5 < 6 < 7 ..

[python] 프로그래머스 - 3 x n 타일링

🤔문제 해결 Lv4 | dp 2 x n 타일링 문제와 마찬가지로 dp 문제. 완전 탐색으로 초반 몇 가지 경우의 수를 구한다.(손이나 코드로...) 몇 가지 경우의 수를 가지고 점화식을 세운다. 나는 1번 부분을 하다가 수가 너무 커져 시간이 오래걸릴까봐... 다른데서 가져왔다 나같은 사람을 위해 이제 위의 경우의 수를 가지고 식을 세우면 된다. 규칙성은 무조건 있다 💨 💻소스 코드 def solution(n): answer = 0 dp = [0] * (n + 1) dp[0] = 1 # 아무것도 두지 않는 경우도 1가지 sub = 0 for i in range(2, n + 1, 2): dp[i] = dp[i - 2] * 3 + sub * 2 sub += dp[i - 2] answer = dp[n] % 1..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 숫자 블록

🤔문제 해결 Lv4 구간(begin ~ end)이 정해져 있으므로 전부를 구할 필요는 없다. 선택한 구간만 잘라서 여기에 어떤 숫자가 들어가야 할지를 알아보자. 규칙을 잘 살펴보면 I 의 약수 중( 1 제외) 가장 작은 수로 나눈 몫이 해당 인덱스의 값이 된다. 10을 보면 2,5,10 중 2로 나누면 값은 5이다. 9의 경우 3,9 중 3으로 나누면 값은 3이다. 7의 경우 소수이므로 7로 나누면 값은 1이다. 위의 방법으로 코드를 짜면 정확도 테스트는 아주 쉽게 통과한다. 💡중요 이제 효율성 테스트가 문제인데 시간초과도 아니고 실패 라고 한다.이유는 전체 도로의 길이는 10^9 이지만 블록의 숫자는 10^7 까지이다.몫이 10^7을 넘어가게 된다면 사실상 해당블록은 존재하지 않는다!!그러므로 몫이 1..