https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..

백트래킹현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 - 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘 - 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 - 모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것 - 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음 - 만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감 ‼️ 주의재귀로 푸니까 스택 메모리 제한을 확인해야된다.N이 클 경우 백트래킹을 적용하면 시간초과 난다. 백트래킹 알고리즘의 시간 복잡도는 주로 문제의 조건에 따라 달라진다. 선택할 수 있는 숫자가 N개이고, 수열의 길이가 M이므로 총 경우의 수는 O(N^M)다. 따라서 최악의 경우에는 지수 시간이 소요..

https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 문제를 딱 보자마자 유니온 파인드 알고리즘이 생각났다. 풀고보니 유니온 파인드의 기본적인 문제이며, 부모 노드의 중복되지 않은 숫자의 개수는 몇 개인지 세면 되는 단순한 문제였다. 풀이 1 #include #include #include using namespace std; int parent[201]; int getParent(int x){ if(parent[x] == x) return x; re..

https://programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 다익스트라의 기본 문제이다. 다익스트라 알고리즘을 활용하여 dist 값을 찾아낸 뒤, 가장 큰 값을 찾아 그 값과 일치하는 개수를 세면 된다. #include #include #include using namespace std; const int INF = 1e9; vector dist; vector edge[20001]; priority_queue pq; void dijkstra(int..

https://programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 3중 for문에 익숙해지면 풀 수 있는 문제이다. #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for(int i = 0; i < arr1.size(); i++){ vector v; for(int j = 0; j < arr2[0].size(); j++){ int sum =..

https://programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 (0, 1, 2)(0, 2, 1)(1, 0, 2)(1, 2, 0)(2, 0, 1)(2, 1, 0) 다 돌아보면서 가장 많이 탐험할 수 있는 던전의 수를 세는 것이다. 그러므로, next_permutation 알고리즘과 dfs 알고리즘을 둘 다 쓸 수 있다. 풀이 1 (next_permutation) next_permutation 알고리즘을 쓰기 전에 먼저 정렬을 해준다. k의 수는 순열 ..

https://programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 이 문제는 next_permutation 알고리즘으로 풀면 쉽게 풀리지만, 그렇게 해선 시간초과가 나는 문제이다. 해결 방법은 팩토리얼을 사용하여 각 자리의 수를 직접 구해야 된다. 풀이 1 #include #include using namespace std; long long facto(int n){ if(n == 1) return 1; return n * facto(n - 1); } void r..

https://programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 단순한 문제인데 생각보다 시간을 많이 뺏긴 문제이다. s가 1이 아닐 때 반복문을 계속 돌려주고, 0의 개수를 세며 전체 길이에서 0의 개수를 뺀 수를 다시 2진수로 만들면 된다. #include #include #include using namespace std; string Binary(int n){ string str = ""; while(n != 0){ str += to_string(n % ..

https://programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 map을 활용한다면 쉽게 풀 수 있는 문제이다. record가 문자열로 들어왔기 때문에 편리하게 사용하기 위해 reco라는 이중벡터에 넣어줬다. map은 이미 들어온 key값이 있으면 value 예전 값이 사라지고, 업데이트 되는 식이기 때문에 Enter일때나 Chnage일 때 닉네임을 생성하거나, 업데이트 해주면 된다. 결과는 유저 아이디인 key값을 넣으면 업데이트 된 닉네임 value값이 나오..

https://programmers.co.kr/learn/courses/30/lessons/12981 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 조건에 맞지 않는 인덱스를 찾는 것이 우선이다. 1. 이전에 등장했던 단어는 사용할 수 없습니다. map에 영어 단어를 넣고 다음 영어 단어를 넣었을 때, 카운트가 하나라도 됐다면 이전에 나왔던 것이라는 뜻이므로 틀린 인덱스를 찾을 수 있다. 2. 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. 이 방식으로 인덱스를 찾았으면 [번호, 차례] 형태로 return하면 된다. 만약 ..