iridescent

https://www.acmicpc.net/problem/1890

[규칙]

1. 오른쪽과 아래쪽만 이동 가능
2. 칸에 적혀져 있는 칸만큼 이동
3. 0이 나오면 못 감
4. 경로의 개수는 2^63-1보다 작거나 같음
5. 경로의 개수 구해라

[실패 원인]

1. 문제를 제대로 안 읽었다. (최단기 거리인 줄,, )
2. 제일 간단한 DFS로 푸니깐 시간 초과가 났다.
3. 경로의 개수가 2^63-1보다 작거나 같다 == int형으로는 안된다. 

[풀이 설명]

DFS로 푼 것이랑 원리는 비슷한데

반복문을 통해 풀었다. 

• 따른 배열을 만들어서
• route [0][0] 배열에는 1을 저장한다. 
• 각 행열을 다 지나치면서
  • 0이 아니거나, 배열 만든 것(route)이 0이 아니면
  • 가로, 세로에 각 칸에 있는 칸만큼 더해서 더한다. 

이렇게 경로를 저장할 수 있다. 

[소스코드]

#include<iostream>
using namespace std;

int N;
int input_array[101][101];
long long route[101][101] = { 0 };

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> input_array[i][j];
	
	route[0][0] = 1;
	for(int row = 0; row<N; row++)
		for (int col = 0; col < N; col++) {
			if (input_array[row][col] != 0 && route[row][col]!= 0) {
				if (row + input_array[row][col] < N)
					route[row + input_array[row][col]][col] += route[row][col];
				if (col + input_array[row][col] < N)
					route[row][col + input_array[row][col]] += route[row][col];
			}
		}
	cout << route[N-1][N-1];
	return 0;
}

https://www.acmicpc.net/problem/11055

[규칙]

1. 증가 부분 수열
2. 합이 가장 큰 것

[실패 원인]

1. 알고리즘은 간단하였는데, 비교하는 부분에서 합이 큰 값이랑 비교를 안 하고 자신과 작은 값의 수열과 비교해서 틀렸다.

[풀이 설명]

• 증가하면서 합이 가장 큰 것을 선택하면 된다. 
• 나는 배열을 따로 만들어서, 각자 증가하는 부분에 있어서 합을 각 행마다 저장을 했다. 
• 이게 무슨 말이라면, 
•  

  

자신보다 작은 값의 최댓값과 자신을 더하면 된다고 생각했다. 

ex) 50은 자신보다 작은 값이 1과 2가 있다. 

그치만 2는 1을 이미 더한 값이기 때문에 2의 값만 더해주면 된다. (연한 주황색 화살표 참조)

[소스코드]

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
	int N, output_max_num = 0;

	cin >> N;
	vector<int> input_A(N + 1), add_array(N+1,0);
	
	for (int i = 0; i < N; i++)
		cin >> input_A[i];

	for (int i = 0, max_add_num; i < N; i++) {
		max_add_num = 0;
		for (int j = 0; j < i; j++) {
			if (input_A[i] > input_A[j])
				max_add_num = max(max_add_num, add_array[j]);
		}
		add_array[i] = input_A[i] + max_add_num;
		output_max_num = max(output_max_num, add_array[i]);
	}
	cout << output_max_num;
	
	return 0;
}

https://www.acmicpc.net/problem/22857

[규칙]

1. 수열에서 K번 삭제 가능
2. 삭제 후 짝수로 이루어져 있는 연속한 부분 수열 
3. 연속한 부분 수열

[실패 원인]

1. 부분 수열에 대해 내가 잘 몰랐다. 
   • array = [1,2,3,4,5,6,7]
     • 연속된 부분 수열 : {1}, {2}, {3}, {4], {5} ,.... {1,2}, {2,3},.... {1,2,3,4},....

[풀이 설명]

• 최대한 포인터를 사용하지 않고 해 보았다. 
• 어차피 연속된 부분 수열이기 때문에, 짝수부터 시작해야 한다고 생각했다.
  1. 짝수 시작 점부터 짝수 개수를 센다.
  2. 홀수가 나오면 홀수 개수를 센다 (세고 있던 짝수 수는 초기화한다.)
  3. 배열에 짝수, 홀수 수를 각각 넣는다. 
• 홀수의 개수가 들어있는 배열을 이용한다.
  1. 홀수의 개수가 들어있는 배열 0번째부터 더해서 K가 넘을 때까지 반복한다.
     • 반복하면서 짝수의 개수를 더한다.

간단하게 적었지만, 설명이 제대로 안 된 것 같아 그림을 그려서 설명해보자면

위의 그림처럼 노란색 밑줄은 짝수, 초록색 밑줄은 홀수이다.

짝수와 홀수가 연속된 부분을 개수를 세어 각각 배열에 넣은 모습이다. 

문제에서 원소를 K번 삭제하기 때문에 odd의 수가 K번 보다 작어야 한다. 

