허비의 기술블로그

카드를 총 N장 구매하려고 한다. 이때 카드의 수가 각각 1장부터 N장까지 있는 묶음의 가격이 차례대로 주어질 때, 딱 N장을 구매하기 위해 드는 비용을 최대로 하는 정답을 찾는 문제다. ex) N = 4, 카드 묶음 = [1, 5, 6, 7] 일 때 이는 1장 묶음을 사는데 드는 비용이 1, 2장 묶음을 사는데 드는 비용이 5, 3장 묶음을 사는데 드는 비용이 6, 4장 묶음을 사는데 드는 비용이 7 이 든다는 것을 의미한다. 4장을 사는데 드는 최대 비용은 2장 묶음을 2번 사서 드는 10이다. 시간 복잡도: O(N^2) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1..

1~100,000 사이의 자연수 N을 제곱수들의 합으로 나타낼 때, 가능한 경우의 수에서 항의 최소 개수를 구하는 문제다. 시간 복잡도: O(N) 풀이 과정 어떤 규칙으로 나타낼 수 있을지 생각이 안 나서 1부터 숫자들을 제곱수로 나타내 봤다. 제곱수 하나로 만들어질 수 있는 1, 4, 9에서 수가 커질수록 1의 제곱이 1씩 붙는 경우가 많다. 하지만 8, 12처럼 뒤에 1의 제곱이 아니라 다른 수가 붙는 경우도 있어 규칙이 존재하지는 않는다. 그런데 여기서 N에 대해 제곱수의 합으로 나타내려고 할 때, 그 항의 개수는 N에서 어떤 제곱수를 뺀 값에서의 항 개수 + 1과 같다. 12의 경우를 다시 살펴보자. N = 12일 때 정답 값은 N = 8일 때 정답 값 + 1이다. 하지만 나올 수 있는 경우는 N..

암호의 길이 L과 암호에 들어갈 후보 C개의 문자가 입력이 들어오면, 암호가 될 수 있는 모든 문자열들을 출력하는 문제다. 단 암호는 문자가 중복되지 않으며, 모음이 1개 이상이고 자음이 2개 이상이다. 또한 암호는 오름차순으로 정렬돼있다. 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 과정 후보 문자열에서, 암호로 뽑을 L개의 문자를 선별한다. 이때 파이썬에선 Collections 모듈의 Combinations 함수를 사용하면 조합을 쉽게 구할 수 있다. 또 암호는 정렬돼있으므로 후보 문자열을 입력받은 다..

가로, 세로의 크기가 각각 N, M인 직사각형에서 (3

그래프의 정점의 개수(N), 간선의 개수(M), 연결된 간선의 정보가 입력으로 주어진다. 이때 주어진 그래프에서 Connected Component(연결된 요소의 개수)를 구하는 문제다. 다음과 같은 그래프가 주어진다면 Connected Component의 개수는 3개이다. 시간 복잡도: O(MN) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 과정 BFS나 DFS와 같은 그래프 탐색 방법을 활용하면 연결된 모든 노드(정점)를 방문할 수 있다..

길이 N이 주어질 때, 1이 2개 이상 연속해서 나오지 않으며, 길이가 N인 2진수의 개수를 구하는 문제다. 단 2진수는 1로 시작해야 한다. 시간 복잡도 : O(N) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 방법 2진수의 길이가 1씩 늘어난다고 하면, 바로 직전에 만들었던 이친수에 0을 붙여서 이친수를 만들 수 있고, 전전에 만들었던 이친수에 01을 붙여 이친수를 새로 만들 수 있다. 이렇게 만들면 이친수가 중복 없이 생성된다. N 이친수 1 1 2 10 3 101,100 4 1001..

N의 크기가 주어질 때 2 * N 사이즈의 직사각형을 (2 X 1), (1 X 2), (2 X 2)의 직사각형으로 채우는 경우의 수를 구하는 문제다. 경우의 수를 10007로 나눈 나머지를 정답으로 출력한다. 시간 복잡도: O(N) 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 방법 N의 크기가 커질 때마다 채울 수 있는 경우의 수는 일정한 규칙을 가지고 증가한다. N이 1일 때부터 차례대로 확인해보자 N = 1일 때 N이 1일 때는 1X2 직사각형 한 개로 이루어진 경우밖에 없으므로 1이다. N=2일 때 N이 2일 때는 (1X2 사..

-10,000 ~ 10,000 사이의 정수 N개가 입력으로 들어오면, 숫자 입력이 차례로 들어올 때마다 중앙값을 출력하는 문제다. ex) input : 3 6 8 4 5 6 2 output : 3 3 6 4 5 5 5 입력이 짝수개가 들어왔을 때는 중간의 두 수중 작은 수를 출력한다. 시간 복잡도: O(NlogN) 풀이 방법 출력해야 하는 값은 중앙값이다. 제일 간단히 중앙값을 찾는 방법은, 입력이 들어올 때마다 들어온 입력값들을 정렬한 후에 가운데 값을 출력하는 것이지만 그러면 매 입력마다 O(NlogN)의 시간이 걸리고 총 O(N^2 * logN)의 시간이 걸려서 시간 초과가 발생한다. Heap 자료구조를 이용하면 삽입, 삭제를 O(logN) 시간에 할 수 있으며 구현 방법에 따라 MinHeap, M..

입력으로 체스판의 크기 M * M, 나이트의 시작 위치, 이동하고자 하는 위치가 주어진다. 이때 나이트가 목적지까지 가는데 걸리는 최소 이동 횟수를 구하는 문제다. 시간 복잡도: O(M^2) 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 방법 나이트가 한번 이동할 때 갈 수 있는 위치는 다음과 같다. 총 8위치로 이동할 수 있으며 그때의 x, y좌표 변화는 위의 식과 같다. (체스판의 숫자는 dx, dy배열에서의 index) 체스판의 각 위치에 대응하는 M * M 크기의 2차원 배열을 선언하고, 값으로 ..

Firebase 프로젝트를 생성하면 편리하게 정적 웹 호스팅을 진행할 수 있다. 이번에 TodoList를 만들며 Firebase의 Auth, Firestore 서비스를 활용했는데 호스팅도 지원해서 한번 시도해봤다. 순서는 다음과 같다. (프로젝트는 노마드코더 사이트의 트위터 클론 코딩을 참고해서 진행했다.) 1. Firebase의 콘솔로 이동해 프로젝트를 호스팅 할 프로젝트를 선택한다. 2. 호스팅 탭으로 이동해 "Get Started"버튼을 누른다. 3. 호스팅 안내가 나오는데, 설명에 따라서 firebase-tools 모듈을 설치한다. 4. 프로젝트의 Root Directory로 이동해 아래 커맨드를 실행한다. 이때 login 할 때의 계정은 Firebase 계정을 사용하면 된다. 로그인할 때 이메일..