Level 3. 길 찾기 게임 이진 트리를 구현하고, 좌표의 우선순위가 레벨 순회 순서로 되게끔 트리에 삽입한 후 전위 순회나 후위 순회를 하는 문제다. 좌표과 레벨 순회 순서가 되게 하려면, Y 좌표가 큰 것을 우선으로 하되 같은 경우 X 좌표가 작은 것을 선택하면 된다. 트리 구현을 정말 오랜만에 해보는데 학교 자료구조 시간에 워낙 실습을 많이 해서 그런지, 기어이 새록새록 떠올라 어렵지 않게 할 수 있었다. 삽입할 위치의 부모를 찾을 때는 X 좌표만 비교하면서 Up-down 형식으로 재귀적으로 찾으면 된다. 전위/중위/후위 순회 모두 재귀를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; struct Point { int id; ..

Level 3. 거스름돈 문제를 읽고 왠지 DP일 것 같은 느낌이 들었다. 이제 좀 감을 잡았나 보다.. 화폐 단위를 정렬하고 작은 화폐 단위부터 DP를 진행하는 이유는 중복을 처리하기 위함이다. [1, 2, 2]와 [2, 2, 1]은 같은 것이기 때문에 작은 것부터 수행해야 한다. for문에 금액이 먼저 오게되면, 중복 처리가 매우 번거로워진다. DP도 무작정 하는 것이 아니라, 중복을 고려해 때에 따라 정렬과 for문의 순서를 조정해야 한다. #include #include #include using namespace std; int solution(int n, vector money) { int DIV = 1'000'000'007; vector DP(n + 1, 0); DP[0] = 1; sort(..

Level 3. 섬 연결하기 유니온 파인드(Union-Find) 두 노드가 같은 집합에 속하는지 확인하기 위한 서로소 집합(Disjoint set)을 처리하는 알고리즘이다. 유니온 파인드는 대표 노드를 저장하는 1차원 배열을 이용하며, 각 원소의 대표 노드는 자기 자신으로 초기화한다. 모두 서로 다른 잡합에 존재함을 뜻한다. 유니온(Union) : 특정 2개를 연결해 같은 집합으로 묶는다. 대표 노드끼리 연결해주는 작업이다. a, b의 대표 노드가 각각 x, y이고 x < y라고 한다면, union(a, b)는 y 위치의 값을 x로 갱신해주는 작업이다. 파인드(Find) : 두 노드가 같은 집합에 속해 있는지 확인한다. 자신의 대표 노드를 찾는 작업이다. 해당 원소의 대표 노드부터 올라가면서, 재귀적으로..

Level 3. 가장 긴 팰린드롬 긴 문자열부터 모든 부분 문자열을 확인하는 방법이지만, 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include using namespace std; int solution(string s) { int answer = 0; size_t n = s.length(); for (int len = n; 0 < len; --len) for (int ofs = 0; ofs + len

Level 3. 숫자 게임 최소힙을 구성하고 앞에서부터 비교하면서, B가 더 커 점수를 얻을 수 있는 경우 A의 다음 숫자와 비교하면 된다. 레벨 3 문제는 아닌 것 같다.. #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; priority_queue pqA, pqB; for (int num : A) pqA.emplace(num); for (int num : B) pqB.emplace(num); while (!pqB.empty()) { if (pqA.top() < pqB.top()) ++answer, pqA.pop(); pqB.pop(); } return answer; }

Level 2. 교점에 별 만들기 전에 봤을 때 별을 직접 그려야 하는 문제인 줄 알고 넘겼었는데, 막상 자세히 읽어보니 그렇게 어려운 문제는 아니었다. 가장 바깥 쪽의 점들만 표시하는 건 줄 알고 기겁했었는데, 그냥 모든 정수 점들을 구하면 되는 문제여서 쉬웠다. 교점을 구하는 것은 주어진 공식을 사용하면 되고, 그 중 좌표가 정수인 교점만 활용하면 된다. 교점은 두 직선을 통해 구하므로, 이중 for문을 사용하면 된다. int끼리 곱하면서 범위가 넘어갈 수 있기 때문에 long 타입에 저장해준다. 교점을 구하면서 정답 영역의 최소와 최대 지점을 함께 갱신한다. 그리고 마지막에 정답에 점들을 찍어주면 된다. Y 좌표는 maxY - y가 되고, X 좌표는 x - minX가 됨에 주의해야 한다. #incl..