알고리즘
이진 탐색 트리(Binary Search Tree)
이진 탐색 트리 : BST 정의 이진 탐색 트리 정의에 앞서 이진 트리(binary tree)를 정의하자. 이진 트리란 왼쪽, 오른쪽 최대 두 개의 자식 노드를 가질 수 있는 트리를 의미한다. 이때 자식 노드들은 배열이 아닌 포인터로 left와 right를 담는 객체로 구현한다. 단, left 노드 값은 부모 노드보다 작은 값이고 right 노드 값은 부모 노드보다 큰 값이어야 한다. 이진 탐색 트리는 이런 이진 트리 구조에 이진 탐색(binary search)의 아이디어를 가져와 만든 트리이다. 이진 탐색이란 N개 원소 중 원하는 값을 찾을 때, 매번 탐색 값을 절반씩 줄여가며 탐색하는 것을 의미한다. 이렇게 되면 O(lgN) 시간에 원하는 값을 찾을 수 있다. 순회 및 검색 순회 및 검색을 할 때 이..
[프로그래머스 C++] - 프린트
문제 : 프린트 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번..
[알고스팟] - 요새
문제 : 요새 (난이도 : 中) 분석 주어진 데이터를 트리 형태로 가공하면 쉽게 답을 구할 수 있다. 트리 형태에서 최장 길이는 다음 중 긴 길이에 해당된다. 1. 트리의 높이 2. 잎-잎 길이 입력 데이터 중 첫 번째 데이터는 성 외곽이므로 트리의 root로 설정하고, 나머지 tree를 구성하면 된다. 구현 struct TreeNode { vector children; }; // leaf to leaf len int longest; // root를 루트로하는 subtree의 높이를 반환. int height(TreeNode* root) { vector heights; for (size_t i = 0; i children.size(); i++) { heights.push_back(heigh..
[프로그래머스 C++] - 주식 가격
문제 : 주식 가격 분석 level 2. 치고는 간단한 문제이다. 특이 케이스만 잘 처리해주면 손쉽게 풀 수 있다. 주의해야 할 케이스. 1. 떨어지는 기간이 1초일 때 2. 마지막 기간은 항시 0초 idx 주의하며 이중 for문으로 처리하면 된다. 구현 vector solution(vector prices) { vector answer; for (size_t i = 0; i < prices.size(); i++) { int cnt = 0; for (size_t j = i + 1; j < prices.size(); j++) { if (prices[i]
[프로그래머스 C++] - 기능 개발
문제 : 기능 개발 분석 조건이 간결하다. 1. 매일 개발이 진행된다. 2. 배포는 앞에서부터 이뤄진다. 처리 순서를 반복문을 통해 간단하게 구현할 수 있다. vector solution(vector progresses, vector speeds) { vector answer; while (true) { // base case if (progresses.size() == 0) break; else if (progresses.size() == 1) { answer.push_back(1); break; } // progresses for (size_t i = 0; i < progresses.size(); i++) { progresses[i] += speeds[i]; } // 배포 if (progresses...
[프로그래머스 C++] - 다리를 지나는 트럭
문제 : 다리를 지나는 트럭 분석 고려할 조건들이 다소 복잡하다. 대기차가 1대 이상 존재할 때, 차가 다리 위로 올라갈 수 있으면 진입시킨다. 대기차가 있지만, 집입 불가 시 앞선 차량이 빠질 때까지 기다린다. 다리 위 차량들은 시간이 흐를수록 거리가 줄어든다. 대기차가 없고 다리 위 차가 있다면 시간은 계속 흐른다. 대기차가 없고, 다리 위 차량도 없다면 종료. 조건 1, 2 번 논리를 구현하기가 쉽지 않다. 쉽지 않은 이유는 습관 때문이다. 나도 그렇지만 사람 대부분은 아마 남은 길이를 처리할 때, 다리에 진입한 순서대로 처리하려고 할 것이다. 하지만 깊게 생각해보면 굳이 남은 길이의 데이터들은 진입한 순서 정보까지 저장하고 있을 필요는 없다. 젤 짧은 길이가 결국 다리 위 진입한 차량들 중 가장 ..
[프로그래머스 C++] - 멀쩡한 사각형
문제 : 멀쩡한 사각형 분석 직사각형 구조이기에 대각선 기준으로 대칭인 것을 생각하자. 저 한 블록의 규칙을 정리하자면 다음과 같다. 블록의 크기는 (w / gcd) x (h / gcd) 이다. (gcd는 주어진 수의 최대 공약수이다.) 블록 내의 유호 하지 않은 정사각형의 개수는 (블록의 가로 + 블록의 세로 -1)이다. 구현 ※ gcd를 구하는 과정을 재귀로 처리했다. // GCD func, x > y 가정 int calGCD(int x, int y) { if (y == 0) return x; else return calGCD(y, x%y); } long long solution(int w, int h) { long long answer = 1; long long ret = (long long)w*(..
[프로그래머스 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++..