FrontEnd/프로그래머스

    [JS] 행렬과 연산
    FrontEnd/프로그래머스

    [JS] 행렬과 연산

    Deque를 활용하여 해결하였다.  https://school.programmers.co.kr/learn/courses/30/lessons/118670 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 자체는 단순했다. 행렬을 밑으로 밀어내거나 시계방향으로 회전하는 기능을 구현하면 되었다.단, 시간복잡도를 생각해야 하는 문제이다. 행렬을 밑으로 밀어내는 것 자체는 어렵지 않다. Deque로 쉽게 구현할 수 있다. 시계방향으로 회전하는 기능또한 Deque로 구현할 수 있다. 이 두가지를 동시에 할 수 있게 하기 위해 Deque를 아래와 같이 조금은 특이하게..

    [JS] 매출하락 최소화 (2021 카카오)
    FrontEnd/프로그래머스

    [JS] 매출하락 최소화 (2021 카카오)

    tree + dp로 해결할 수 있는 문제였다.  https://school.programmers.co.kr/learn/courses/30/lessons/72416 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   트리구조와 DP를 활용하면 해결할 수 있는 문제이다. 문제를 처음 읽었을때의 생각은 선택을 했거나, 안했거나를 나누어서 계산을 하는 거였다.(결과적으로 완전 틀린 접근은 아니었음) 다만 완전탐색으로 이를 해결하기에는 300,000명까지 사원이 있기에 불가능 했다. 주의를 둘 점은 트리구조이기 때문에 1번노드에서 단방향으로 퍼져나가는 구조라고 생각할 ..

    FrontEnd/프로그래머스

    [JS] 사칙연산

    까다로운 DP문제였다.  https://school.programmers.co.kr/learn/courses/30/lessons/1843# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  이전부터 느낀거지만 이런 유형의 DP가 정말 까다로운 것 같다.  문제에서 제공한 1번예제를 분석해보면서 풀이를 생각해보자. ["1", "-", "3", "+", "5", "-", "8"] 먼저 i,j를 왼쪽부터의 인덱스라고 생각해보자. 예를들어 i : 0, j : 1 이라면 1-3까지를 나타낸다고 생각해보자. 그리고 i와 j의 차를 step이라고 생각해보자. ij수0011..

    [JS] 지형 이동
    FrontEnd/프로그래머스

    [JS] 지형 이동

    union-find를 응용해서 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 어느정도 문제에서 힌트(?)가 있다. 아래와 같이 일종의 팀을 짜는 것이 중요하다. 즉, 서로 건너건너서 사다리 없이 갈 수 있는 공간을 한 팀이라고 생각했다. 이런경우 바로 떠오르는 방법이 유니온-파인드 알고리즘이었다. 따라서 문제푸는 방법자체는 아래와 같이 간단하게 정리되었다. 1. 유니온-파인드로 팀분리하기 2. 팀에서 다른팀으로 넘어가는 최소..

    FrontEnd/프로그래머스

    [JS] 트리 트리오 중간값

    트리 구조의 특징을 활용하여 해결하였다!! https://school.programmers.co.kr/learn/courses/30/lessons/68937 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 잘 읽어보면 정답이 "트리에서의 최장거리" 혹은 "트리에서의 최장거리 - 1"임을 알 수 있다. 1. 최장 거리의 두 점을 A,B라고 두고 A와 B사이에서 A혹은 B와 가장 인접한 점을 C로 두면 중간값이 최장거리 -1이 된다. 2. 최장거리가 여러 경우로 나오는 경우 3개의 점이 서로 최장거리가 되므로 중간값이 최장거리로 만들 수 있다. 즉, 해..

    [JS] 지형편집
    FrontEnd/프로그래머스

    [JS] 지형편집

    이분탐색을 응용한 방식으로 해결하였다! https://school.programmers.co.kr/learn/courses/30/lessons/12984 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한사항을 처음 읽고 든 생각은 이분탐색이었다. 모든 층을 검사하는건 10억이라는 수치상 말이 안되었기 때문이다. 이분탐색을 사용하려면 정렬된 데이터가 필요했다. 층수 자체는 정렬된 데이터긴 하지만 우리가 원하는 건 최소 비용이다. 이는 정렬되어 있지 않다. 여기서 아래 특징들을 짚고 넘어가면 좋을 것 같다. 1. 특정층 n에 도달하기 위한 비용을 계산할때는..

티스토리툴바