https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해사용자의 입장, 퇴장, 닉네임 변경 기록이 주어질 때,모든 기록을 처리한 후 출력 메시지를 최종 닉네임 기준으로 구성해야 한다. 접근 방법userId와 nickname의 관계를 해시맵(userIdNameMap)에 저장record를 순회하며,입장(Enter)과 퇴장(Leave) 기록만 메시지로 남기기닉네임 정보가 있는 경우(Enter, Change)에만 해시맵을 갱신하기모든 기록을 처리한 뒤, 메시지에 저장된 userId를 최신 닉네임으로 변환 풀..

https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해길이가 같은 두 개의 큐가 주어진다.한 번의 연산은 한 큐에서 pop 한 원소를 다른 큐에 insert 하는 것을 의미한다.이 연산을 최소 횟수로 수행하여 두 큐의 합을 같게 만들어야 한다.어떤 방법으로도 두 큐의 합을 같게 만들 수 없으면 -1을 반환한다. 접근 방법처음에는 단순히 모든 상태를 BFS로 탐색하는 방법이 떠오른다.하지만 큐의 길이가 최대 300,00이므로, BFS로 모든 상태를 탐색하는 것은 불가능!DP 역시 가능한 큐의 상태를..

https://school.programmers.co.kr/learn/courses/30/lessons/49993#fnref1 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해선행 스킬 순서가 주어질 때, 각 유저의 스킬트리가 순서를 어기지 않는지 판단하여 가능한 스킬트리 개수를 구한다.접근 방법스킬트리 순서를 어기지 않는지만 판단하면 된다. 따라서 각 스킬트리에서 선행 스킬만 추출한 뒤, 주어진 순서의 접두사(prefix)인지 확인한다.코드function solution(skill, skill_trees) { let answer = 0 for (const tree of skill_trees) ..

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해비내림차순(오름차순 또는 같음)으로 정렬된 수열이 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아야 한다.부분 수열의 합이 k.가능한 부분 수열이 여러 개인 경우, 길이가 가장 짧은 수열을 선택.길이까지 같다면 시작 인덱스가 가장 작은 수열을 선택. 접근 방법단순하게 생각하면, 이중 for문으로 모든 구간을 탐색하면 된다.하지만 이 방식의 시간 복잡도는 O(n²)인데, n이 최대 1,000,000까지 가능하므로 시간 초과가 발생한다. 문..

문제 이해가로가 2이고 세로가 n인 직사각형을 2×1 타일로 가득 채우는 방법의 수를 구하는 문제이다.타일은 가로로 두 개, 또는 세로로 한 개씩 놓을 수 있다. 접근 방법처음에는 가능한 모든 타일 배치를 DFS로 탐색하는 방법을 시도할 수 있다.하지만 n이 커질수록 경우의 수가 급격히 증가하므로, DFS는 O(2ⁿ) 수준의 시간 복잡도를 가진다.이 방식은 n이 수십만 단위일 때 절대 수행될 수 없다. 따라서 가로 길이 n인 타일을 놓을 수 있는 방법은가로 길이 n-1(마지막에 세로 한 개)인 타일 방법 + 가로 길이 n-2(마지막에 가로 두 개) 라는 점,→ 즉 동적 계획법(DP)을 통해 해결해야 한다!f(n) = f(n−1) + f(n−2)피보나치 수열과 동일한 형태! 풀이 1. DP 배열 이용가장 ..

https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해자연수 x를 y로 변환하는 최소 연산 횟수를 구하는 문제. 아래 세 연산이 가능하다.x에 n을 더하기x에 2를 곱하기x에 3을 곱하기x를 y로 만들 수 없다면 -1을 반환해야 한다. 접근 방법변환 횟수를 최소화 → 노골적인 BFS!BFS는 가까운 노드부터 탐색하기 때문에, 특정 수를 처음 방문했을 때가 그 수에 도달하는 최소 연산 횟수이다. 즉 아래와 같은 흐름으로 코드를 작성하면 되겠다.시작점 x에서 BFS 탐색가능한 연산 결과(+n, *2,..

https://school.programmers.co.kr/learn/courses/30/lessons/131704# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해컨베이어 벨트에는 1번부터 n번까지 상자가 순서대로 놓여 있고, 제시된 순서대로 트럭에 상자를 실어야 한다.만약 원하는 순서가 아니면, 상자를 스택 구조의 보조 컨베이어에 임시로 보관한다.트럭에 실을 수 없는 상황이 오면 작업을 종료한다.접근 방법메인 컨베이어에서 상자를 순서대로 확인한다.현재 트럭이 원하는 상자라면 즉시 싣는다.아니라면 보조 컨베이어에 push한다.상자를 하나 처리할 때마다 보조 컨베이어의 top이 트럭이 원하는 상자인지 확..

https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 이해땅따먹기 게임의 땅은 N행 × 4열의 형태로 주어진다.각 칸에는 점수가 적혀 있으며, 위에서부터 한 행씩 내려오면서 한 칸씩 밟아야 한다.조건은 다음과 같다.같은 열은 연속해서 밟을 수 없다.마지막 행까지 도착했을 때의 최대 점수를 구한다.제한 조건은 다음과 같다.N ≤ 100,000각 점수는 100 이하 자연수 접근 방법처음에는 DFS로 모든 경로를 탐색하는 방식이 떠올랐다. (실제 DFS로 구현해도 입출력 예시는 통과한다)그러나 경로 수는 매..