Algorithm

백준 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] 의 상태를 배열에 저장해..

백준 2098 외판원순회 c++ // 상태 비트기반 dp, 비트마스킹, 비트 1111 만드는법

https://www.acmicpc.net/problem/2098 1. 외판원순회 특징1. {a,b,c} 집합을 "방문"한 상태에서 d로 가는 최소값과{b,a,c} 집합을 "방문"한 상태에서 d로 가는 최소값은 같다.즉, {a,b,c} 집합안에서 최소값인 경로(a->b->c 등)는 dp를 채우면서 저장된다.2. 2->3->1->2와3->1->2->2 는 같은 경로이다.따라서, 출발점은 아무거나(1번도시) 로 하자. 1.5. 비트 1111 만드는법1 하면된다!10000 -1 == 1111이렇게하면, 모든도시방문한 비트가 만들어진다! 2. 의사코드1. dfs(현재도시, 방문한도시체크용 비트)dfs(0, 1) 로 시작한다. //(0번도시부터 시작, 0번도시 방문표시==1)2. 기저사례 : 모든도시를 방문한경우..

백준 15486 퇴사2 c++ // 탑다운디피, 재귀디피, 맨뒤에서오는 노드그림을 떠올려라!

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)www.acmicpc.net 1. 의사코드1. 완탐기반, 상태를 배열에 저장함2. 상태 : idx==해당날짜3. 아래 그림을 그리고 참고하면서 max 식을 만들어낸다.max { 상담하는경우는 그때 이익을 더함 vs return 받은 이전값을 그대로 씀 }이값을 배열에 저장한다.#include typedef long long ll;using namespace std;//dp[i] : i날짜일때 최대수..

백준 2240 자두나무 c++ // 탑다운디피, 재귀디피 형식, 비트연산자, memset사용법

https://www.acmicpc.net/problem/2240 2240번: 자두나무자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어www.acmicpc.net1. 탑다운디피1. 디피는 기본적으로 "상태"를 "배열"에 저장하고이미 저장된 경로는 더 연산안하고 배열에 저장된 값을 사용하는 것이다.2. 이문제에서 "상태"는 {idx, 위치, 이동제한} 이다. 그 값은 그상태일때, 획득가능한 자두의 최대값이다. 2.비트연산자1. 나무위치가 1,2로 주어졌지만 이를 0, 1로 바꾸면 코드가 매우 간결해지는 장점이 생긴다.2. 장점 : if(0) , if(1)로 바로 활용가능..

프로그래머스 보석쇼핑 c++ //투포인터 ,슬라이딩윈도우, map,set

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 투포인터 ,슬라이딩윈도우 코드형식s,e=0부터시작해서이렇게 움직이는 투포인터를 슬라이딩 윈도우라고 한다.while(1): e가끝 and 조건불만족 -> 탈출! if(조건만족) e가 범위밖이면 continue! +1하기전 자료구조 갱신! e+1 else +1하기전 자료구조 갱신! s+1해당 형식을 암기하자. 2. map,set 활용법set는 se..

백준 22988 재활용캠페인 c++ // 투포인터, /2주의사항, 투포예외처리

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 의사코드 1. n이 10만 -> 완탐불가 -> 투포? 2. s와 e를 움직이며 관찰한다. 3. e가 이미 x이상인경우-> 가능성없음 -> 제거, cnt+1 4. 병을만들수있으면 만든다. (코드참조) 5. 병을못만드는 경우 -> s+1 -> 더큰값과 합치면 병을 만들수 있는지 탐색한다. 5.1. 위에서 ..

백준 13423 ThreeDots c++ // 이분탐색

https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net 1. 의사코드 1. 2중포문으로 nC2를 함 2. mid값이 존재한다면, 간격이같은 순서쌍이 존재하는것임 -> cnt+1 3. 단, 간격이 홀수이면 mid가 x.5가 되므로 반드시 불가능함 -> continue 처리 4. 시간복잡도 : nC2 (1000*1000/2) * log 1000(이분탐색) 2. 전체코드 #include typedef long long ll; usin..

백준 16472 고냥이 c++ // 투포인터, 매개변수탐색, 투포의 핵심아이디어, set 존재여부 조사하는법

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 1. 시행착오 1. cnt에 e-1과 e를 비교하여 다르면 cnt를 1증가시킨다. 반례 : cac의 경우 실제 cnt는 2가 되어야하는데, 단순히 e와 e-1을 비교하면 ac에서 a!=c이므로 cnt가 증가되어 버린다.. 2. 해결 : set에 현재 등장한 알파벳들을 저장한다 2. 의사코드 1.while(str의 범위내인지 체크) 2. 현재 알파벳갯수가 n이하인경우 -> 너 가능성있어 -> e를 뒤로보내며..