Yepchani's place

문제삼각 달팽이https://school.programmers.co.kr/learn/courses/30/lessons/68645   풀이설명규칙대로 배열을 채운 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 구하는 문제입니다. 높이가 n인 삼각형 배열의 마지막 원소는 (n * (n + 1) / 2) 입니다.첫 인덱스부터 시작해 아래, 오른쪽, 위 순서대로 방향을 진행하며 삼각형 배열을 채우면 됩니다.삼각형 배열은 1차원 배열로 표현할 수 있습니다.이 때, 각 행의 첫 번째 인덱스는 (x * (x + 1) / 2)입니다. 여기에 y를 더하면 x행의 y열입니다.즉, (x, y) 원소의 위치는 (x * (x + 1)) / 2 + y 입니다. 예시 코드function solution(n) { ..

문제마법의 엘리베이터https://school.programmers.co.kr/learn/courses/30/lessons/148653  풀이설명0층으로 가기 위해 필요한 마법의 돌의 최솟값을 구하는 문제입니다. 엘리베이터는 현재 층에서 절댓값이 10 ^ c (c >= 0인 정수) 형태인 정수만큼 위아래로 갈 수 있습니다.따라서 현재 층의 가장 마지막 자릿수부터 0 또는 10으로 만들어 나가면 최솟값을 구할 수 있습니다.6층의 경우, 0층으로 가기 위해서는 -1을 6번 누르거나, +1을 4번 누르고 -10을 1번 누를 수 있습니다. 따라서 10을 거쳐가는 게 빠릅니다. 마지막 자릿수에 따라 다음과 같이 움직입니다5보다 작은 경우, 0으로 갑니다.5보다 큰 경우, 10으로 갑니다.5인 경우, 다음 자릿수에..

문제가장 긴 팰린드롬https://school.programmers.co.kr/learn/courses/30/lessons/12904  풀이설명문자열 s의 부분문자열 중 가장 긴 팰린드롬의 길이를 구하는 문제입니다. 홀수 길이 팰린드롬  또는 짝수 길이 팰린드롬이 있을 수 있습니다.팰린드롬은 특정 인덱스를 중심으로 해서 좌우로 퍼져나가며 구할 수 있습니다.문자열을 순회하면서 각 인덱스에서 만들 수 있는 가장 긴 팰린드롬의 길이를 구해 최대 길이를 비교합니다. 예시 코드function solution(s) { let maxLength = 1; for (let i = 0; i = 0 && right

문제2개 이하로 다른 비트https://school.programmers.co.kr/learn/courses/30/lessons/77885  풀이설명양의 정수들로 이루어진 배열이 있을 때, 각 숫자마다 자신보다 크고 자신과 비트가 2개 이하로 다른 수들 중 제일 작은 수를 배열에 담아 구하는 문제입니다. 조건을 만족하는 수는 다음과 같이 구할 수 있습니다.짝수의 경우, 이진수가 항상 0으로 끝나므로, 1을 더하면 됩니다.홀수의 경우, 가장 마지막에 위치한 '01'을 '10'으로 바꾸면 됩니다. 1로만 이루어질 수 있으므로, 이진 문자열 앞에 0을 붙인 후 수행합니다. 예시 코드function solution(numbers) { return numbers.map((x) => { if (x % 2 =..

문제N-Queenhttps://school.programmers.co.kr/learn/courses/30/lessons/12952  풀이설명n개의 퀸을 조건에 만족시키며 배치할 수 있는 방법의 수를 구하는 문제입니다. 백트래킹을 통해 해결할 수 있습니다. 각 (행, 열)에 퀸이 배치될 수 있는지를 확인하고, 가능하면 다음 퀸으로 넘어갑니다.모든 퀸이 배치 가능하면 카운트를 증가시킵니다. 예시 코드function solution(n) { const board = Array(n).fill(0); let answer = 0; function canPlace(row, col) { for (let i = 0; i

