문제https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 코드function solution(nodeinfo) { class Binary { constructor(idx, xPos) { this.idx = idx; this.xPos = xPos; this.left = null; this.right = null; } insert(idx, xPos) { if (xPos > this.xPos) { this.toRight(idx,..
알고리즘
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이번 문제는 탐색이다. 하지만 입력되는 배열의 길이가 100만으로 매우 긴 모습을 알 수 있다. 이렇게 입력이 큰 문제의 경우 시간복잡도를 고려한 풀이 설계가 필요하다. 문제를 읽어보면 한 풍선의 양쪽 풍선 중 하나만 터트릴 수 있으며, 두 풍선 중 작은 풍선을 터트리는 것은 한번만 가능하다.(큰 풍선을 터트리는 것은 횟수 제한이 없다) 필자는 최종적으로 남는 풍선의 관점으로 풀이를 진행했다. 맨 마지막에 남는 풍선은 왼쪽 혹은 오른쪽의 풍선들보다 작은 수를 갖어야 한다. 이러한 점을 이용해 투 포인터 알고리즘을 적용해 마지막에 남을 수 있는 지 ..
문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이필자는 해당 문제를 단순 구현으로 풀이하려 했다. DP 알고리즘을 이용해 이전 문자열 + '0'.repeat(5 ** (i - 1)) + 이전 문자열 로 문자열을 구해 풀려했지만, 특정 케이스에서는 컴파일 에러가 발생했다. 그래서 수학적인 접근을 시도했다. 우선 문자열에서 규칙을 찾아보자면, 1의 개수는 4 * n개 이다. 그리고 0은 5개로 자른 문자열에서 항상 2번 인덱스에 위치한다. 이와같은 특징을 이용해 1과 0을 구분할 수 있는 check 함수를 제작해보자.check 함수에서는 크게 3가지 경우를 처리한다.1. 입력된 인덱스 값이 5보다..
문제https://www.acmicpc.net/problem/2003 풀이투포인터의 기본 문제이며, 주어지는 수열에서 연속된 수들의 합이 M이 되면 카운트를 올리는 문제이다. 이 문제에서 while 문을 이용해 반복해주는 부분이 있는데, 이 while 문의 조건에 원래는 lp 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(Number);const arr = input[0].split(' ').map(Num..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이 문제는 DP 알고리즘을 이용해 풀이하는 문제이다. 이 문제를 보면 홀수 길이의 경우 절대 조건을 만족하는 경우가 없기에 0을 반환한다. 짝수 길이의 경우 점화식이 존재한다. 처음에는 어떻게 점화식을 만들지 잘 몰랐다. 하지만, 조금 더 생각해보면 짝수 길이만 되며, 이전의 경우를 이용한 경우를 추가하며 이전 값들을 이용하는 DP 알고리즘의 이용이 필요하다는 것을 알게되었다. 점화식은 ((dp[i - 1] * 4)) - (dp[i - 2]) % 1000000007 이지만, 이 경우는 dp[i - 1]..
문제https://www.acmicpc.net/problem/2579 풀이처음 이 문제를 풀때는 BFS로 접근했지만 나는 풀이 방법을 찾지 못했다... 시간초과 에러가 발생했다.... 그래서 순수하게 동적 계획법을 사용해 풀이하기로 결정했다. 이 문제를 잘 보면 특정 패턴이 보일 것이다. n 번째에 도달하는 방법은 두가지가 있다. 첫 번째로는 n-1 번째에서 한칸 뛰어넘어 온 경우이고, 두 번째는 n-2 번째에서 두칸을 넘어온 경우이다. 이때 두칸을 넘어온 경우는 문제가 되지 않지만, 한 칸을 넘어온 경우는 3칸을 연속해서 넘으면 안된다는 제한이 있다. 위와 같은 제한을 피하는 방법은 n-3칸에서 두칸 넘고 n-1칸에서 한칸 넘는 방법이 있다. 코드const input = require('fs') .r..
