Yepchani's place

문제동물원https://www.acmicpc.net/problem/1309  풀이2 x N 크기의 우리에 사자를 배치하는 경우의 수를 구하는 문제입니다. 규칙은 다음과 같습니다.사자들을 우리에 가둘 때, 가로 또는 세로로 붙어있게 배치할 수는 없습니다.한 마리도 배치하지 않는 경우도 하나의 경우의 수로 칩니다. DP를 이용해 해결할 수 있습니다. dp[i]는 i번째 우리에 [사자가 없을 때, 좌측에 있을 때, 우측에 있을 때] 입니다.dp[1] = [1, 1, 1]로 초기화 해줍니다. 점화식은 다음과 같습니다. i번째 우리에 사자가 없을 때, dp[i][0]은 i - 1번째 우리의 모든 경우의 수를 합친 값입니다.dp[i][0] = dp[i - 1].reduce((acc, cur) => (acc + cu..

문제1, 2, 3 더하기 4https://www.acmicpc.net/problem/15989  풀이설명정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 1, 2, 3의 합으로 나타내는 방법의 수입니다.dp[0] = 1로 초기화 해줍니다. 1, 2, 3을 num으로 나타낸다면dp[i] = dp[i] + dp[i - num]입니다. 예시 코드function solution() { const T = +input(); const n = 10000; const dp = Array(n + 1).fill(0); const answer = []; dp[0] = 1; for (let i = 1; i

문제부대복귀https://school.programmers.co.kr/learn/courses/30/lessons/132266  예시 코드class Queue { constructor() { this.inbox = []; this.outbox = []; } enqueue(data) { this.inbox.push(data); } dequeue() { if (!this.outbox.length) { while (this.inbox.length) { this.outbox.push(this.inbox.pop()); } } return this.outbox.pop(); } size() { return this.inbox.length..

문제다음 큰 숫자https://school.programmers.co.kr/learn/courses/30/lessons/12911  예시 코드def solution(n): x = n # 1. 가장 낮은 '1'비트 찾기 right_one = x & -x # 2. 가장 낮은 '1'비트에 1 더하기 added_one_bit = x + right_one # 3. 변경된 비트 패턴 찾기 modified_pattern = x ^ added_one_bit # 4. 변경된 비트 패턴 조정하기 # 4-1. 오른쪽 끝으로 시프트하기 adjusted_pattern = (modified_pattern) // right_one # 4-2. 오른쪽으로 2비트 시프트하기..

문제2018 카카오 블라인드 채용 - [3차] 파일명 정렬https://school.programmers.co.kr/learn/courses/30/lessons/17686  예시 코드function solution(filenames) { const parsedFilenames = filenames.map(parseFilename); parsedFilenames.sort((a, b) => { if (a.head b.head) return 1; return a.number - b.number; }); return parsedFilenames.map((file) => file.name);}function parseFilename(filename) { const regex = /^([^\d..

문제  14426번: 접두사 찾기문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자www.acmicpc.net 예시 코드class TrieNode { constructor() { this.children = {}; this.isTerminal = false; }}class Trie { constructor() { this.root = new TrieNode(); } insert(key) { let node = this.root; for (let i ..

문제  5582번: 공통 부분 문자열두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들www.acmicpc.net 예시 코드function solution() { const str1 = input(); const str2 = input(); const len1 = str1.length; const len2 = str2.length; const dp = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0)); let maxLen = 0; for (let i = 1; i  풀이두 문자열에서 LCS(Lo..

문제  1700번: 멀티탭 스케줄링기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전www.acmicpc.net 예시 코드function solution() { const [N, K] = input().split(" ").map(Number); const order = input().split(" ").map(Number); const plugs = new Map(); let cnt = 0; for (let i = 0; i max) { max = tmp; idx = k; } } plugs.delete(idx); ..

문제  12904번: A와 B수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수www.acmicpc.net 예시 코드function solution() { const S = input(); let T = input().split(""); while (S.length !== T.length) { if (T.at(-1) === "A") T = T.slice(0, -1); else if (T.at(-1) === "B") T = T.slice(0, -1).reverse(); else break; } return..

문제  2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 예시 코드function solution() { const MOD = 1000000000; const [N, K] = input().split(" ").map(Number); const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0)); dp[0][0] = 1; for (let i = 1; i = 1) dp[j][i] += dp[j - 1][i]; dp[j][i] %= MOD; } } return dp[N][K];} 풀이이 문제는 DP를 이용해 풀 수 있는데요.이해하는 데 필요한 두 가지 포인트를 알아보겠..