분할 정복 분할 정복은 그대로 해결하기 어려운 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀적으로 구한다. 그 후, 부분 문제의 답을 이용해 전체 문제의 답을 계산해낸다. 재귀 호출과 다른 점은 문제를 한조각과 나머지 전체로 나누는 대신, 거의 같은 크기의 부분 문제로 나눈다는 것이다. 분할 정복이 필요한 문제의 예시로, 거듭 제곱을 구하는 알고리즘을 구현하면 다음과 같다. 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/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 Problem 4x4 크기의 보드에, 짝이 있는 카드가 주어진다. 카드를 선택해 뒤집고 짝 카드를 찾아 뒤집으면 해당 카드들이 사라진다. 카드는 커서를 이용해 선택할 수 있으며, 키를 조작해 커서를 이동시킬 수 있다. 모든 카드를 화면에서 사라지게 하는 최소 키 조작 횟수를 구한다. 커서는 [Ctrl] 키와 방향키에 의해 이동된다. - 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른..
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/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 📍 Problem 벽이 존재하는 NxN 크기의 부지에 벽을 피해 (0, 0) 칸 부터 ..
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..
