[목차]310 [백준 5052번 / C++] 전화번호 목록 #접근방법 문자열을 담고 있는 벡터를 sort 해준다. 접두어는 현재 벡터 문자열 이전의 문자열이기 때문에 "v[i].find(v[i - 1])" 의 코드를 통해 체크해준다. 만약 0이라면 접두어라는 의미이며 0이 아니라면 접두어가 아니라는 뜻이다. * 0의 의미는 해당 문자열을 찾았을 때 시작 인덱스 번호를 뜻함. #include #include #include #include using namespace std; int main() { int n; cin >> n; while (n--) { int number; cin >> number; string result = "YES"; vector vs; for (int i = 0; i > s; vs... 백준/구현 2022. 3. 2. [백준 1806번 / C++] 부분합 투포인터 문제이다. #접근방법 start, end, sum 변수 생성 start 포인터가 end 포인터 이하일 때 동안 while문을 반복 sum값이 s값보다 이상이면 현재 길이의 최솟값 갱신 sum값이 s값보다 이상일 때 start 포인터 증가 ( sum 값 감소) sum값이 s값보다 미만일 때 end 포인터 증가 ( sum 값 증가) #include #include #include using namespace std; int main() { int n, s; cin >> n >> s; vector v; for (int i = 0; i > a; v.push_back(a); } int start = 0; int end = 0; int sum = 0; int re.. 백준/증가수열 & 투포인터 2022. 3. 2. [프로그래머스 Level_3 / C++] 베스트앨범 unordered_map 을 활용해서 정렬을 잘할 수 있는지를 묻는 문제이다. #접근방법 map(장르, 재생횟수, 고유번호) m1 생성 map (장르, 재생횟수 합) m2 생성 m2에 합산한 값 저장한 후 내림차순으로 정렬 m1에 재생횟수의 내림차순으로 정렬하며 재생횟수가 같으면 고유번호 오름차순으로 정렬 m2의 Key 값은 장르의 이름이며 재생횟수의 합이 큰 것부터 작은 것까지 정렬되어있다. 그러므도 m1에서 m2 장르의 이름을 key값으로 가지는 것을 차례대로 보면서 정렬되어있는 고유번호를 2개까지만 answer에 저장하면된다. #include #include #include #include #include using namespace std; bool cmp(pairv1, pairv2){ if(v1.. 프로그래머스/Level_3 2022. 2. 25. [프로그래머스 Level_3 / C++] 단어 변환 dfs 문제이다. #접근방법 현재 들고있는 문자열과 words 배열의 문자열들을 하나하나 비교한다. 현재 들고 있는 문자열과 words 배열의 특정 문자열과 비교했을 때 딱 하나만 다를 경우 dfs를 호출한다. 이때 dfs를 호출하기 전에 문자열의 인덱스 번호를 방문처리를 해주고 dfs 호출이 끝난 후 방문처리를 풀어준다. #include #include #include #include int v[50]; using namespace std; vector w; string t; int result = 987654321; void dfs(string s, int cnt ){ if(s==t){ result = min(result, cnt); return; } for(int i=0; i 프로그래머스/Level_3 2022. 2. 25. [프로그래머스 Level_3 / C++] 등굣길 dp와 dfs를 활용한 문제이다. 이 문제와 매우 비슷한 백준 문제가 있으니 다음 문제도 풀어보면 좋다. 프로그래머스/Level_3 2022. 2. 25. [프로그래머스 Level_3 / C++] 정수 삼각형 dp 배열을 생성하여 풀면 된다. level_3 라기에는 쉬운 문제여서 어떤식으로 접근하는지만 떠올리면 바로 해결할 수 있는 문제이다. #접근방법 위의 예제를 통해서 dp배열을 생성하면 밑의 숫자값으로 세팅된다. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24 왜 이런 dp 값이 나왔는지에 대해선 아래에 있는 코드를 보고 이해하길 권한다. 즉, 피라미드 구조에서 dp값을 갱신하기 위해서는 현재 위치에서 바로 위에 양쪽에 있는 숫자값중 큰 값을 골라서 더해주면 되는 것이다. * 끝지점일 경우 바로 위의 dp값을 전달받아 현재값을 더해준다. #include #include #include #include using namespace std; int dp[500][500]; in.. 프로그래머스/Level_3 2022. 2. 25. [백준 1520번 / C++] 내리막 길 dp와 dfs를 활용한 문제이다. 어떤 착한 조상이 dfs라는 배를 타고 여행을 떠나는데 길을 잘 모르는 상태이다. 그래서 현재 위치(X)를 표시해주고 그 위치에서 갈 수 있는 "A,B,C,D"의 4개의 갈림길을 "A"부터 차례대로 여행을 계속한다. 결국 가고자하는 도착지점에 도착했을 때 아까 체크해주었던 현재 위치(X)로 돌아가고 "B"라는 갈림길로 또 여행을 간다. "D"까지 여행을 다하고 나서 현재 위치(X) 로 돌아온다. 근데 알고봤더니 "A,B,D" 의 갈림길은 도착지점으로 가는 경로였지만 "C"는 낭떠러지였다 그래서 착한 조상은 현재 위치(X) 라는 곳에 "A, B, D" 이 세개의 경로만 도착지점에 갈 수 있다고 "3"이라는 숫자를 새겨놓는다. 그 조상은 수많은 여행을 통해 "map[500].. 백준/DP 2022. 2. 24. [백준 2098번 / C++] 외판원 순회 비트마스킹과 dp를 활용한 문제이다. tsp 알고리즘은 완전 탐색으로 도시가 n개이면 시간 복잡도 n! 이 걸리는 np-hard문제로 널리 알려져있다. 그렇기 때문에 이미 탐색했던 경로에 대해서는 다시 방문해서 처음부터 재귀함수를 호출할 필요없이 비트마스킹과 메모이제이션을 활용해 기록했던 데이터값을 다시 들고와야 시간초과를 피할 수 있다. #접근방법 * dp [도시의 수][ 방문 비트] ex) [방문비트] -> 1100 : 4번째 도시와 3번째 도시를 방문했다는 뜻. ex.1) " 0 -> 1 -> 2 -> 3 (도시 방문 경로) " 위의 방문 경로는 dp[3][1111(2진수)]의 배열의 주소를 참조하고 있으며 해당 배열에 다음 도시로 가야할 경로값 중 최소값을 더해주며 갱신해준다. 즉, 완전탐색을 하.. 백준/비트마스킹 2022. 2. 23. [백준 1261번 / C++] 알고스팟 dfs 문제이다 #접근방법 dp (벽을 뚫은 횟수)를 생성한다. (큰 값으로 초기화 ) dfs 함수를 호출하는데 벽을 만난다면 카운트 +1 을 해주고 아니라면 현재 카운트대로 함수 호출 만약, dp (벽을 뚫은횟수) 배열에 값이 현재 매개변수로 받아온 카운트 값보다 작다면 갱신해준다. 그게 아니라면 리턴 ex) 0 0 1 1 1 1 0 0 0 1 0 0 예제1) m[0][0] -> m[0][1] -> map[1][1] -> map[1][2] -> map[2][2] 일때 벽을 총 1번 뚫는다. 예제2) m[0][0] -> m[1][0] -> map[1][1] -> map[2][1] -> map[2][2] 일때 벽을 총 3번 뚫는다. 여기서 보면 현재 위치가 둘다 map[2][2] 이지만 뚫어왔던 벽의 개수.. 백준/DFS BFS 2022. 2. 23. [백준 5557번 / C++] 1학년 DP를 활용한 문제이다. #접근방법 입력할 수 있는 개수 최대 100과 최대 sum값을 20을 가지기 때문에 dp[101][21] 배열 생성. 등호를 붙여야 하는 (index-2) 위치에 도달 할 때까지 dfs방식으로 호출한다. ("- 연산", "+ 연산" ) - sum값이 0보다 작거나 20보다 크면 return 0 - 이미 메모이제이션이 되있는 경우 해당 값을 return - (index-2) 위치에 도달했을 때 마지막값과 sum값이 같으면 return 1 (카운트) #include using namespace std; typedef long long ll; int n; ll dp[101][21]; ll d[101]; ll go(int idx, int sum) { if (sum 2.. 백준/DP 2022. 2. 22. 이전 1 ··· 16 17 18 19 20 21 22 ··· 31 다음 반응형