swea 1244 [S/W 문제해결 응용] 2일차 - 최대 상금 사용언어 : PYTHON 풀이 구현을 위한 생각 백트래킹을 사용하여 모든 경우를 중복없이 탐색한다. 모든 경우를 탐색하며 goal(주어진 숫자를 내림차순으로 정렬한 값)과 차이가 가장 작은 값이 정답이다. 💡 goal : 이동횟수 제한이 없다고 할 때, 숫자를 swap해서 도달할 수 있는 최대값은 내림차순으로 정렬한 값이다. 백트래킹 숫자카드 1,2,3,4가 있다고 할 때 두 번 교환할 수 있는 모든 경우는 위 그림과 같다. (x표시는 중복되는 경우) 바로 직전에 교환한 경우보다 뒤의 경우만 조회하면 중복없이 교환할 수 있다. 바로 직전에 교환한 경우를 기억하기 위해서 stack을 활용하였다. 코드 def backTracking(m): gl..
백준 (BOJ) 14500 https://www.acmicpc.net/problem/14500 사용언어 : PYTHON 1.문제 2.풀이 브루트포스 알고리즘을 사용하는 문제이다. ( 다른 풀이를 추가하였습니다) 시간제한은 2초인데 1억=1초의 룰에 대입했을때 2천8백만이 나오므로 브루트포스 알고리즘을 사용해도 된다. 499*499*19*6 = 28,386,114 회전 또는 대칭으로 만들 수 있는 모든 테트로미노를 1과 0의 배열로 만든다. 19개의 테트로미노들을 돌아가며 종이의 모든 배치 가능한 구역에 배치한다. 그리고 모든 배치중에서 최댓값을 찾는다. 이 문제를 통해서 연산이 복잡해 질 때는 함수를 사용하여 복잡한 연산들을 분할하면 좀 더 쉽게 구현할 수 있음을 알게되었다. 3.코드 import sys..
백준 (BOJ) 1107 https://www.acmicpc.net/problem/1107 사용언어 : PYTHON 1.문제 2.풀이 2-1. 시도했다가 실패한 풀이 N : 5457 M : 3 고장난 버튼 : [5,7] 이면 입력이 가능한 버튼들은 [0,1,2,3,4,5,6,8,9]이다. 5457의 첫 번째 숫자 5가 없으므로 첫 번째 숫자를 4 혹은 6을 입력하는 것이 최소로 이동할 수 있는 수가 될 것이다. 이 때 4를 입력한 경우는 뒤에 숫자를 최대한 큰 수로 입력해야 하고, 6을 입력한 경우는 최대한 작은수를 입력해야 한다고 생각하여 문제를 풀고자 했다. 2-2. 올바른 풀이 브루트포스 알고리즘 0 ~ 999899+1 까지 리모컨으로 입력할 수 있는 모든 숫자들을 비교하며 최솟값을 찾는다. N의 ..
백준 (BOJ) 11053번 https://www.acmicpc.net/problem/11053 사용언어 : PYTHON 1.문제 2.풀이 A={10,20,10,30,20,50}을 예로 들어 생각해보았다. dp[i] = A[0], A[1], ... A[i] 일때 '증가하는 부분 수열'에서 A[i]의 위치(인덱스)값 이다. i=0 일 때 dp[0]는 A[0] 즉 10의 '증가하는 부분 수열'={10} 에서 위치 즉 1 이다. i=1 일 때 dp[1]는 A[1] 즉 20의 '증가하는 부분 수열'={10,20} 에서 위치 즉 2 이다. i=2 일 때 dp[2]는 A[2] 즉 10의 '증가하는 부분 수열'={10,20} 에서 위치 즉 1 이다. i=3 일..
백준 (BOJ) 11052번 https://www.acmicpc.net/problem/11052 사용언어 : PYTHON 1.문제 2.풀이 최적해(최댓값)을 구하는 문제이므로 다이나믹 프로그래밍을 사용하여 풀 수 있었다. 최적해의 일부분이 그 부분에 대한 최적해가 DP 순환식을 세우는 출발점임을 생각했다. N이 4이고 P1=1, P2=5, P3=6, P4=7인 경우 최댓값 = max(P4를 선택하지 않은 경우, P4를 선택한 경우)이다. 이때 P4를 선택하면 N의 갯수를 모두 채우기 때문에 P4하나만 살 수 있다. 따라서 max{(P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값, 7}이 된다. 위 최적해의 일부분 (P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값 = (P3를 ..
백준 (BOJ) 1463번 https://www.acmicpc.net/problem/1463 사용언어 : PYTHON 1.문제 2.풀이 다이나믹 프로그래밍 (Bottom up) 방식으로 풀어야 했다. 2-1.순환식을 세우기 순환식을 세우는 사고의 출발점은 '최적해의 일부분이 그 부분에 대한 최적해인가?' 라고 배웠다. 정수 N을 1로 만드는 최소 횟수를 구하는 함수를 D(N)이라고 하자. 최적해를 생각해보면 다음과 같다. D(10)은 10을 2로 나눈 D(5)와, 10에서 1을 뺀 D(9)중 더 작은 값 + 2로 나누거나 1을 뺀 연산횟수 1과 같다. D(12)는 12를 3으로 나눈 D(4)와, 12를 2로 나눈 D(5), 12에서 1을 뺀 D(11) 중 더 작은값 + 연산의 횟수 1과 같..
백준 (BOJ) 6588번 https://www.acmicpc.net/problem/6588 사용언어 : PYTHON 1.문제 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다...
백준 (BOJ) 17298번 https://www.acmicpc.net/problem/17298 사용언어 : PYTHON 1.문제 2.풀이 시간제한이 1초이기 때문에 중첩 반복문으로 풀게되면 시간초과가 나올것 같아서 스택을 사용하여 풀어야겠다고 생각했다. 처음에는 큰 수에 생각이 사로 잡혀서 스택에 가장 큰 값을 유지하면 안될까? 라는 생각을 계속하였다. 1시간 정도 고민해보다 도저히 안될것 같아서 다른분들의 풀이를 검색하였다. 검색을 통해 알게된 아이디어는 다음과 같다. 스택에 수열의 가장 큰 값을 유지하는 것이 아닌, 스택의 제일 윗 값보다 큰 값이 나올때 까지 수열의 값들을 차례대로 쌓는 것이었다. 그러다가 스택의 제일 위의 값보다 큰 수열의 값이 나오면 그 수는 스택 제일 윗 값의 오큰수가 된다...
