7건의 항목
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.
실버4 : 그리디 문제이다. 풀이 단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 문자열만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.
골드2 : 그리디, 정렬 문제이다. 생각 실제로 운송물을 움직인다고 생각해보자. 그렇다면 가장 무거운 하중을 움직일 수 있는 크레인이 가장 많이 움직여야 최단 시간에 짐을 움직일 수 있다. 이부분이 핵심이다.
실버1 : 그리디 문제이다. 풀이 처음에 부르트 포스로 접근했다가, 시간초과가 났다. 그래서 그리디로 방향을 전향했다. >가 나왔을 때, 가장 큰 숫자를 설정해두고, 이하 부터 순서대로 이숫자를 채우는 것으로 해당 조건을 만족시킬 수 있다.
골드5 : 스택 문제이다. 풀이 비슷한 문제를 한 3번 봤다. 근데 그 때는 heap을 사용해서 뒤에서 가장 큰 문자를 계속해서 뽑는 것으로 문제를 해결했다. 풍선 터트리기 그런 방식으로 해당 문제를 다시 풀려했으나, 밑에 알고리즘 분류를 봤는데 stack…이더라.
풀이 어떻게 해야 이런 문제를 풀 수 있을까. 일단 조합과 같은 생각은 n이 작을 때 한다. 완전 탐색 방법을 먼저 생각한다.
Greedy는 알고리즘 문제를 풀 때 보았던 용어이다. 이 용어는 어떤 의미로 사용이 될까? 무언가 탐욕적으로 한다는 의미일 것이다. 다음과 같은 문자열에서 처음 나오는 tag를 검색하고 싶다 해보자.