분류 전체보기

백준 1759 암호만들기 c++ // 포함불포함 완탐 dfs, 순열시간초과 나는경우 해결

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 순열시간초과 나는경우 해결 15! == 시간초과 해결 -> 포함,불포함 완탐 (2^15 == 32768) 2. 전체코드 #include using namespace std; int l, c, visited[16]; vector v; int mo[128]; //현재까지 k번인덱스까지 포함,미포함 판단함 / 모음갯수/ tempStr void dfs(int k, int cnt, string s) { i..

백준 9251 LCS c++ // DP 푸는방법 : 1. 부분해->전체해 2. DP테이블 그리기

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. DP 테이블 2. 전체코드 #include using namespace std; string s1, s2; int d[1004][1004]; //LCS(i,j) : x1,x2..xi / y1...yj 의 문자열에서 최대부분문자열의 길이 /* * 1. 부분문제로 만들기 * 2. 뒤부터 탐색 * 3. 맨뒤가 같은경우 : LCS(i,j)=LCS(i-1,..

백준 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..