Yepchani's place

문제2023 카카오 블라인드 채용 - 미로 탈출 명령어https://school.programmers.co.kr/learn/courses/30/lessons/15036  풀이설명미로를 탈출하기 위한 경로를 구하는 문제입니다. 유의해야 할 점은 모든 노드가 재방문 가능하며, 탈출 경로의 길이가 k여야 하고, 가능한 탈출 경로가 여러 개일 경우 사전 순으로 빠른 경로를 택해야 합니다. 스택을 사용한 dfs를 통해 해결할 수 있습니다.사전 순으로 방문하려면 d, l, r, u 순으로 방문해야 하므로, 스택에는 역순으로 넣어주면 됩니다. 예시 코드function solution(n, m, x, y, r, c, k) { const IMPOSSIBLE = "impossible"; // 목표 지점까지의 거리와 k..

문제2021 카카오 블라인드 채용 - 광고 삽입https://school.programmers.co.kr/learn/courses/30/lessons/72414  풀이설명누적 재생시간이 가장 많은 구간에 광고를 삽입하려 할 때, 광고 시작 시각을 구하는 문제입니다. 구간 별 시청자 수의 누적합을 구한 후, 슬라이딩 윈도우 기법을 통해 누적 재생시간이 가장 많은 구간을 구할 수 있습니다. 예시 코드function solution(play_time, adv_time, logs) { const playSeconds = HMSToSeconds(play_time); const advSeconds = HMSToSeconds(adv_time); const viewerCountPerSegment = Array(p..

문제PCCP 기출문제 3번 - 충돌위험 찾기https://school.programmers.co.kr/learn/courses/30/lessons/340211  풀이설명경로를 설정한 대로 로봇이 움직일 때, 충돌이 일어날 수 있는 위험 상황이 몇 번 일어나는지를 구하는 문제입니다. 같은 시간, 같은 위치에 두 대 이상의 로봇이 있을 때, 충돌할 가능성이 있는 위험 상황으로 판단합니다.그래서 Map을 생성해, 시간과 위치 정보를 바탕으로 키를 만들어, 해당 키를 생성하는 로봇의 개수를 카운트했습니다. 유의할 점은 로봇은 한 번에 수직 또는 수평으로 한 칸밖에 움직일 수 없고, 수직으로 먼저 이동 후 수평으로 이동해야 한다는 점입니다. 예시 코드function solution(points, routes) {..

문제입국심사https://school.programmers.co.kr/learn/courses/30/lessons/43238  풀이설명모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 구하는 문제입니다. 이분탐색으로 해결할 수 있습니다.시간을 정하고 해당 시간 안에 정해진 사람 수를 처리할 수 있는지 확인합니다. 예시 코드function solution(n, times) { times.sort((a, b) => a - b); let left = 1, right = times[0] * n, minTime = 0; while (left

문제2018 카카오 블라인드 채용 - [3차] 자동완성https://school.programmers.co.kr/learn/courses/30/lessons/17685  풀이설명학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지를 구하는 문제입니다. 각 단어를 찾는 데 필요한 접두사의 길이를 구하면 됩니다. 접두사 관리가 핵심이므로 Trie 구조를 사용해 해결할 수 있습니다.트라이(Trie) - 효율적인 문자열 검색을 위한 자료구조 예시 코드class TrieNode { #prefixCount; #children; constructor() { this.#prefixCount = 0; this.#children = {}; } increasePrefixCount() { ..

문제PCCP 기출문제 1번 - 동영상 재생기https://school.programmers.co.kr/learn/courses/30/lessons/340213  풀이설명입력이 모두 끝난 후 동영상의 위치를 "MM:SS" 형식으로 구하는 문제입니다. 시간의 형식을 맞춰 변환하는 게 중요합니다. 예시 코드function solution(video_len, pos, op_start, op_end, commands) { const PREV = "prev"; const NEXT = "next"; const SECONDS_TO_PREV = 10; const SECONDS_TO_NEXT = 10; const VIDEO_START_TIME = 0; video_len = convertToSeconds(vide..

문제2022 카카오 블라인드 채용 - 양과 늑대https://school.programmers.co.kr/learn/courses/30/lessons/92343  풀이설명노드를 방문하며 모을 수 있는 양의 최대 수를 구하는 문제입니다. 늑대의 수가 양의 수와 같거나 더 많아지면 양들이 잡아먹히기 때문에 방문 순서에 따라 결과가 달라집니다.해당 경우를 제외한 가능한 모든 경우를 탐색하기 위해 백트래킹을 사용했습니다. 여기서 주의할 점은, 모든 노드가 양으로 이루어진 이진트리의 경우, 일반적인 완전탐색을 하게 된다면 시간을 어마어마하게 잡아먹게 됩니다.이 문제를 해결하기 위해 인접한 양들을 모아 그룹화를 진행하고, 그룹 트리를 만들어 시간을 단축할 수 있습니다. 아래와 같은 트리가 있습니다. 이를 그룹화한다..

문제조이스틱https://school.programmers.co.kr/learn/courses/30/lessons/42860  풀이설명조이스틱 조작 횟수의 최솟값을 구하는 문제입니다. 조작 횟수는 수직 이동 횟수 + 수평 이동 횟수입니다. 수직 이동 횟수는 문자열을 순회하며 각 문자가 기본 문자와 얼마나 차이나는지를 구하면 됩니다. 신경써야 할 부분은 수평 이동 횟수인데요.수평으로 이동하는 시나리오는 총 두 가지입니다.한 쪽 방향으로 쭉 이동할 경우한 쪽 방향으로 이동하다가 특정 지점에서 반대쪽 방향으로 이동할 경우 2번을 고려하기 위해서, 기본 문자인 A가 아니면서 가까운 두 문자의 인덱스 i와 j를 찾아 첫 문자에서 i까지 오른쪽으로 이동한 횟수와 j까지 왼쪽으로 이동한 횟수를 구해야 합니다.둘 중 ..

문제숫자 블록https://school.programmers.co.kr/learn/courses/30/lessons/12923  풀이설명구간에 깔려 있는 블록들의 숫자를 구하는 문제입니다. 블록 숫자 n값을 1부터 마지막 값까지 증가시키면서 구간 내 위치에 설치합니다.n이 쓰여진 블록은 n * 2, n * 3, n * 4 번째 위치에 설치됩니다.  다음 두 가지 값을 적절하게 선택하는 게 중요합니다.n의 최댓값n이 쓰여진 첫 번째 블록 인덱스 문제에서 제시한 n의 최댓값은 10,000,000이므로, 마지막 블록 인덱스를 2로 나눈 값과 비교해 더 작은 값을 선택합니다.n이 쓰여진 첫 번째 블록 인덱스는 begin 이상이면서 n의 배수 중 최솟값을 선택합니다. 예시 코드function solution(be..

문제2018 카카오 블라인드 채용 - [3차] 압축https://school.programmers.co.kr/learn/courses/30/lessons/17684  풀이설명주어진 문자열을 압축한 후의 사전 색인 번호를 구하는 문제입니다. 압축 알고리즘은 LZW를 사용합니다. 압축 방법은 다음과 같습니다.길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다. 단계 2로 돌아간다. 투 포인터를 사용해 가장 긴 문자열을 관리합니다. 예시 코드function solution(msg) {..