Algorithm

백준 14003 LIS 5 c++ // LIS 이분탐색 오류수정, LIS 출력하는법

https://www.acmicpc.net/problem/140031. LIS 오류수정이전문제는  Ai가 1부터시작하기 때문에if(lis[idx]==0) 이 해당 num이 처음등장하는 개큰수임 과 필요충분조건이 된다하지만, Ai에 0이 있는경우 이 '0'이 처음등장한다는 의미인지 lis안에 계산된 '0'이 라는 의미인지 불명확하다!!!// https://www.acmicpc.net/problem/14003 따라서, if(idx == len) 이렇게 하는것이 Ai의 범위에 상관없이 처음등장하는 개큰수라는 것과 필요충분조건이다!!//lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!! 예시) lis : -2 0 0 5에서 -1삽입시 lis[idx]==0이고, len+1이된다.하지만, len증..

백준 12015 LIS c++ // 이분탐색, LIS nlgn풀이 종결?, 한계

https://www.acmicpc.net/problem/12015 1. 설명1. 기존 dp : O(n^2) // n개입력에대해 * 앞의n개를 살펴보며 최대값을 찾아야함2. lower_bound : lb성질에 의해 n개입력 * lgn으로 구현쌉가능 2. 의사코드1. num을 1개씩보면서2. (lis에없는) 개큰수가 등장한경우, lis길이+13. 나머지는 lb성질에의해 날먹된다.작은값이오면, 기존값을 작은값으로 교체함 i)작은값이옴 -> 10 20 30 에서 25in, idx=30, 30값이 25로 교체됨ii)같은값이옴 -> 10 20 30 에서 20in, idx=20, 변화없음iii)개큰값이옴 -> 10 20 30 [ ]에서 40in , idx=0, lis에 추가해줌4. ex)10 -> 저장, lis+1..

백준 14719 빗물 c++ // 구현, 그리디

https://www.acmicpc.net/problem/147191. 의사코드1. 높이에따라 2차원배열을 만들어줌2. 값이0인곳에 물이 찰수있는지 탐색함3. 좌측이 1이있고 우측에 1이있어야 물이찰수있음빈칸들(0)에 대해 O,X 가능한지 불가능한지 조사함.2. 전체코드#include using namespace std;int Y,X,num, a[504][504],ret;vector> v; //탐색대상위치int left(int y, int x) { if (x = X) { return 0; } if (a[y][x] == 1) return 1; return right(y, x + 1);}//해당좌표에 빗물이 찰수있는지int go(int y, int x) { //좌측에 ..

백준 11000 강의실배정 c++ // 강의실배정 vs 회의실배정, pq cmp 구현시 주의점

https://www.acmicpc.net/problem/110001. 강의실배정 vs 회의실배정1. 회의실배정 : 시작시간이 빠른것부터 배정하면 된다. 배정이가능하다면, ret++ 하면된다.end변수를 사용한다 // 가장최근에 끝난 회의의 종료시간int end = 0; int tot = 0; while(pq.size() > 0){ sub = pq.top(); if(end 2. 강의실배정 :  시작시간기준으로정렬, pq는 종료시간기준으로 정렬top.sec과 입력값.first를 비교하며 가능하다면(즉, 같은 회의실 사용으로 처리하는것이다. -> pq.size가 써야되는 강의실의 수가 된다. 2. pq cmp 구현시 주의점1. cmp는 매개변수가 같으면 거짓을 리턴해야함2..

백준 16928 뱀과 사다리 게임 c++ // dp불가능한경우, bfs복습

https://www.acmicpc.net/problem/169281. dp불가능한경우1. dp는 단방향이고 사이클이 없는 그래프에서만 사용가능하다! 이문제의경우 뱀을만나는경우 뒤로돌아가기때문에 양방향이다!! ->  dp 불가 2. dp 주의점그럼에도 불구하고 dp로 짤때 실수를 많이 했는데,시행착오를 고쳐보자1. 의사코드(그래프)dp는 끝에도달(100)하면 그때 중 최소값을 골라(v표시)가는 알고리즘이다.이때, 98에서 dp=dfs이렇게 저장을 해줘야 "1"값이 저장되어 12로 그대로 전달된다.기존 : dfs만 돌려줬더니 dp초기값인 0이 12번노드로 리턴됬다....  3. 전체코드 dp(오답)오답인이유 : dp는 해당상태를 재탐색하지 않는 알고리즘인데,뱀을타고 역방향으로 이동하는경우 재탐색하면 더 나..

백준 2096 내려가기 c++ // dp도안되면? 슬라이딩 윈도우

https://www.acmicpc.net/problem/2096 꽤나 애먹었던 문제이다...1. 시간복잡도 분석완탐 -> 3^100000 -> 시간초과dp -> [y][x] -> 3*100000 -> 메모리초과(4MB) -> ?? 2. 슬라이딩 윈도우입력을 모두 받지않고, 입력이 들어오면 그때그때 처리한다.모든입력에대해 아래 그림처럼 ㅁ 칸만 보고 그때그때 처리한다. 3. 의사코드1. 역발상이 필요한데mx배열중 가능한 최대값을 먼저 고른후, cur값과 더해야한다!2. 주의사항그 값을 pqr에 저장후 사용해야함이유 : min[0] = min(mi[0], mi[1]) 이런식으로 진행되는데위에서 min[0]값을 바꿔버리므로, 다음 min[1] 계산할때 오답이나온다.  #include using namespa..

백준 1932 정수삼각형 c++ // 재귀dp, 1,2,3,4..n 개 입력받는법

https://www.acmicpc.net/problem/1932 1. 1,2,3,4..n 개 입력받는법int n; cin >> n; for (int i = 1; i > dp[i][j]; } }j 2. 의사코드1. 아래, 우아래 로 이동 하는 dfs2. 그때 상태를 dp에저장 : 그상태일때 최대값3. 기저사례1 : 정상적으로 n번째 노드에 노착기저사례2 : x가 아래 그림과같이 빨간x쳐진곳으로 간경우 -> 비정상 -> 매우작은값을리턴시켜 배제시킴.                     - 특징발견 : x>y인 경우가 그러함. 3. 전체코드#include using namespace std;int n,m,a[504][504];int dp[504][504];//상태 : 좌표 : 그때 합 최대값int dfs(..

프로그래머스 주사위고르기 c++ // 빡구현, 완탐, dp, 이분탐색, 발상 아이디어

https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 의사코드 고민완탐? : 10C5 * 6^5 * 10C5 * 6^5 -> 시간초과상태기반 dp? : (A가고른주사위 bit, B가고른주사위 bit) : 그떄 A의 승수 같은 상태가 중복되지 않는다... and 매 상태마다 6^5 * 6^5 -> 완탐이나 마찬가지임 * dp아이디어 : 메모리, 자료구조(배열)을 이용해 시간복잡도를 줄이자.각 경우마다 주사위의 합들을 arrA, arrB에  각각 따..