일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- softeer
- upper_bound
- Kafka
- BFS
- msSQL
- 퇴사통보
- 경력
- 처우산정
- 기술면접
- BOJ
- 연결요소
- 13908
- 매개변수탐색
- 6987
- 오퍼레터
- 이분탐색
- 백준
- incr
- 성적평가
- 처우협의
- 소프티어
- compose
- Docker
- boj #19237 #어른 상어
- 물채우기
- dfs
- 파라메트릭
- @P0
- 백트래킹
- OFFSET
- Today
- Total
목록2020/01 (39)
기술 블로그
https://www.acmicpc.net/problem/2352 LIS 문제이다. n이 40,000이나 되기 때문에, O(n^2)으로는 풀지 못 한다. 따라서, lower_bound()를 활용하여 O(nlogn)으로 풀어야 한다. 참고 : https://hsdevelopment.tistory.com/464 시간 초과 코드(O(n^2))12345678910111213141516171819202122232425262728293031323334#include using namespace std; #define Max 40001 int n, ans, dp[Max];vector v; int main(){ //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r"..
https://dyngina.tistory.com/16 을 참고하여 작성하였습니다. 이 글은 저만의 공부를 위하여 간단 요약한 것입니다. 위의 원글을 보시길 바랍니다. ※ lower_bound를 활용한 LIS 풀이법 단점은 답 밖에 모른다.경로 역추적은 다른 방법을 쓰자. 배열(또는 벡터) 내에서 증가 수열을 유지할 수 있는 최적의 장소를 lower bound를 이용하여 찾아준다. vector v = {10, 20, 40, 30, 70, 50, 60}; 1. 10을 넣는다. 이 때의 v.size() = 1현재 : v = {10} 2. 20을 넣는다. 이 때의 v.size() = 2현재 : v = {10, 20} 3. 40을 넣는다. 이 때의 v.size() = 3현재 : v = {10, 20, 40} 4..
https://www.acmicpc.net/problem/17267 예전에 한참 고민하고, 고민했던 C++로 풀었던 문제이다. 그 당시에는 queue로 풀려고 하였으나, 계속 틀려서 결국 질문을 통하여 해결하였다. 최대한 자유롭게 움직여서 이동할 수 있는 최대 칸 수를 구하는 문제이므로, 최대가 되기 위해서는 상, 하로 우선 먼저 최대한 많이 움직여야 한다. 따라서, deque를 사용하여 상, 하일 때는 rear이 아닌 front쪽에 push를 해주면 된다. 물론 좌, 우일 때는 rear쪽에 push를 해준다. 또한, 내가 못 풀고 있었을 때의 코드에 대한 반례도 올려본다. 아마 deque로 말고, queue로 구현하였다면, 첫 번째 반례에서 20이 뜰 것이다.2 왼쪽에 있는 0으로 바로 가기 때문에 L..
https://www.acmicpc.net/problem/1058 dfs 풀려고 했는데, 계속 틀렸다고 나와서 플로이드-와샬, bfs로 풀었다. 내가 푼 dfs에서는 반례가 있었다. 12345676NYYNYNYNYNNNYYNYNNNNYNNNYNNNNYNNNNYNcs 위의 예시 경우0 → 1 → 2를 한 다음0 → 2 → 3을 해야하는데 이미 전에 2를 방문처리(true)로 해버려서3을 방문하지 못 한다. 따라서, 좀 더 좋은(?) dfs를 설계해야 한다. 이 부분은 나중에.. dfs(오답)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include using namespac..
https://www.acmicpc.net/problem/1449 Greedy그리디 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; int N, L, ans;vector v; int main(){ //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d %d", &N, &L); int pos; for (int i = 0; i
https://www.acmicpc.net/problem/18244 아래의 문제를 변형한 문제이다쉬운 계단 수 : https://www.acmicpc.net/problem/10844 dp[i][j][k] : 길이가 i이고, 끝자리가 j인 숫자. 단 k는 아래와 같다.k=1 : 2번 감소된 상태k=2 : 1번 감소된 상태k=3 : 초기 상태k=4 : 1번 증가된 상태k=5 : 2번 증가된 상태 설명은 주석으로 대체 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include using namespace s..
https://www.acmicpc.net/problem/10844 36번 째 줄을 ans += (dp[n][j] % Mod); 라고 써서, 틀렸다고 떴었다. ans을 더하면서 int 범위를 벗어나는 것 같다. dp[i][j] = 길이가 i인 수에서 j로 끝나는 쉬운 계단 수 단, 끝이 0과 9일 때만 조심하면 된다. 길이가 i이고, 끝이 0일 때는 그 전 길이(i-1)에서는 끝이 1일 때만 계단 수가 된다.길이가 i이고, 끝이 9일 때는 그 전 길이(i-1)에서는 끝이 8일 때만 계단 수가 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std; #define Max..