Algorithm/문제 풀이7 BOJ백준 3649 로봇프로젝트 풀이(C++) 문제링크 문제는 주어진 블록 중 두개를 골라 주어진 길이의 구멍을 막을 수 있나 알아보는 문제이다.즉, 주어진 값이 있을 때, 그 중에서 주어진 조건을 만족하는 차이가 가장 큰 값이 있는지 탐색하는 문제라고 볼 수 있다. 접근 방법은 다음과 같다. 어떠한 크기의 구멍을 두 블록으로 막는다고 했을 때 두 블록은 '반드시' 하나의 작은 블록과 하나의 큰 블록으로 이루어져 있다.따라서 주어진 블록 값들을 오름차순으로 정렬한 뒤 각각의 끝에서부터 블록을 하나씩 골라 구멍의 값과 비교하고 다음에 따라 원하는 값을 찾을 때까지 반복한다. - 구멍의 크기가 두 블록의 합보다 작은 경우 -> 작은 블록 쪽을 큰 쪽으로 한 칸 옮긴다(인덱스가 i였다면 i+1로 증가시킨다.)- 구멍의 크기보다 두 블록의 합이 큰 경우 -.. 2019. 2. 21. BOJ 백준 6236 용돈관리 풀이(C++) 문제 링크 이 문제는 흔히 최적화 문제라고 부르는 문제로서 특정 상황이 주어졌을 때 그 상황을 만족하는 최솟값, 최댓값 등의 특정 값을 찾는 문제이다.처음에 이 문제의 분류는 분할정복 문제로 되어있는데 도대체 어떤 기준으로 문제를 작게 쪼개어야할지 감이 오지 않아 머리만 싸매고 있던 도중파라메트릭 서치(Parametric Search)라는 접근법이 있다는 것을 알게 되었다. 파라메트릭 서치에 대한 설명은 이 글을 읽으면 어느 정도 감이 올 것이다.이 알고리즘을 사용하면 위의 문제에서 통장에서 인출해야할 최소 금액을 구하는 문제에서 특정 금액을 인출했을 경우 예산대로 돈을 사용할 수 있는가에 대한 문제로 변환하여 풀 수 있다. 예를 들어 위의 예시에서 탐색 범위를 하루 최소 사용 금액인 100원에서 한 번.. 2019. 2. 11. BOJ백준 9019 DSLR 풀이(C++) 문제 링크 이번 문제는 BFS 문제이다.BFS문제는 현재 상태와 다음 상태에 대한 관계를 정의하는 것이 첫 번째라고 볼 수 있다.이번 문제에서는 현재 상태와 다음 상태는 D S L R로 이루어지는 문자열의 길이로 판가름난다.예를 들어 현재 상태가 L 이라면 다음으로 갈 수 있는 상태는 LD, LS, LL, LR 이렇게 네 가지이다.즉 현재가 500이라면 다음 상태는 1000, 499, 5000, (00)50이 되는 것이다. 좀 더 프로그래밍적으로 접근해보자.예를 들어 초기값이 1234이고 3412를 만든다고 해보자.먼저 초기값 1234와 빈 문자열을 c++에서 지원하는 자료형인 pair로 묶어 큐에 넣어준다.그 후 큐(queue)가 빌 때까지 아래와 같이 반복문을 돈다.1. 의 첫번째 데이터를 가져오고 .. 2019. 2. 8. BOJ백준 2293 동전1 풀이(Python) 문제 링크 n가지 종류의 동전을 이용하여 k원을 만드는 경우의 수를 구하는 문제이다.이 문제역시 Dynamic Programming을 이용하여 간단히 해결할 수 있다.개인적으로 DP문제의 핵심은 문제를 어떻게 작은 문제로 나누거나 일반화시킬 것인가이기 때문에이와 같은 관점에서 생각해본문제 풀이의 핵심 전략은 다음과 같다. A-k1원, A-k2원, A-k3원...까지 주어진 동전들로 만드는 경우를 구했다고 했을 때 A원을 만드는 경우는 다음의 경우들을 더해주면 된다. 더 자세히 서술하면 1. n가지 종류의 동전을 반복문으로 순회하면서 내부에서 반복문을 한 차례 더 돌린다.2. 이 때 내부 반복문은 동전의 가치부터 k까지 순회한다.3. 내부 반복문이 j번째를 순회한다고 했을 때 dp[j]에 dp[j-(순회중.. 2019. 2. 8. BOJ백준 1890 점프 풀이(Python) 문제는 위와 같으며 전형적인 DP(Dynamic Programming)문제이다.DP의 의의는 이전에 계산했던 값들을 이번에 구할 값을 계산할 때 응용함에 있으므로 이를 중심으로 생각해보자. 예를 들어 A와 B라는 칸에서 C로 갈 수 있다고 해보자. 그렇다면 칸C까지 갈 수 있는 경우의 수는 칸A와 칸B까지 갈 수 있는 경우의 수의 합이 될 것이다.이를 이용하며 시작점부터 차례대로 게임판을 순회하며 각 칸에서 갈 수 있는 칸에 현재 칸까지 오는 경우의 수를 더해준다. 아래는 소스코드이다.123456789101112131415161718192021222324252627282930import sysN = int(sys.stdin.readline())board = []for i in range(N): temp .. 2019. 2. 6. BOJ백준 1748 수 이어 쓰기1 풀이(C++) 문제는 위와 같이 간단하다.단순히 연속된 수를 옆으로 쭉 나열하면서 N까지 이어썼을 때의 자릿수, 즉 문자열의 길이를 구하면 된다. 간단히 증가하는 자릿수의 규칙을 찾아보자 - 한 자리 수(1 ~ 9)123456789 -> 9자리- 두 자리 수(10 ~ 99)101112...979899 -> 180자리... 보다시피 (각 자리의 길이) * (각 자리 숫자의 개수) 가 해당 자리수까지 전부 더했을 때 증가되는 문자열의 길이임을 알 수 있다.만약 입력으로 받은 N이 네 자리 숫자라면 3자리 숫자까지는 전부 더해지므로 위의 공식대로 증가시키고 입력받은 숫자의 길이인4자리수 부터는 따로 계산해주면 쉽게 답을 구할 수 있을 것이다. 아래는 코드이다.12345678910111213141516171819202122#.. 2019. 2. 6. 이전 1 2 다음