• 예를 들면 k가 2라면
  • odd배열에서 2보다 작거나 같게 반복하면서
  • even배열을 더해준다.
  • 그렇게 되면 2 + 3으로 젤 긴 수열은 5가 된다. 

• 다른 예시를 들어보면

K = 5 일 때,

odd가 2와 3을 선택을 해야

젤 큰 길이를 가지는 4 + 6 +5가 된다. 

[코드]

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int N, K;
	int odd_row = 0;
	cin >> N >> K;
	vector<int> even(N+1), odd(N+1);
	
    //odd, even배열에 넣기
	for (int i = 0,num, even_start =0,even_row = 0; i < N; i++) {
		cin >> num;
		if (even_start == 0 && num % 2 == 0)even_start = 1;
		if (even_start == 1) {
			if (num % 2 == 0) {
				even[even_row] += 1;
				if(odd[odd_row] > 0)odd_row++;
			}
			else {
				odd[odd_row] += 1;
				if (even[even_row] > 0)even_row++;
			}
		}
	}
    
    //최댓값 구하기
	int max_sum = 0;
	for (int i = 0, sum; i <= odd_row; i++) {
		sum = 0;
		for (int j = i, count = 0;  j <= odd_row; j++) {
			count += odd[j];
			if (count <= K)	sum += even[j];
			else { 
				sum += even[j]; 
				break; 
			}
		}
		max_sum = max(max_sum, sum);
	}
	cout << max_sum;
	return 0;
}

https://www.acmicpc.net/problem/1932

[규칙]

1. 맨 위의 층부터 시작

2. 아래의 있는 수 중 최대가 되는 경로 찾기

3. 대각선 왼쪽 또는 오른쪽에 있는 것만 선택 가능

4. 삼각형 크기 500이하

5. 시간제한 2초

[실패 원인]

• 이것도 마찬가지로 마음 편하게 DFS로 풀었더니 시간 초과가 났다. 
  
  • 시간이 2초나 되는데 오류가 난 것이다. ㅋㅎㅋㅎ, 세상에,,,
  • 그래서 백준의 '질문 검색'버튼을 이용해서 다른 분들도 시간 초과가 났나 보았다. 
  • 보니깐 문제가 '메모이제이션(Memoization) 을 이용해야 한다고 한다. 
    • 메모이제이션이란?
      • 구글에 검색해서 보았더니, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하는 것이라고 한다. 
      • 참고 : https://wondytyahng.tistory.com/entry/memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
      • 근데 이걸 보고 이걸 저장할 값이 있나 생각을 해보았다. 
      • 그전에, 이걸 DFS를 사용할 필요가 있나?라는 생각을 해보니 답이 나왔다. 

[풀이 설명]

• 먼저 마지막 행 위의 행부터 시작하기로 했다. 

  • 

    n-2행부터
    • 자기 아래의 값, 아래 +1 값 중 큰 값을 자신과 더했다. 
    • 옆에 그림을 보면 알 수 있다. 
    • 첫 번째를 설명해보면, 젤 마지막 행에서 4와 5중에서는 5가 크므로, 2(자기 자신)과 5를 더해준다. 
    • 이렇게 0번째 행까지 해준다. 

[소스 코드]

#include <iostream>
#include<algorithm>
using namespace std;

int main() {
	int n; //삼각형의 크기 
	int Triangle[501][501];
	int max_num = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> Triangle[i][j];

	for (int row = n - 2; row >= 0; row--)
		for (int col = 0; col <= row; col++)
			Triangle[row][col] += max(Triangle[row + 1][col], Triangle[row + 1][col + 1]);

	cout << Triangle[0][0];

	return 0;
}

https://www.acmicpc.net/problem/2579

[규칙]

1. 계단은 한 번에 한 칸 or 두 칸

2. 연속 세 칸  X

3. 마지막 도착 계단은 반드시 밟아야 함

4. 총 점수의 최댓값 구하기

[실패 원인]

1. DFS로 푸는 게 젤 안전할 것 같아서 풀었는데 시간 초과가 나왔다. 

- 아마 제한시간이 1초여서 계단의 수가 300 이하이지만, 시간이 부족한 것 같았다. 

2. DFS 말고 아래 설명할 알고리즘으로 풀었는데, 세번째 칸이 무조건 (첫 번째 계단 + 세 번째 계단) 값인 줄 알았는데 문제를 잘 보니 

이렇게 시작점은 포함되지 않기 때문에,(첫 번째 계단 + 세 번째 계단) OR(두 번째 계단 최댓값 + 세 번째 계단)의 최댓값이 세 번째 계단 값이었다. 

[풀이 설명]

DFS가 실패한 뒤, 실패한 이유는 시간 초과여서 '그럼 반복하여 배열을 이용해서 해보자'라는 생각을 하게 되었다. 

순서대로 생각을 해보면, 

º 첫 번째 계단은 1번째 계단 값

º 두 번째 계단은 1번째 계단 + 2번째 계단

º 세 번째 계단은

    (1번째 계단 + 3번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 3번째 계단) : 시작점은 연속된 세 개의 계단을 밟아서는 안된다는 조건에 빠지기 때문