문제과제 진행하기https://school.programmers.co.kr/learn/courses/30/lessons/176962  풀이설명과제를 끝낸 순서대로 이름을 구하는 문제입니다. 과제를 시작 시간 순서로 정렬합니다.각 과제에 대해서 다음 작업들을 반복합니다.현재 시간이 다음 과제 시작 시간보다 작을 경우스택에서 최근 과제를 꺼내 다음 과제까지 남은 시간내에 해결할 수 있는지 판단합니다.해결 가능할 경우, 완료 목록에 추가하고 현재 시간을 (현재 시간 + 남은 과제 시간)으로 업데이트 합니다.불가능할 경우, 해당 과제를 다시 스택에 추가하고 현재 시간을 다음 과제의 시작 시간으로 업데이트합니다.스택에 과제를 추가하고, 현재 시간을 해당 과제의 시작 시간으로 업데이트합니다. 예시 코드functio..

문제카운트 다운https://school.programmers.co.kr/learn/courses/30/lessons/131129  풀이설명목표 점수가 주어졌을 때, 최선의 경우 던질 다트 수와 그때의 싱글 또는 불을 맞춘 횟수를 구하는 문제입니다. DP로 해결할 수 있습니다. 최선의 경우란, 던질 다트 수를 최소화하고, 다트 수가 같을 경우, 싱글 또는 불을 맞춘 횟수를 최대화한 경우를 말합니다. 다트 하나를 던져서 획득할 수 있는 스코어는 다음과 같습니다.1 ~ 20(1 ~ 20) * 2(1 ~ 20) * 350 dp[i]는 i점을 만들기 위해 필요한 [다트 수, 싱글 또는 불을 맞춘 횟수]입니다.i점은 (i - 스코어)점에 다트 한 개를 추가로 던져 구할 수 있습니다.가능한 스코어를 전부 시도해 보..

문제110 옮기기https://school.programmers.co.kr/learn/courses/30/lessons/77886  풀이설명변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 구하는 문제입니다. 먼저 문자열 내에 존재하는 모든 110을 없애고, 카운트를 증가시킵니다.110을 제거하고 남은 문자열에 대해서도 같은 작업을 반복합니다. 문자열을 넣을 위치를 정해야 합니다.우선순위는 다음과 같습니다.111 바로 앞마지막 0 바로 뒤첫 번째마지막으로 110을 카운트만큼 반복한 문자열을 해당 위치에 넣어서 만든 문자열을 반환하면 됩니다. 예시 코드function solution(s) { return s.map(processBinaryString);}function process..

문제N으로 표현https://school.programmers.co.kr/learn/courses/30/lessons/42895  풀이설명N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 구하는 문제입니다. dp를 사용해 해결할 수 있습니다. dp[i]는 N을 i번 사용해서 만들 수 있는 수들의 모음입니다.N을 i번 사용해서 만든 수, dp[j]와 dp[i - j]의 조합으로 생성될 수 있습니다. (1  점화식은 다음과 같습니다. 예시 코드function solution(N, number) { const MAX_N_LIMIT = 8; const dp = Array.from({ length: MAX_N_LIMIT + 1 }, () => new Set()); for (let i ..

문제3 x n 타일링https://school.programmers.co.kr/learn/courses/30/lessons/12902  풀이설명길이가 n인 직사각형을 채우는 방법의 수를 구하는 문제입니다. DP를 이용해 해결할 수 있습니다.dp[n]은 길이가 n인 직사각형을 채우는 방법의 수입니다. 직사각형의 길이가 짝수일 때, 각 길이에 맞는 전용 블록을 만들 수 있습니다. 만들 수 있는 전용 블록의 종류는 다음과 같습니다.n = 2일 때, 3가지n = 4 이상의 짝수일 때, 2가지 아래는 그 예시입니다. 따라서 dp[n] = dp[n - 2]에 길이가 2인 전용 블록을 채우는 가짓수 + dp[n - x]에 길이가 x인 전용 블록을 채우는 가짓수입니다. (x는 4이상의 짝수) 단, dp[0]은 아무것도..