전체 글
[프로그래머스 C++] - 스킬트리
문제 : 스킬트리 분석 다중 for 문을 이용하면 쉽게 풀 수 있는 문제이다. 배운 선행 스킬 개수인 int형 cnt 변수와 bool형 변수인 check를 통해 그때그때 판단해서 처리했다. 구현 int solution(string skill, vector skill_trees) { int answer = 0, cnt = 0; bool check = true; for (int i = 0; i < skill_trees.size(); i++) { for (int j = 0; j < skill_trees[i].size(); j++) { for (int x = 0; x < skill.size(); x++) { if (skill[x] == skill_trees[i][j]) { if (x == cnt) { cnt++..
[프로그래머스 C++] - 124 나라의 숫자
문제 : 124 나라의 숫자 분석 10 진법 숫자나라 진법 10 진법 숫자나라 진법 4 11 19 141 5 12 20 142 6 14 21 144 숫자나라의 진법이 기본적으로 3진법을 따라가는 것을 알 수 있다. 따라서 맨 뒷자리인 1, 2, 4 는 각각 주어진 숫자를 3으로 나눈 나머지 1, 2, 0에 해당되는 것을 구할 수 있다. 또한 3개씩 끊어 생각할 때, 맨 뒷자리를 제외한 앞자리는 동일한 것을 알 수 있다. 19, 20, 21로 예를 들면 각기 맨 뒷자리는 나머지인 1, 2, 0에 해당하는 1, 2, 4이고, 앞자리는 14로 동일하다. 여기서 14는 10진법으로 6인데 6이 나온 순서는 다음과 같다. 3개씩 끊어 생각할 때, 그 중 3의 배수에서 3을 뺀 값을 3으로 나눈 값이다. (3으로 ..
알고스팟 - 트리 순회 순서 변경
문제 : 트리 순회 순서 변경 (난이도 : 下) 분석 전위 순회 데이터를 통해 root 값을 확정적으로 알 수 있다. (preorder[0]) 중위 순회 데이터를 통해 왼쪽 트리와 오른쪽 트리의 개수 파악이 가능하다. 이를 적절히 조합하면 후위 순회 데이터를 추출할 수 있다. 구현 ※ std::find() 함수의 활용과 printPostOrder() 호출 순서를 눈여겨보자. vector slice(const vector& v, int a, int b) { return vector(v.begin() + a, v.begin() + b); } void printPostOrder(const vector& preorder, const vector& inorder) { const int N = preorder.si..
알고스팟 - 외계 신호 분석
문제 : 외계 신호 분석 (난이도 : 中) 분석 이 문제의 핵심은 입력단의 크기이다. 모든 입력단을 처리하기에는 너무 큰 것을 알 수 있다. 따라서 이 문제는 온라인 알고리즘(online algorithm)을 사용해야 한다. 온라인 알고리즘(online algorithm): 전체 입력이 한 번에 주어지지 않아도 계산을 할 수 있는 알고리즘을 말한다. 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워 넣는 방법으로 동작하는데, 처음에 모든 원소가 주어지지 않아도 정렬을 시작할 수 있다. 오프라인 알고리즘(ofline algorithm): 반면 선택 정렬은 남아 있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 동작하므로, 모든 원소를 알고 있어야 한다. 일단 입력단의 크기를 ..
스택 - 1. 짝이 맞지 않은 괄호
문제 : 짝이 맞지 않은 괄호 (난이도 : 下) 분석 Stack의 구조인 LIFO(Last In First Out)를 안다면 쉽게 접근할 수 있는 문제이다. 짝이 맞는지 확인하는 함수 wellMatched()에서 짝을 맞추는 과정을 유의 깊게 봐보자. (주석 참조) 구현 bool wellMatched(const string& input) { // opening과 closing의 문자 순서를 유심히 보자. // idx로 짝을 맞추기에 같은 순서로 선언됐다. const string opening("({["), closing(")}]"); stack openStack; for (int i = 0; i < input.size(); i++) { // find() 함수는 일치하는 idx를 반환한다. // 만약 일치..
연결 리스트 - 조세푸스 문제
문제 : 조세푸스 문제 (난이도 : 下) 분석 문제 상황이 원형 리스트 상태이다. STL에선 원형 리스트를 지원하지 않으므로 약간의 변형을 통해 구현하면 쉽게 문제를 해결할 수 있다. 구현 void josephus(int n, int k) { list survivors; for (int i = 1; i 2) { // earse() 지운 원소의 다음 원소를 반환 kill = survivors.erase(kill); if (kill == survivors.end()) kill = survivors.begin(); n--; // k-1 번 다음 사람으로 옮긴다. for (int i = 0; i < k - 1; i++) { kill++; if (kill == survivors.end()) kill = survi..
동적 계획법 - 13. 두니발 박사의 탈옥
문제 : 두니발 박사의 탈옥 (난이도 : 中) 분석 이 문제는 학부 때 확률과 통계를 수강했던 사람이면 마르코프 연쇄(Markov Chain)를 생각할 수 있을 것이다. 앞서 푼 문제를 참고하면 확률을 처리하는데 큰 문제는 없을 것이다. 2021/01/03 - [알고리즘 문제 해결 전략] - 동적 계획법 - 10. 우물을 기어오르는 달팽이 동적 계획법 - 10. 우물을 기어오르는 달팽이 문제 : 달팽이 (난이도 : 下) 분석 처음 풀면 매우 당황스러운 문제이다. 경우의 수를 구하는 것과 달리 확률은 어떻게 처리할지 고민이 된다. 그러나 코드를 한번 보고 나면 어떻게 처리할지 감 return-value.tistory.com search(days, num) = 탈옥 d일 후 두니발 박사가 num 마을에 있을..
동적 계획법 - 12. 폴리오미노 & 메모이제이션
문제 : 폴리오미노 (난이도 : 中) 분석 일단 poly(n) = n개의 정사각형으로 만들 수 있는 세로 단조 폴리오미노의 수를 반환한다고 하자. 그러나 매개변수 n 하나로 폴리오미노의 위치를 정하기가 애매하고 어렵다. 따라서 1st row에 있는 정사각형 수 별로 나머지 rows의 폴리오미노 반환을 받아야 한다. 1st row의 정사각형 개수를 firsts라고 할 때, poly(n, first) 함수를 정의하자. poly 함수는 n개의 정사각형을 포함하되, 1st row에 first개의 정사각형이 들어가는 폴리오미노의 수를 반환한다. 1st row에 first개의 정사각형이 있고, 2nd row에 second개의 정사각형이 있다고 하자. 이때 이들을 붙일 수 있는 방법의 수는 first + second..