https://www.acmicpc.net/problem/3584 자기 자신도 조상에 포함시켜야 한다는 점이 가장 유의해야 할 점이다. 현재 조상을 저장할 새 노드를 선언한다.현재 조상 노드를 a를 시작으로 a의 조상을 거슬려 올라가며 순회한다. 현재 조상 노드와 b가 같거나, b의 조상 노드와 같으면 둘의 가장 가까운 공통 조상이다.현재 b 노드에 대해서 a 노드의 조상을 모두 검사했는데 없으면, 다시 현재 조상 노드를 a로 초기화 후, b를 b의 조상으로 초기화하고 검사를 다시 수행한다.#include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T;..
📚분류
https://www.acmicpc.net/problem/5214 보통 BFS에서는 정점이 하나의 종류이지만, 이 문제에서는 정점을 두 종류로 나누어 푸는 것이 좋다."역"에 대한 정점과 "하이퍼튜브"를 정점으로 두고 배열을 저장한다.이러면 각 입력의 최댓값인 100,000개와 1,000개가 주어져도 101mb를 차지하기 때문에 메모리 초과를 해결할 수 있다. 정점들을 저장할 때, 시작 역인 1번 역을 포함하는 하이퍼튜브들을 따로 저장한다.문제가 1번 역에서 시작하여 마지막 역에 도착하는 것이니, 무조건 1번 역으로 시작해야 하기 때문이다. 1번 역이 포함된 하이퍼튜브들을 대상으로 BFS를 수행하여 최단 거리를 구한다. BFS 로직방문한 하이퍼튜브를 체크하여 순환이 일어나지 않도록 한다.현재 하이퍼튜브에..
https://www.acmicpc.net/problem/2879 가능한 많이 그룹을 묶어 탭을 편집해야 한다.그룹을 묶는 조건은 나와 같은 편집 방법(추가 or 삭제)인 연속된 줄들만 묶을 수 있다.개별적으로 남은 줄들은 어쩔 수 없이 남은 편집 횟수만큼 그대로 편집해줘야 한다. 따라서, 앞에서부터 자신의 줄이 올바를 때까지 다음 과정을 반복한다.나부터 시작해서 그룽으로 묶을 수 있는 마지막 줄의 위치까지 그룹으로 묶는다.그룹 내에서 가장 적은 편집 횟수로 올바르게 되는 줄의 편집 횟수를 찾는다.그룹을 다 같이 편집할 때, 하나라도 완성이 되면 그룹을 다시 재구성해야 하기 때문해당 편집 횟수만큼 그룹을 모두 편집한다.이러면 그룹 내에서 최소 한 개의 줄은 완성이 되므로 다시 그룹을 재구성해야 함.편집 ..
https://www.acmicpc.net/problem/30885 먼저, 문제 설명을 잘못 해석하기 쉽기 때문에, 문제 조건부터 보자.다음과 같은 입력의 전개이다.41 3 4 2 1 -> 3 -> 4 -> 2 순으로 흡수를 진행한다. 자신과 인접한, 즉 왼쪽 - 오른쪽의 미생물에 대해서만 흡수를 시도할 수 있다.현재 날의 크기를 기준으로 자신보다 크기가 작거나 같은 미생물을 흡수한다. 1의 경우, 먹을 수 있는 게 없으니 넘어간다. 3의 경우, 왼쪽을 먹고 4가 된다.여기서, 4가 되었으니 오른쪽의 4를 먹을 수 있지 않나? 하는 의문이 생긴다. 조건 3의 "흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다" 라는 문구를 보자.3을 기준으로 한 번에 왼쪽 와 오른쪽을 흡수해야 하므로, ..
https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.이 말은 즉, 그리디로 풀라는 얘기와 같다. 각 이동 방향 문자를 사전 순으로 나열하면, 아래[d] -> 왼[l] -> 오[r] -> 위[u] 순서가 된다.즉, 목표 위치로 가는 경로를 구할 때, 다음과 같은 규칙이 생긴다.가장 아래로 많이 간다.아래로 갈 수 없다면, 왼쪽으로 간다.왼쪽으로 갈 수 없다면, 오른쪽으로 간다.오른쪽으로 갈 수 없..
https://school.programmers.co.kr/learn/courses/30/lessons/17677 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해시 맵을 사용 하여 풀었다.코드 설명은 주석으로 대체한다. 교집합, 합집합을 구할 때, 한 번의 집합 순회로 구하는 방법을 생각해 봤다.두 문자열의 총집합 수에다가 교집합을 뺀 값은 합집합이라는 결론이 나왔다. 예를 들어, 두 문자열의 집합 A와 B가 있다고 하자. (편의상 숫자로 설명)A = { 1, 1, 2, 2, 2 }B = { 1, 2, 2 }교집합은, 서로 중복되는 요소를 min으로 계산한다.따라서, { 1, 2, 2 }가 된다. ..
스켈레탈 메쉬 컴포넌트(USkeletalMeshComponent) 에는 애니메이션 틱을 최적화하기 위한 옵션인 Visibility Based Anim Tick Option가 있다.이 설정은 스켈레탈 메쉬가 화면에 보이는지 여부에 따라 애니메이션 업데이트(Tick)를 조정하는 기능이다.즉, 화면에 보이지 않는 메쉬는 애니메이션 업데이트를 중단하거나 줄여 성능을 절약할 수 있다. 설정 방법enum class EVisibilityBasedAnimTickOption : uint8{ AlwaysTickPoseAndRefreshBones, // 항상 애니메이션 틱 실행 (기본값) AlwaysTickPose, // 항상 애니메이션 틱 실행, 그러나 본(뼈대) 업데이트는 안 함 OnlyTic..
https://school.programmers.co.kr/learn/courses/30/lessons/389481 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 먼저, 봉인된 주문을 순서대로 정렬한다.내가 찾으려는 n번째 안에 봉인된 주문이 없으면 계산할 필요가 없기 때문이다.내가 10번째 문자를 찾는데, 그 안에 3개의 문자가 봉인되었다면, 그냥 13번째 문자를 찾으면 된다. 일단 이렇게 봉인된 주문을 고려한 최종적으로 찾아야 할 순번을 구한다. 다음으로, 이제 이 순번의 문자를 구하면 된다.일단 절대로 for문으로 이를 하나씩 올리는 건 불가능하다. 찾으려는 문자의 순번을 보면, 정답이 몇 자리인..
