일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- AWS
- 동시성
- 전문가를 위한 파이썬
- Network
- dockerfile
- IMAGE
- 알고리즘
- Algorithm
- Thread
- Python
- BAEKJOON
- Kubernetes
- fluent python
- Refactoring
- 플랫폼
- Fast API
- RabbitMQ
- Ethereum
- BlockChain
- 러스트
- Container
- docker
- rust
- function
- 파이썬
- guru
- 이더리움
- 백준
- 블록체인
- 코어 이더리움 프로그래밍
- Today
- Total
글쓰기 | 방명록 | 관리 |
목록전체 글 (99)
Victoree's Blog
Concept & Idea 가장 중요한 Concept은 DP[i][j]가 I부터 J까지의 최소 행렬 곱셉 횟수를 메모해놓는 배열이라는 점이다. 간단히 배열값을 바꿔가면서 순차적으로 검색하는 풀이는, 뒤쪽 배열들을 우선적으로 묶었을 때를 고려하지 못한다. 첫번 째 컨셉을 고려해서 문제를 풀기 시작해보자. 최종적으로 구하게되는 값은 DP[1][N]이다. 이 값을 출력하기 이전에, 계산될 과정은 DP[1][N] = DP[1][k] + DP[k+1][n] + map[1][0]map[k][1]map[n][1]; 일것이다. 해당 사진처럼 인덱스를 하나하나 써가며, 풀이를 하면 필요한 작업만 연산할 수 있고, 생각의 정리를 더 잘 할 수 있게 된다. 이런 식으로 연습을 하도록 하자! Code #include usin..
Concept & Idea 1 3 6 10의 수열을 만들고, 1 4 10 20의 수열을 만드는 것은 쉬운 작업이었다. 처음에는 30만 * 30만은 거뜬할거라 생각했는데, 생각해보니까 시간초과가 날 수 밖에 없었다. 사면체 배열의 수 * 30만 만큼만 비교하면 문제를 더 빠르게 해결할 수 있다. Code #include #include using namespace std; int n; long long layer[200]; vector vec; long long dp[300001]; int main(){ cin>>n; for(int i=1; i
Concept & Idea 앞서 공부했던 LIS 알고리즘을 이용하여 문제를 해결할 수 있었다. map은 입력받는 배열이고, p1은 수열을 출력하기 위한 순서를 기록해놓는 배열이다. 또한 LIS 알고리즘을 이용하려면 LIS를 체크하기 위한? 배열이 있어야한다. 내 코드에선 그 배열이 T배열이다. int lowIndex = lower_bound(t+1, t+pIndex, map[i])-t; 이 코드에서 틀렸습니다를 고칠 수 있었다. 나는 배열의 시작을 0부터 하지 않고 1부터 했으며, 이 문제의 입력으로 음수가 들어올 수 있다. 그래서 0과 음수를 비교했을 때, lower_bound에서 오류가 나왔기 때문에 오답을 냈다. 배열의 시작주소를 +1하니 문제를 해결할 수 있었다. 이 문제에서 또 핵심적인 하나의 ..
Concept & Idea LIS 알고리즘에 대해 공부하였다. 벡터는 lower_bound를 찾기 위한 벡터 배열이다.1. 해당하는 벡터 배열의 가장 마지막 요소보다 크기가 더 크면, 배열에 그냥 푸쉬해준다.2. 해당하는 벡터 배열의 가장 마지막 요소보다 크기가 더 작으면, 벡터 배열에 적절한 요소를 찾아 넣어준다. 이때 적절한 위치를 찾는데, 어차피 sort되어있는 배열이기 때문에 lower_bound를 이용하여 index를 찾고 값을 갱신해준다. lower_bound를 사용할 때는, 해당 배열의 첫 주소, 끝 주소, 찾고싶은 값을 매개변수로 넣고 배열의 시작 주소를 빼주어야 index값을 구할 수 있다. Code #include #include using namespace std; int n; lon..
Concept & Idea 다이나믹 프로그래밍적으로 사고하는 것은 맞았다. 내가 i,j에 위치해있을 때, [i-1][j-1], [i][j-1],[i-1][j]를 검사하는 것이 중요했다. 처음에는 max값으로 잡았는데, min값으로 잡아야 했었다. min으로 잡고나니 또 다른 문제가 발생했었는데, dp배열을 내가 계속 갱신해주고 있었던 것이 문제였다. dp[i][j]=t; dp[i-1][j-1]=t; dp[i][j-1]=t; dp[i-1][j]=t; 이 작업을 생략하고, 그냥 dp[i][j]=t 를 해주니 맞았다. Code #include #include using namespace std; string map[1001]; int dp[1001][1001]; int n,m; int res=0; int ma..
Concept & Idea 문제 상황을 좀 더 간결히 해서, int x에 값을 넣음으로 조건문이 되게 간단해 질 수 있었다. 자리가 1자리일 때의 경우와, 2자리가 가능할 때의 경우를 나눠서 생각했으면 빠르게 풀었을 것 같다. 또한 더할 때 dp[i-1]%1000000 라고 풀었었는데, 이렇게 풀면 안된다. 더하고 나서 따로 mod를 취해주어야 한다…😢 Code #include #include using namespace std; string n; int dp[5001]; int main() { cin>>n; int s=n.size(); dp[0]=1; n=" "+n; for(int i=1; i=1 && x=10 && x