문제 https://www.acmicpc.net/problem/1700 Algorithm그리디 알고리즘cntK_list 에 각 전기용품마다 사용 순서를 따로 deque로 저장한다.그리디하게 해결하기 위해,1. 멀티탭에 플러그가 꽂혀 있고, 해당 전기용품이 꽂혀있는지2. 그렇지않다면 멀티탭에 공간이 남아있는지3. 그렇지 않다면 멀티탭을 정렬한 후, 하나를 뽑는 후 새로 꽂는다. 이 때, 남은 전기용품의 순서를 기준으로 정렬한다. Codefrom collections import dequeinput = __import__('sys').stdin.readlineN, K = map(int, input().rstrip().split())K_list = deque(list(map(int, input().rst..
전체 글
항공대 알고리즘 동아리 Koala 🥰문제 https://www.acmicpc.net/problem/18111문제팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.좌표 (i,..
https://www.acmicpc.net/problem/8958알고리즘연속된 기호, 숫자를 세는 조건은 무엇일까? 또한 지금까지 연속된 기호, 수가 몇개인지 세기 위해선 어떻게 해야 할까?많은 방법이 있겠지만 이 문제에서는 이번 기호가 'O'라면, 분기를 나누어 '이전 기호'가 'X' 라면 연속된 횟수 1로 바꾸거나,그게 아니라면 계속해서 연속 횟수 c를 하나 증가시키는 방법을 사용했다. 그 이외의 경우라면, 현재 기호가 'X'이므로 c를 0으로 초기화했다. 점수를 계산하기 위해선 '현재까지의 O 수'를 세어야 하는데 이 역할을 cnt로 대신했다. 또한 이전 원소를 체크하기 때문에 index가 0번째인 원소는 c를 1로 고정하도록 예외 처리 해 주었다.코드input = __import__('sys')...
문제 https://www.acmicpc.net/problem/1890 Algorithm1. 처음엔 재귀함수를 사용해서 백트래킹으로 완전탐색을 시도했는데 시간 초과가 발생했다.2. DP를 사용하여 각 타일에 올 수 있는 경우의 수만 체크하여 각 타일에 갈때마다 dp 이중 배열의 값을 더해줬다. Codeimport java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;public class Main { private static Buff..
https://www.acmicpc.net/problem/1965알고리즘 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자에 넣을 수 있고, 한 번에 넣을 수 잇는 최대의 상자 개수를 찾는 코드를 구성해야 하므로, 해당 수열에서 가장 길이가 긴 증가하는 수열을 찾으면 된다. dp배열을 만들고, i번째 원소보다 앞에 있는 원소(0 ~ i-1)들중에 i번째 원소보다 작은 원소의 개수를 카운팅해주어 dp배열에 저장하는 방식으로 구성하였다.https://www.acmicpc.net/problem/11053해당 문제와 코드가 유사하다.코드import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int,inp..
문제 https://www.acmicpc.net/problem/11726 Algorithm규칙을 찾기 위해 n=1인 경우부터 세보니, n=k일 때 그 경우의 수는 (n = k-2 일 때의 경우의 수) + (n = k-1 일 때의 경우의 수)와 같다. Code#include using namespace std;int main(){ int n; cin >> n; int dp[1001] = {0}; dp[1] = 1; dp[2] = 2; for (int i=3;i
문제요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레드카드오렌지카드퍼플카드블루카드청록카드그린카드그레이카드카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드..
https://www.acmicpc.net/problem/1915입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.출력첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 코드n, m = map(int, input().split())dp = [[0]*m for _ in range(n)]arr = [list(map(int, input())) for _ in range(n)]ans = 0for i in range(0, n): for j in range(0, m): if arr[i][j] == 1: if i == 0 or j == 0: dp[i][j] = 1 els..
https://www.acmicpc.net/problem/2618유형다이나믹 프로그래밍문제어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다.모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, ..
https://www.acmicpc.net/problem/14495접근 방법f(1) = f(2) = f(3) = 1 이므로 미리 초기화, n을 입력받아 n번째 피보나치 비스무리한 수를 출력해야 하므로, vector로 선언(배열로 해도 굳이 상관은 없을듯)f(n) = f(n-1) + f(n-3) 이므로, v[i] = v[i-1] + v[i-3] 으로 반복문을 돌며 n번째 비스무리한 수까지 계산 코드#include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; if (n == 1 || n == 2 || ..
4435번: 중간계 전쟁알고리즘:DFS(깊이 우선 탐색)를 활용하여 백트래킹으로 문제를 해결한다. 이를 통해 각 전투의 결과를 저장하고 출력하도록 구현하였다.코드:G_S = [1, 2, 3, 3, 4, 10] S_S = [1, 2, 2, 2, 3, 5, 10] def cbr(g_c, s_c): g_t = sum(g_c[i] * G_S[i] for i in range(len(G_S))) s_t = sum(s_c[i] * S_S[i] for i in range(len(S_S))) # 결과 비교 if g_t > s_t: return "Good triumphs over Evil" elif g_t
문제 https://www.acmicpc.net/problem/17142 Algorithm그리디 알고리즘, 정렬일반적으로 A를 선택하는 것이 더 최선일 것이라 가정하고,예외적으로 B가 최선인 경우, 그리고 금액에 맞도록 선택 횟수를 조정 한 뒤,메뉴를 1. A, B의 차이가 최대 2. A의 맛, 3. B의 맛을 기준으로 내림차순하여 그리디하게 선택한다. Codeinput = __import__('sys').stdin.readlineN,X = map(int, input().rstrip().split())menu_list = [list(map(int, input().rstrip().split())) for i in range(N)]cnt_A, cnt_B = 0, 0ans = 0for i in menu_..