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..

Level 2. 유사 칸토어 비트열 너무 어려운 수학 문제.. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include using namespace std; int f(int n, long long x) { if (n == 1 || f(n - 1, x / 5)) return (x % 5) != 2; else return 0; } int solution(int n, long long l, long long r) { int answer = 0; for (long long i = l - 1; i < r; ++i) answer += f(n, i); retu..

Level 2. 숫자 카드 나누기 우선, 원소의 범위가 크므로 단순 반복문을 사용하면 시간 초과가 발생할 것이다. 약수를 구하는 것은 유클리드 호제법을 사용하면 된다. GCD(a, b) = GCD(b, (a % b)) a, b의 대소관계는 상관 없다. GCD(a, b, c) = GCD(GCD((a, b), c)이다. 이 문제는 그냥 각 배열의 최대공약수를 구하고, 조건에 맞는 큰 수를 반환하면 된다. 문제에서는 마치 최대 공약수를 구하고도, 그 최대 공약수의 약수 중에서 조건에 맞는 것을 찾아야 하는 것처럼 나와 있다. 하지만, 최대 공약수로 나누어 떨어지는 데 그 약수로 나누어 떨어지지 않는 경우는 존재할 수 없다. #include #include #include using namespace std; ..