목록Algorithm (428)
Mini
백준 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에 각각 따..
프로그래머스 도넛과막대그래프 c++ // 그래프 차수 특징발견, 사이클검사방법, 최대번호노드 찾는방법
https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 그래프 차수 특징발견각 그래프마다 대표정점의 특징(고유한 degree값)이 존재한다.해당정점의 갯수가 그 그래프의 갯수이다!0. 모든그래프의 갯수 == 시작점에서 뻗어나가는 간선갯수와 같다.4에서 위로가는 집합 : a모양좌로가는 집합 : b모양우로가는 집합 : c모양이 된다.즉, 3개의 집합이 도넛인지, 뭔지 찾으면 된다.1. 도넛그래프out, indegree가 같다, but 대표정점이 없다. ..
백준 5670 c++ 휴대폰자판 // 트라이 자식수, 소수점출력방법, mx설정방법
https://www.acmicpc.net/problem/56701. mx설정방법1. 그냥 문제에 있는 단어길이의 총합을 mx로 잡으면 된다.n * 단어의 길이 -> 시간초과 난다...각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 10^6이다. 2. 소수점출력방법 cout 하면된다. 3. 트라이 자식수(의사코드)1. insert 하면서 cnt를 +1 하면서 지나감 // cnt가 1임 -> 유일값2. 값이 -1이면, child를 +1 한다. // 자식수를 기록해놓는다.3. 삽입마지막단계에 chk배열로 단어의 끝을 표시한다.* find ( root의 자식 부터 시작하므로 ret=1부터 시작)0. !! ret+1은 다음단어를 입력받는다는 뜻이다. !!1. cnt가 1이면 유일값이므로 그..
https://www.acmicpc.net/problem/21276 1. 문자열을 idx로 바꿔서 풀어라1. map m을 두고 sort 후m["철수"] = 0 , m["석열"]=1 ... 이런식으로 할당하면 된다.2. 이래야 실수를 줄이고 디버깅, 복잡도등 이점이 많다.. 2. 조상찾기주의점석호 철수(조상) 일때,석호 그래야 철수의 indegree가 0이됨.* 위상정렬의 기본 idea가 indegree가 0인점을 제거해 나간다는 점을 꼭 생각할것!! 3. 의사코드1. 문자열을 idx로 바꿈2. 입력만 문자열일뿐 숫자 위상정렬과 같이 생각하면 쉽다.자료구조가 숫자 그자체에서 해당 idx로 바뀌었을 뿐이다.vector adj[1001]; //i노드의 인접리스트들의 idxvector child[1001]; /..
백준 2623 음악프로그램 c++ // 위상정렬, 사이클 검사방법
https://www.acmicpc.net/problem/2623 1. 사이클 검사방법결론 : 큐를 탐색하면서 , 차수가 0인애를 result에 담고, result.size가 n이아니면 사이클이 있는것임!이유 : 위와 같을때, a가 큐에들어가려면 c가 없어지면서 deg[a]-1 해줘야 되고c가 큐에 들어가려면 b가없어지면서 deg[c]-1 해줘야 되는데a,b,c는 서로가 없어져야 큐에들어갈수 있음 -> 그런데 데드락처럼 큐에 들어갈수없는 존재들이다.따라서 사이클이 있는 a,b,c는 정답에 들어가지 않음 -> result.size()가 4(n)가 아닌 1이 되어있음 2. 전체코드#include using namespace std;typedef long long ll;vector adj[10001]; //i..