재원블로그 재원블로그

이 문제는 이진 트리의 탐색을 이용한 문제이다. 2차원 좌표로 점들이 주어지고, 이들을 이진 트리로 간주하여 전위, 후위 순회 결과를 찾는 문제이다. 중요한 점은 x좌표가 같은 것이 하나도 없다는 사실이다. 또한 이진 트리를 중위 순회하면 오름차순으로 정렬된다는 사실도 굉장히 중요하다. 이를 이용하면 x좌표로 오름차순 정렬한 노드들의 순서가 곧 중위 순회한 결과를 나타내게 된다. 그러면 문제가 중위 순회 결과가 주어졌을 때, 전위 및 후위 순회의 결과를 나타내는 문제로 바뀌게 된다. 일정 구간 안에서 가장 y좌표가 높은 노드가 루트임을 이용하여 문제를 쉽게 풀 수 있었다. import java.util.*; import java.io.*; class Solution { Node[] inorder; Lis..

이 문제는 그리디 알고리즘을 이용해서 풀었다. scores의 길이 범위가 [1, 100,000] 이므로 O(N log N) 이하의 알고리즘을 생각해야 한다. 나의 경우에는 근무 점수를 기준으로 내림차순, 같을 경우 동료 점수 기준으로 내림차순으로 정렬했다. 그 후 delete() 메소드를 통해 기준 미달인 사원을 추출하고, rank() 메소드를 통해 완호의 등수를 매기고 리턴한다. delete 메소드가 굉장히 중요한데, 기본 아이디어는 high라는 변수를 정하고 list를 순회하면서 동료 점수가 더 낮은 경우 삭제하고 만약 높다면 high에 새로 저장하는 것이다. 여기서 주의할 점은 점수에 중복이 가능하여 분기문이 추가된다는 것이다. 만약 입력이 [[4, 0], [2, 3], [4, 4], [2, 6]]..

이 문제는 kmp 알고리즘 및 문자열, 구현 문제이다. 문제를 단순화하면 라디오에서 재생된 만큼의 음표 문자열에서 내가 들은 문자열을 각각 탐색하는 문제이다. 아주 단순하게, 브루트포스 알고리즘으로 문자열 탐색을 수행할 경우 O(NM)의 시간이 걸린다. 입력 문자열의 최대 길이가 1,439 이므로 단순하게 제곱하면 약 200만이고, 이를 최대 길이 100인 문자열 배열에 대해 수행해야 하므로 약 2억번의 연산이 걸려 1초 안에 풀 수 없게 된다. 그러므로 문자열 탐색 시간을 줄여아 하고 이 때 kmp 알고리즘이 떠올랐다. O(N + M) 시간에 탐색이 가능하므로 시간 안에 풀 수 있게 된다. 이 문제에서 핵심 포인트가 몇개 있는데 그 중 하나는 #이 붙은 음표이다. C#은 하나의 문자로 취급되어야 하기 ..

이 문제는 구현 문제이다. 문제 설명 자체가 좀 어려운데, 간단하게 말하면 해당 위치의 배열 값으로 위치를 계속 바꿔가면서, 순환되는 숫자들을 그룹으로 묶고, 그 그룹들 중 가진 숫자가 큰 두개의 그룹의 숫자를 곱한 값을 리턴하면 된다. 기본으로 주어지는 cards는 인덱스가 0부터 시작해 문제가 복잡해질 것 같아 새로 card 배열을 만들고 인덱스와 카드 숫자가 일치하도록 만들었다. #include #include #include using namespace std; #define MAX 100 int card[MAX + 1]; int maxSize; void init(vector& cards) { for (int i = 0; i < cards.size(); i++) { card[i + 1] = car..

이 문제는 수학을 이용해서 푸는 문제이다. 점 찍기 문제와 거의 동일한 문제이다. 한 가지 다른 점은 원 내부에 또 다른 원이 있고, 그 원 안에 점은 포함하지 않는 것이다. x가 1부터 r2 - 1 까지 루프를 돌며 y좌표를 계산하면 간단히 풀 수 있다. 이 때 유의할 점은 x가 r1 + 1부터 x가 r2 - 1까지인데, 이때는 calculateLow()가 엉뚱한 값을 내놓기 때문에 low를 1로 설정한 뒤 점의 개수를 세어주는 것이다. 또 하나 주의할 점은 이유는 모르겠지만 자료형을 전부 long long으로 놓아야 문제가 제대로 풀린다는 것이다. 두 가지만 주의하면 어렵지 않게 풀 수 있다. #include #include #include using namespace std; typedef long..

이 문제는 수학을 이용해서 푸는 문제이다. 콜라츠 추측에 대한 정보가 주어지는데 이는 그대로 구현하면 된다. 범위에 대한 설명이 헷갈렸는데, [a, -b]에 대해서 [a, 콜라츠 추측 루프 횟수 - b] 로 정의하는 것만 조심하면 된다. 정적분에 대해서는 루프를 돌면서 사다리꼴의 넓이를 구해주는 방식으로 구했다. #include #include #include using namespace std; vector collatz(int number) { vector results(1, number); while (number != 1) { if (number % 2 == 0) { number /= 2; } else { number = number * 3 + 1; } results.push_back(number..

이 문제는 재귀를 이용해서 푸는 완전 탐색 문제이다. 이 문제에서 중요한 점은 하나의 곡괭이를 잡으면 광물 5개를 무조건 캐고 버린다는 것이다. minerals의 최대 길이가 50이고, 곡괭이는 3개 중 하나를 선택하게 되는데, 곡괭이 하나당 광물 5개를 캐므로 실제 최악 시간 복잡도는 3^10 ~= 60,000 이 되어 충분히 완전 탐색으로 문제를 풀 수 있다. #include #include #include using namespace std; #define DIA 0 #define IRON 1 #define STONE 2 #define INF 1000000000 int fatique(int pick, string mineral) { switch (pick) { case DIA: if (mineral..

이 문제는 우선순위 큐를 이용하여 푸는 문제이다. 이 문제를 처음 봤을 때, 그리디 아니면 DP 문제라고 생각했다. 그러나 DP 배열을 만들기에는 입력 값들이 너무 컸고, 그리디는 어떤 방식으로 동작하는 지 끝내 찾아내지 못했다. 그래서 검색을 통해 찾아본 결과 우선순위 큐를 사용하는 아주 간단한 풀이가 있었다. 우선순위 큐를 최소 힙으로 만들고, enemy에 대해 루프를 돌면서 최소 힙에 삽입한다. 이 때 최소 힙의 크기가 k보다 커지는 순간은 무적권의 사용 한도를 넘었다는 것이 되므로, 최소 힙에서 하나를 빼어 현재 가지고 있는 병사에 수에서 뺀다. 만약 이 순간에 남은 병사보다 최소 힙에서 추출한 값이 더 크다면 라운드를 더 이상 진행할 수 없는 것이므로 현재 인덱스를 리턴한다. 만약 루프가 모두 ..