• Spready 스팀 페이지 • • Spready 플레이스토어 • • Spready Demo 플레이스토어 • 게임 소개 Spready에 대해 간단한 소개부터 하자면, 4개 챕터로 이루어진 색칠하는 3D 퍼즐 게임이다. 각 스테이지에는 캔버스가 배치되어 있다. 플레이어는 크레파스와 지우개를 사용해 모든 캔버스를 ...

4781번: 사탕 가게 문제 링크: 4781번: 사탕 가게 개요 각 테스트케이스마다 사탕 n개의 칼로리와 가격이 주어졌을 때, m만큼의 돈으로 얻을 수 있는 최대 칼로리를 출력하는 문제이다. 0/1 배낭 문제의 형태를 띠고 있지만 각 사탕을 무제한으로 구매할 수 있고, 가격이 정수가 아니라는 점을 고려해야 한다. 풀이 n과 m 입력받...

1395번: 스위치 문제 링크: 1395번: 스위치 개요 세그먼트 트리를 이용해 쿼리를 수행하고 부분합을 출력하는 문제이다. 그러나 원소의 개수와 쿼리의 개수가 최대 100,000으로, 평범한 세그먼트 트리로 풀이하면 시간 초과를 맞이하는 미래가 찾아온다. 이 문제는 ‘느리게 갱신되는 세그먼트 트리’ 알고리즘을 이용할 것이다. 평범한 세그...

1017번: 소수 쌍 문제 링크: 1017번: 소수 쌍 개요 수의 리스트가 주어지면, 리스트에 있는 모든 수에 대해 두 수를 합해 소수가 되도록 짝을 지어줄 수 있는지 여부(A)를 확인해야 한다. 또한 첫 번째 수와 짝지었을 때 A가 되는 모든 수를 오름차순으로 출력해야 한다. 이 문제에서 주어진 리스트는 하나 뿐이지만 두 그룹으로 나누어...

16916번: 부분 문자열 문제 링크: 16916번: 부분 문자열 개요 문자열이 두 개 주어지면, 두 번째 문자열이 첫 번째 문자열의 부분 문자열인지만 판단하면 되는 간단해 보이는 문제이다. 쉽게 떠오르는 방법인 브루트 포스로 풀면 문자열 길이가 n일 때 시간복잡도가 O(n^2)이 되는데, n이 최대 100만이므로 시간 초과를 피할 수 없다....

2696번: 중앙값 구하기 문제 링크: 2696번: 중앙값 구하기 개요 문제가 시킨 일인 수열이 주어지면 홀수 번째 수를 읽을 때마다 중앙값을 출력하는 작업만 착실하게 수행하면 되는 문제이다. 하지만 매번 수열을 정렬하고 중간 인덱스 값을 출력하는 방식으로는 시간초과를 피할 수 없다. 따라서 우선순위 큐를 두 개 이용해서 풀이할 것이다. ma...

14621번: 나만 안되는 연애 문제 링크: 14621번: 나만 안되는 연애 개요 주어진 그래프에서 노드들을 연결하는 최단 거리 트리의 총 거리를 구하는 문제이다. 최소 스패닝 트리 알고리즘 중 크루스칼 알고리즘을 이용해 풀이하겠다. 최소 스패닝 트리에 대해 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 포스...

17387번: 선분 교차 2 문제 링크: 17387번: 선분 교차 2 개요 두 선분의 양 끝 점이 주어지면 교차 여부를 출력하는 문제이다. ccw 알고리즘을 이용해 두 점이 만드는 선분에 대해 다른 한 점이 어느 방향에 위치하고 있는지를 알아낼 수 있고, 이를 이용해 교차 여부를 확인할 것이다. 풀이 ccw 함수 int ccw(int ...

3109번: 빵집 문제 링크: 3109번: 빵집 개요 n*m 크기의 맵이 주어지면 왼쪽부터 오른쪽까지 연결하는 파이프라인을 겹치지 않게 설치할 수 있는 최대 개수를 구하는 문제이다. 최대한 많은 파이프라인을 만들어야 하기 때문에 왼쪽 가장 위 칸에서부터 시작하며, 오른쪽으로 파이프를 연결할 때는 위, 중간, 아래 순으로 진행한다. 풀이 ...

1517번: 버블 소트 문제 링크: 1517번: 버블 소트 개요 주어진 수열에 대해 버블 소트를 수행하여 오름차순으로 정렬할 때 발생하는 Swap의 횟수, 즉 각 원소의 자리 변화의 총 횟수를 구하는 문제이다. n의 범위가 (1 ≤ n ≤ 500,000)이기 대문에 정직하게 버블 소트를 진행하며 Swap의 횟수를 세면 시간복잡도가 O(n^2)...