(TIL) 20210528

1.Facts(한 것)

---

• 학교 수업 듣기
• C++, 자바스크립트로 프로그래머스 문제 풀기
• 알고리즘 수업 듣기
• 자료구조 정리 및 포스팅

2.Findings(배운 것)

---

여러 알고리즘 문제를 풀다보면, 항상 트리 관련 문제는 풀지 못했었다.

그때는 그냥 단순히 실력이 부족해서 그렇거니 했다(사실 이게 문제이긴 하다)

하지만 실제는 자료구조에 대한 배경지식이 전무해졌기 때문이었다.

 

대부분의 트리 문제는 BFS와 DFS문제인데,

이 두 종류의 문제를 풀려면 이진 트리의 개념을 기본으로 탑재했어야 했는데 그렇지 못했다.

 

이진트리는 포화 이진 트리, 완전 이진 트리와 이를 제외한 이진 트리가 있다.

주로 사용하는 트리는 완전 이진트리를 사용하며, 노드간의 연결을 표현하는 방법은 배열로 표현할 수도 있고,

링크(연결리스트)로 표현 할 수도 있다.

 

특히 순회방법이 중요한데, DFS에서 사용하는 방법은 자손 노드보다 루트 노드를 먼저 방문하는 전위 순회를 사용한다.

(BFS는 레벨 순회)

그리고 노드 마다 모두 번호가 있기 때문에 map<>자료구조를 이용하면 쉽게 구현 및 문제 해결이 가능하다.

 

 

자료구조를 정리하는 겸 해서 프로그래머스에서 스택,큐에 관한 문제를 풀어보았다.

아래 코드는 프로그래머스 기능개발(Lv.2) 문제에 대한 코드이다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

queue<int> q;
queue<int> speed;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int day = 1;
    int num = 0;
    for(int i = 0; i < progresses.size(); i++) {
        q.push(progresses[i]);
        speed.push(speeds[i]);
    }
    while(!q.empty()) {
         while((100-q.front()) <= speed.front() * day) {
             q.pop();
             speed.pop();
             num++;
        }
        if(num != 0) {
             answer.push_back(num);
        }
        num = 0;
        day++;
    }
   
    return answer;
}

위와 같은 방식 말고도, 100-q.front()에 관한 배열을 만들어서 시간복잡도 O(n)으로 구현할 수도 있다.

(처음 떠오른대로 구현했다.)

 

3.Feeling(느낀 점)

---

4.Affirmation(자기 선언)

---

• 나는 매일 성장하는 개발자이다.
• 나는 배우는 것을 즐기는 사람이다.