Algorithm 뽀개기

입력받은 수열을 사용하여 가능한 모든 순열을 생성하고 각 순열에서 인접한 두 숫자의 차이의 절댓값을 더한 값 중 최댓값을 찾는 문제를 해결하고자 했다. 1. 모든 순열 생성 2. 인접한 두 숫자의 차이의 절댓값 더하기 3. 최댓값을 찾기 먼저 새로운 순열을 저장할 배열, 중복을 확인할 배열, 가능한 최댓값을 갱신하기 위한 변수를 설정한다. 가능한 모든 순열을 탐색해야 하기 때문에 백트래킹 (모든 가능한 경우의 수를 탐색하는 알고리즘) 을 사용했다. 방문한 숫자를 되돌리기 위한 visited 배열과 순열을 구성하는 arr 배열을 통해 매번 새로운 순열을 구성한다. base case 인 cur 이 n 이 되었을 때 즉 순열이 완성되면 total 변수를 사용하여 인접한 값들의 차이의 절댓값을 구하고 이를 an..

dp 에 이어 드디어! 브루트포스 문제를 풀게 되다니... 구현/수학 만 하염 없이 풀다가 이렇게 있어 보이는 문제를 풀 땐 마음이 긴장된다.긴장은 둘째 치고... 인생 첫 브루트포스 문제 브론즈 1 임에도 답을 보고 풀다... 브루트포스에 지레 겁 먹어서인지 바보 같은 코드만 짜다가 결국 감을 잡고자 여러 답을 확인해보고 이해하기로 했다. 1. 9 명이라고 제시되어 있다.2. 오름차순으로 출력한다.3. 어떤 7 명인지 찾을 필요는 없다. 핵심은 9 명의 난쟁이 중 2 명을 뺀 후 나머지의 합이 100 이 됨을 확인하는 것이 아니라, 9 명을 모두 합하고 2 명을 빼면 100 이 되는 순간을 확인하는 것이다.  그래서 먼저 list 에 9 명의 키를 모두 담고 flag 를 만든다. flag 는 합이 10..

조건1. 연속된 몇 개의 수일지는 모른다. (한 개 이상 선택)2. 연속된.3. 최대 합을 구해야 한다. 부분합을 구해서 dp 배열에 부분합의 max 값을 갱신해주고 그 dp 배열의 max 값을 구하면 최대 합이 구해진다. d[i-1] + list[i] 는 현재 원소 i 를 포함하는 최댓값의 후보이다. d[i-1] 에 list[i] 를 더한 게 현재 원소 보다 크다면 계속 더해나가는 것이 최댓값이 유지가 되는 것이고 d[i-1] 에 list[i] 더한 게 list[i] 보다 작다면 d[i-1] 는 음수라는 것이고 그러면 list[i] 부터 새롭게 연속합을 시작해야 한다. n = int(input())list = list(map(int,input().split()))dp = [0] * nfor i in r..

11053 가장 긴 증가하는 부분 수열을 제법 내 힘으로 풀고 자신감이 생겨서 연계된 문제인 가장 긴 증가하는 부분 수열 4 문제를 풀었다. 겁도 없이 골드 문제를 손댄 죄...Solutionn = int(input())list = list(map(int,input().split()))dp = [1] * nresult = []for i in range(n) : for j in range(i) : if list[i] > list[j] : dp[i] = max(dp[i] ,dp[j]+1) # i 에서의 최적의 해를 갱신해준다. max_length = max(dp) # 가장 긴 증가하는 부분의 길이- 먼저 가장 긴 증가하는 부분 수열의 길이를 구한다.m..