문제 링크 1. 아이디어 주어진 규칙을 따를 때 저장할 점을 구하는 문제로 한 행 또는 열을 구성하는 사각형의 수 +1이 한 행 또는 열을 구성하는 점의 수가 되며 이를 제곱한 값이 전체 점의 수가 된다. 현재 한 행을 구성하는 사각형의 수를 $a_n$이라고 하면 점화식은 $a_n = 2 \times a_{n-1}$이 되므로 일반항은 $a_...

문제 링크 1. 아이디어 1번부터 $N$번까지 $N$명의 사람이 원을 이루며 있을 때, $K$번째 사람을 제거하는 과정을 반복하는 문제다. 큐 자료구조를 활용하면 간단하게 해결할 수 있는데 1부터 $N$까지를 순서대로 큐에 넣은 뒤 큐의 맨 앞을 바라보며 $K$번째가 될 때까지 큐에서 꺼내서 큐 뒤에 넣다가 $K$번째면 큐에서 꺼내고 출력하는...

문제 링크 1. 아이디어 BaekJoon 11866번 - 요세푸스 문제 0에서 $N$과 $K$의 범위가 더 커진 문제로 여전히 큐를 활용하면 동일하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(N \times K)$ ...

문제 링크 1. 아이디어 거스름돈을 줄 때 동전의 개수가 최소가 되게 해야 하는 문제다. 동전의 액면가가 25, 10, 5, 1센트인 체계에서는 액면가가 더 큰 동전부터 최대한 많이 거슬러주면 동전의 개수가 최소가 된다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 주어진 동전들을 적절히 사용해서 가치의 합이 $K$가 될 때 필요한 동전 개수의 최솟값을 구하는 문제다. 각 동전을 여러 번 사용할 수 있으며 동전의 가치가 오름차순으로 주어지고 서로 배수, 약수 관계에 있으므로 최대한 가치가 큰 동전부터 많이 사용하면 된다. 작은 동전 여러 개로 큰 동전의 가치를 만들고 있다면 그 ...

문제 링크 1. 아이디어 두 정수는 콤마로 구분된다. 따라서 콤마를 기준으로 파싱한 후 합을 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 테스트 케이스 수) 3. ...

문제 링크 1. 아이디어 주어진 좌표를 $y$ 좌표에 대한 오름차순으로, $y$ 좌표가 같다면 $x$ 좌표에 대한 오름차순으로 정렬하는 간단한 문제다. 다만 $N$이 최대 $100{,}000$이라서 $O(N^2)$보다 빠른 정렬 알고리즘이 필요하다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 주어진 좌표를 $x$ 좌표에 대한 오름차순으로, $x$ 좌표가 같다면 $y$ 좌표에 대한 오름차순으로 정렬하는 간단한 문제다. 다만 $N$이 최대 $100{,}000$이라서 $O(N^2)$보다 빠른 정렬 알고리즘이 필요하다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 주어진 세 변의 길이를 통해 직각삼각형인지 여부를 판단하는 문제로 피타고라스 정리를 활용하면 해결할 수 있다. 주어진 세 변의 길이를 정렬한 후 가장 긴 변의 길이의 제곱이 나머지 두 변의 길이의 제곱의 합이랑 같은지 비교하면 된다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 다트가 다트판에서 몇 점에 위치하는지 구할 수 있어야 하는 문제로 다트판의 중심과 다트와의 거리를 피타고라스 정리로 구하고 해당 거리가 어떤 고리에 위치하는지 판단하면 다트의 점수를 구할 수 있다. 2. 복잡도 접근 시간 공간 ...