분할 정복 분할 정복은 그대로 해결하기 어려운 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀적으로 구한다. 그 후, 부분 문제의 답을 이용해 전체 문제의 답을 계산해낸다. 재귀 호출과 다른 점은 문제를 한조각과 나머지 전체로 나누는 대신, 거의 같은 크기의 부분 문제로 나눈다는 것이다. 분할 정복이 필요한 문제의 예시로, 거듭 제곱을 구하는 알고리즘을 구현하면 다음과 같다. def pow(a, b): res = 1 for i in range(b): res *= a return res 단순 반복 연산으로 시간복잡도가 O(b)인 풀이이다. 분할 정복을 통해 더 빠르게 해결할 수 있다. a, b, c = map(int, input()..
https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 Problem 2x1 크기의 로봇이 좌표 (1, 1)에서 (N, N)까지 최소 비용으로 이동시킨다. 이동 조건은 다음과 같다. 1. 로봇은 앞 뒤 구분없이 움직일 수 있으며, 4방향으로 1칸씩 평행 이동이 가능하다. 한 칸 이동에 1초가 소요된다. 2. 4방향으로 90도 회전이 가능하며, 회전 방향에 벽이 없어야한다. 한번 회전에 1초가 소요된다. 💡 Solution 로봇의 현재 상태를 que..
https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 📍 Problem 단어 begin 에서 target으로 변환하는 가장 짧은 순서를 찾는다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있으며 2. 주어진 words에 있는 단어로만 변환할 수 있다. ex. begin target words 최소 변환 과정 return "hit" "cog" ["hot", "dot", "do..
https://programmers.co.kr/learn/courses/30/lessons/72412 총 2**4 = 16개의 조건에 만족될 수 있다. 이 때, 만들어진 쿼리에 X 점수의 지원자가 한명 존재한다는 의미로 쿼리에 해당 지원자의 점수를 저장한다. 따라서 지원자는 총 16가지 key에 점수가 저장된다. (key 구성은 조건을 구별할 수 있도록 구성하면 된다.) -> ex. combination_dict["java backend junior pizza"] = [150] 그리고 쿼리가 들어오면, combination_dict에서 쿼리에 해당하는 조건을 찾아서 점수를 만족하면 count 해주면 된다. from collections import defaultdict def solution(info, ..
