전체 글

그리디 (Greedy) 알고리즘이란?그리디(Greedy)는 사전적으로 '탐욕적인'이라는 뜻이다.그리디 알고리즘은 말 그대로 탐욕적인 알고리즘이다.  그리디 알고리즘은 현재 상황에서 가장 최적의 해를 선택을 하며 선택을 번복하지 않는다.이러한 특성을 가지고 지역 최적해를 추구한다고 이야기 하기도 한다.이렇게 선택을 반복해 하나의 문제를 푸는 알고리즘이다. 하지만 그리디 알고리즘을 모든 상황에서 적용가능한 것은 아니다. 현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.  그렇다면 해당 문제가 그리디 알고리즘으로 해결이 가능한지 어떻게 알 수 있을까?그리디 알고리즘으로 문제를 해결하기 위해선 다음의 두 가지 조건을 만족해야한다.1. 최적 부분 구조: 부분해를 구하는 과정이 최적..

동적 계획법(Dynamic Programming)이란?동적 계획법이란 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고 이를 활용하여 전체 문제를 해결하는 방법이다.하지만 동적 계획법은 작은 부분 문제들을 통해 전체 문제를 해결한다고 해도 반드시 효율적인 것은 아니다.동적 계획법을 효율적으로 사용하기 위해선 다음의 두 가지 조건을 만족해야 한다.1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복적으로 등장해야 한다.2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구할 수 있어야 한다. 어떠한 문제를 다음과 같이 작은 문제로 나누었다고 해보자.A, B, C, D의 작은 문제로 하나의 전체 문제를 푼다고 했을 때, 이 경우는 동일한 작은 문제가 반복적으로 등장하지 않..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 풀이 과정1. 배터리를 사용하지 않고 현재위치* 2의 위치로 순간 이동2. 배터리를 K만큼 소모하고 K칸만큼 이동이 두 가지 기능이 있는 슈트을 가지고 N만큼 이동한다고 했을 때, 배터리 소모량의 최솟값을 구하는 문제이다. 일단 배터리를 소모하면 안 좋기 때문에 최대한 1번 방식으로 이동하는 것이 좋다. 따라서 1번방식으로 현재위치에서 될 수 있으면 곱하기 2를 하고 어쩔 수 없는 경우엔 2번방식으로 배터리를 1소모하고 1만큼 움직여서 N을 만들어야 한다.하지만 앞으로 이동하는 입장에선 그 어쩔 수..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 풀이 과정카펫의 형태가 위와 같이 중앙에는 노란색, 테두리 1줄은 갈색이 칠해져 있다고 할 때,  갈색과 노란색 타일의 갯수를 통해 카펫의 가로, 세로의 길이를 구하는 문제이다. 일단 나는 노란색 타일의 집중을 했다.왜냐하면 노란색 타일의 모양에 따라 필요한 갈색타일의 갯수가 달라지기 때문이다.예를 들어, 노란색 타일이 4개 있다고 하면, 노란색 타일의 모양은 1 X 4의 형태도 되고 2 X 2도 가능하다. 이때, 카펫을 만들기 위해 필요한 갈색 타일의 갯수는 서로 다르다.1 X 4의 경우 갈색은 ..