분류 전체보기

백준 5052 접두사 찾기 c++ // 트라이, 접두사검사, 포함검사

https://www.acmicpc.net/problem/14426 1. 트라이해당 문자 삽입, 삭제, 검색을 O( s.size()) 만에 가능하게 하는 알고리즘이다.주로 접두사검사, 포함검사, 자동완성기능 키워드가 있으면, 트라이 문제이다!1. 삽입2. 삭제chk[cur] 만 0으로 만들어 놓으면된다.3. 검색자식이 -1이면, false를 반환하면된다.그외에는 1 반환. -> 접두사검사chk[cur] 반환 -> 완전한 포함검사  2. 전체코드#include using namespace std;typedef long long ll;const int ROOT = 1; //1번부터 시작!int unused = 2; //다음노드 넣을 번호const int MX = 10000 * 500 + 5; // N * 문..

백준 4811 알약 c++ // 재귀dp, 경우의수는 +

https://www.acmicpc.net/problem/4811 1.의사코드1. 알약을 1개꺼낸 경우 vs 반개꺼낸경우 계속 2분탐색이다.2. 완탐? -> 2^30 -> 불가 -> dp?3. 상태 : 큰알약갯수, 작은알약갯수 : 그때의 경우의수4. 경우의수는 기저사례 -> return 1, 후 +하면 된다.아래 그림과 같이 1이 리턴되고 거꾸로 타고오면서 그런 경우의 수가 모두 더해진다. 2. 전체코드#include using namespace std;typedef long long ll;ll dp[34][34];//큰알약남은갯수, 반알약남은갯수 : 그상태일때, 경우의수ll dfs(int a, int b) { if (a==0 && b==0) return 1; if (dp[a][b] != -1..

백준 1103 게임 c++ // 경우의수 dp, 사이클검사방법

https://www.acmicpc.net/problem/1103 1. 사이클검사방법1. 방문한 좌표를 재방문했으면, 사이클이 있는것이다!! 2.중앙의 y,x에서 출발한경우, vis[y][x]=1 걸고들어간다탐색하면서 봤는데 vis[y][x]=1 이면, 빨간색경로로 갔다온것이다, 싸이클이 있는것임.이후, 원복을 해줘야함!원복안하는경우 : 우측의 2가 vis되있고, 다른경로(빨간경로)에서 2를 방문하면 사이클이 있는것으로 판단해버린다... 3. 의사코드if(visited) -1출력, 종료 visited = 1;상하좌우 탐색visited = 0;  2. 시행착오1. -1검사과정에서 상하좌우 같은수가 있으면 -1을 리턴하도록 했는데 이경우는1 11 1 에서는 먹히지만3 5 5 25 5 5 52 5 5 3 에서..

프로그래머스 n+1카드게임 c++ // 그리디, 집합을 분류하라

https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 시행착오1. 완탐 ? -> 경우의수 : 선택안함, 좌측선택, 우측선택, 둘다선택 (4) ^ 1000(n) ->불가2. dp?상태 : [idx][round][mycard] == 1000*1000*1000 == 10억 -> 메모리초과 -> 불가// mycard (내가 갖고있는 카드)부분을 정수 1개의 상태로 표현 불가능 -> 불가!3. 그리디? 부분최적해가 전체최적해가 된다. 2. 의사코드0. 매순..

백준 17070 파이프옮기기 1,2 c++ // 재귀dp

https://www.acmicpc.net/problem/170691. 의사코드1. dfs("끝" 좌표, 상태 :가로 세로 대각) 의 상태 기록이 필요함2. 기저사례 : 범위밖, 벽이있음 -> 해당 경우의수는 "0" 개로 처리 -> 배제시키기3. 좌표가 n-1인경우 -> 정답 -> 1개의 정답으로 처리.4. 논리부분 : 케이스에 맞게 [초기화, 논리, 리턴] 해주면 끝. 2. 시행착오1. 상태가 대각(2)일때 y-1, x-1도 벽인지 체크해줘야함2. dfs 호출부에서 (0,0,0)이 아닌 (0,1,0) 으로 호출해야함 // 끝좌표가 (0, 1) 이므로. 3. 전체코드#include using namespace std;typedef long long ll;ll n, a[33][33], dp[33][33][..

백준 1010 다리놓기 c++ // 수학, 조합론

https://www.acmicpc.net/problem/1010 1. 시행착오1. 팩토리얼을 dp에 담으면 되지앟나?2. long long의 범위도 벗어난다.. 오버플로우3. 5C2 = 5*4 / 1*2 로 간소화하기 && 그때그때 나눗셈 계산 -> 오버플로 방지 2. 의사코드1. 이문제는 mCn 문제로 간소화 할 수 있다.즉, (1, 3, 4) 순서쌍 하나만 있으면 그것을 안겹치는 경우로 생각하면 된다. 2. nCr 간소화 버전을 코드로 구현하면 끝이다.ex) 5C2 = 5*4*3 (m~m-2) / 1*2*3(r=1부터 위 수행횟수만큼 증가)  2. 전체코드#include typedef long long ll;using namespace std;ll tc, n,m, dp[34];//n!의 값ll df..

백준 1149 RGB거리 c++ // 재귀dp, 추가정보 필요시 해결방법

https://www.acmicpc.net/problem/1149 1. 의사코드1. 완탐 -> 3C1 을 N번반복 -> 3^1000 -> 불가2. dp? 3. 상태 : [idx][색깔] 1000(n개)*3(빨,노,파)에 가능!3.5 값 : 그 상태일때, 비용의 최소값4. 완탐기반으로, 위에서 칠한색을 제외한 2개중 최소값을 dp에 저장함. 2. 추가정보 필요시 해결방법위에서 무슨색을 칠했는지 알아야하기때문에 , b[idx] 배열에 기록해둠. 3. 전체코드#include typedef long long ll;using namespace std;int n, k,dp[1004][3],a[1004][3];int b[1004]; //해당 idx에 어느색을 칠했는지int dfs(int idx, int color) ..

백준 12865 평범한베낭 c++ // 재귀dp, 불가능한경우를 먼저 ret하라

https://www.acmicpc.net/problem/12865 1. 불가능한경우를 먼저 ret하라int dfs(int idx, int weight) { //기저사례 //!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능. // 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨. if (weight > k) { return -987654321; } if (idx == n) { return 0; }idx==n return 0이 먼저오는 경우 : 조건불만족인데 n에 도달한경우도 유효한 경로로 카운팅이 되어버린다.. 2. 의사코드0 번베낭을 담는다, 안담는다1번 베낭을 담는다 안담는다 ... 로 완탐하고dp[idx][weight] 의 상태를 배열에 저장해..