º 네 번째 계단은

    (1번째 계단 + 3번째 계단 + 4번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 4번째 계단)

º 다섯 번째 계단은

    (2번째 계단 + 4번째 계단 + 5번째 계단) 

            OR

    (3번째 계단+ 5번째 계단) 

이렇게 된다.

그래서 식을 생각해보면

X자리의 최댓값을 구하려면

X자리 계단 값 + X-2의 최댓값

X자리 계단 값 + X-1의 계단 값 + X-3의 최댓값

이라는 식이 나온다.

그렇지만 X-1은 왜 계단 값을 구하냐

이것은 옆의 판을 보면 알 수 있다. 

5번의 계단의 최댓값을 구할 시

2번, 4번, 5번 이렇게 뛰어넘는다고 생각하면

4번째 계단은 무조건 앞에 3번을 포함하지 않아야 한다. 

4번째 계단의 최댓값을 구한다면, 3번이 포함할 수 있기 때문에 사용하지 않는다. 

이렇게 소스코드를 짜면,

#include <iostream>
#include<algorithm>
using namespace std;


int main() {
	int N;
	int score[301];
	int max_score[301];

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> score[i + 1];

	max_score[1] = score[1];
	max_score[2] = score[1] + score[2];
	max_score[3] = max(score[2]+score[3],score[1] + score[3]);

	for (int i = 4; i <= N; i++) {
		max_score[i] = max(score[i] + max_score[i - 2], max_score[i - 3] + score[i - 1] + score[i]);
	}
	cout << max_score[N];
	return 0;
}

나온다. 

https://jinseongsoft.tistory.com/251

해보았지만 계속 오류가 났다. 

https://github.blog/2020-12-15-token-authentication-requirements-for-git-operations/

여기서 보면 github는 '2021년 8월 13일부터 Git 작업을 인증할 때 계정 비밀번호를 더 이상 받지 않으며 GitHub.com에서 인증된 모든 Git 작업에 대해 개인 접속 토큰(개발자용)이나 OAuth 또는 GitHub App 설치 토큰(통합자용)과 같은 토큰 기반 인증을 사용하도록 요구할 예정이다.'이라고 파파고가 번역해줬다. 

https://hyeo-noo.tistory.com/184

여기 너무 상세히 적혀있다. 

여기 있는 것을 다 따라하고 , 체크해주면 된다. 

여기서 해시값을 따로 복사해서 저장해둬야한다. 

위에 말한 것처럼 비밀번호대신 hash값을 넣어야 하기 때문이다. 

이만 뿅 

프로젝트를 진행하면서 github를 쓸 수가 없어서 

막 힘들게 힘들게 만들어놓은 잔디밭이 비어져있었다,,

그래서 잔디밭을 매꾸러 날짜 수정을 해보겠다. 

① 먼저. 나는 git bash를 사용했다. 

물론 git을 사용하려면 git을 설치해야 한다. 

설치는 넘어가고

bash창을 열면 

② cd를 통해서 git이 저장될 장소에 간다. 

난 git파일을 D드라이버에 하고 싶어서 여기로 했다. 

복사하면 된다. 

여기서 물론, 파일 경로 적을 때 '\'로 적으면 안 되고, 

'/'로 사용해야한다.

난 이미 저장된 것의 날짜를 수정하기 위한 것이기 때문에, 

혹시 모르니

git init
git remote https://깃허브 주소

하고

③

git log

여기서 수정할 코드의 해시값을 복사를 해준다. 

백 트래킹 이 친구를 함 해보겠다. 

해시값을 복사해준다. 

④ 'q'를 눌러 나간다. 

⑤

git rebase -i 해시값

⑥ 젤 첫 줄에 'pick'값을 'edit'라고 바꾸고

'esc'누르고 ':w'엔터 친다

⑦ 자기가 원하는 달과 날짜, 시간을 지정한다. 

GIT_COMMITER_DATE="Sep 22 10:00:00 2018 +0000" git commit --amend --no-edit --date "Sep 22 10:00:00 2018 +0000"

⑧ git log로 확인한 뒤

⑨ git push 해준다. 

push에서 로그인하면 된다. 

--------------------------------------------------------------------------- KeyError Traceback (most recent call last) ~\anaconda3\lib\site-packages\pandas\core\indexes\base.py in get_loc(self, key, method, tolerance) 3079 try: -> 3080 return self._engine.get_loc(casted_key) 3081 except KeyError as err: pandas\_libs\index.pyx in pandas._libs.index.IndexEngine.get_loc() pandas\_libs\index.pyx in pandas._libs.index.IndexEngine.get_loc() pandas\_libs\hashtable_class_helper.pxi in pandas._libs.hashtable.Int64HashTable.get_item() pandas\_libs\hashtable_class_helper.pxi in pandas._libs.hashtable.Int64HashTable.get_item() KeyError: 733 The above exception was the direct cause of the following exception:

data_en.reset_index()