게으른개발너D

✨ 동적 계획법 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 Greedy나 Back tracking처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. Dynamic Programming(DP)라고도 부른다. 동적 계획법이 어렵게 느껴지는 원인 중 하나 Dynamic하지 않고 Programming과도 관련이 없다. 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다. 두 가지 방법론이 있다. 메모이제이션 (Memoization) 타뷸레이션 (Tabulation) ✨ 메모이제이션 (Menoization) 하향식 접근법 (작은 문제들의 결과를 저장해 뒀다가 필요할 때 꺼내 쓰는 방법) 동적 계획법에서 작은 문제들의 결과는 항상 같다. 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 ..

✨ 백트래킹 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기 (Pruning)이라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색해서 순환 (Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. BFS, DFS 모든 경우의 수를 찾을 때도 사용한다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 결정한다. ✨ 백트래킹 로직 작성하는 방법 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하..

https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. Q Q Q Q Q Q Q Q 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는..

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모..

✨ 투포인터 알고리즘 일차원 배열에 인덱스를 가리키는 두 개의 포인터(변수)를 두고 조작하는 알고리즘 (이 인덱스를 가리키는 변수를 포인터라고 부름) 보통 연속적인 구간에 대한 계산을 할 때 많이 사용한다. 예시) 다음 배열에서 합이 10인 수열의 수는? 처음에는 포인터 두개가 전부 첫 인덱스를 가리킨다. 이때는 아직 구간에 대한 합(partialSum)이 7이고 구간 합이 10인 경우는 하나도 찾지 못한 상태이다. count = 0 partialSum = 7 p1 = 0 p2 = 0 아직 구간 합이 10을 넘지 못했기 때문에 두번째 포인터를 증가시키고 해당 index에 대한 값을 구간 합 변수에 더해준다. 따라서 partialSum 변수는 8이 된다. count = 0 partialSum = 8 p1 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한 ..

해당 그래프를 최소한의 비용으로 모든 정점을 연결하려면? 필요한 간선 외에는 모두 제거하면 된다. 이러한 알고리즘을 최소 신장 트리라고 한다. ✨ 최소 신장 트리 (Minimum Spanning Tree) 신장 트리 (Spanning tree)란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프이다. 여기서 최소 신장 트리 (MST)는 다음과 같은 조건을 만족한다. 최소한의 간선으로 모든 정점이 연결되어야 한다. 모든 신장 트리 중 가중치의 값이 최소여야 한다. Cycle이 발생해서는 안된다. 최소 신장 트리를 위한 알고리즘은 대표적으로 두 가지가 있다. 크루스칼 (Kruskal) 프림 (Prim) 미리 알아두면 좋은 크루스칼 알고리즘 그리디 개념을 이용하여 구현할 수 있다. 먼저 모든 그래프를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N 개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N 까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받..