분류 전체보기

백준 12865 평범한 배낭 c++ // dp는 경우의수로 해결

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. dp는 if(dp[i][j]=~~~) else dp[i][j]=~~~ 형태로 해결하라 2. 전체코드 #include using namespace std; int n, k,ret; int d[104][100000+4]; // i번째 물건까지 왔을때 최대가치, 제한무개 j int weight[100 + 4]; int value[1..

백준 1753 최단경로 c++ // 다익스트라 알고리즘

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 고찰 정석다익스트라 : O(V^2+E) 우선순위큐 다익스트라 : O(VElgE) 우선순위큐로 풀면된다. 2. 의사코드 1. q.push(0비용,시작정점) 2. 최소거리vertax 선택, 최단거리와다름->무쓸모->continue 3. v의 이웃에 대해, 이웃으로직진 > v로직진+이웃비용 -> 후자가 더짧음 -> d업뎃, q.push 4.while(q.siz..

프로그래머스 표편집 c++ // 연결리스트 직접구현 하는방법, 삽입삭제 되돌리기는 연결리스트(직접구현)!

https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 고찰 stl의 list를 쓰면 풀수없는듯 하다. 이유 : prev,next 가 없음.. - 삽입삭제, 되돌리기는 연결리스트(직접구현)! - 삭제된 노드도 prev,next가 남아있기때문에 복원이 ez하다! 2.전체코드 #include using namespace std; struct Node{ int n; Node* prev; Node* next; Node(int n, Node* prev, ..

프로그래머스 거리두기확인하기 c++ // bfs, check함수 활용방법, 문자열을 배열처럼 활용하는방법

https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문자열을 배열처럼 활용하는방법 auto place : places 후 place[i][j]로 접근하면 된다. places -> [POOOX, PPPPP..], [PPAP, ...] [...] place -> [POOOX, PPPPP, ...] place[i] - > POOOX place[i][0]=='P' 2. check함수 활용방법 1. check로 의사코드짜고 2. 이후에 구체적으로 구현..

프로그래머스 숫자문자열과영단어 c++ // 문자열, regex_replace 사용법

https://school.programmers.co.kr/learn/courses/30/lessons/81301/solution_groups?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. regex_replace 사용법 s=regex_replace(대상문자열, regex("찾는문자열"), "대체할문자열"); //대체된 문자열을 반환함 2. 내 답안(노가다) #include using namespace std; int solution(string s) { string answer = ""; for(int i=0;i='0' &&..

프로그래머스 코딩테스트공부 c++ // dp, 예외처리방법

코딩테스트 연습 - 코딩 테스트 공부 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 삽질과정 n이 150밖에안되서 빡구현인줄 알았는데, 알고보니 dp였다... 1.1 현재값 계산을 위해 이전값을 이용한다 -> dp를 떠올렸어야 했다. 2.주의사항 입력값이 최대값보다 큰경우, 다음계산할 값(코딩력,알고력)이 최대값을 넘을경우, 최대값으로 고정하는 로직이 필요하다. 2. 전체코드 #include using namespace std; int max_alp,max_cop; const int INF=9..

백준 20922 겹치는건 싫어 c++// 투포인터 정석풀이 형식

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 1. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n>>k; for (int i = 0; i < n; ++i) { ci..

백준 22862 c++ // 투포인터 응용방법(db 이용)

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 1. 의사코드 holsu변수를 db로 사용한다. holsu변수 => s~e까지 구간중 홀수의 갯수를 저장, 갱신한다. 2. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); ..