문제 https://www.acmicpc.net/problem/11478 Algorithm1. 처음엔 재귀를 이용해서 앞에서 부터 중복되는 문자열이 있으면 무시하는 방식으로 풀려 했는데 시간 초과 발생 (코드 짜는데 20분)2. Set 이용해서 푸니까 바로 풀림 (코드 짜는데 1분)3. 범위 보고 시간 복잡도 구하고 된다 싶으면 그냥 쉬운 개념 부터 쓰자... Codeimport java.io.*;import java.util.*;public class Main { static HashSet hashSet = new HashSet(); static int ans = 0; public static void main(String args[]) throws IOException { Buffer..
전체 글
항공대 알고리즘 동아리 Koala 🥰
https://www.acmicpc.net/problem/1918문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차..
https://www.acmicpc.net/problem/17413알고리즘단어를 뒤집어서 출력하면 되는 문제이다. 하지만, 태그안에 있는 단어는 뒤집지 않아야 한다.단어를 구분하는 기준은 공백과 태그이므로 이를 기준으로 코드를 구성하였다.태그가 들어오면 단어를 뒤집지 말고 출력해야 하므로 스택에 넣지않고 계속 ans에 붙여준다. flag를 설정해서 다음 단어가 태그안에 있다는 것을 표시해주고 태그가 끝나면 flag를 비활성화 해준다.공백이 나오면 stack에 있는 단어들을 ans에 붙여준다.문제에서 문자열의 끝은 공백이 아니므로, 마지막에 한번더 스택을 검사해서 단어를 붙여준다.코드import sysinput = sys.stdin.readlineans = ''stack = []s = input().str..
N = int(input())arr = []for i in range(N): arr.append(list(map(int, input().split())))arr.sort(key = lambda x: [-x[0], x[1]])cnt = 0for i in range(N): if arr[4][0] == arr[i][0] and arr[4][1] https://www.acmicpc.net/problem/15905
https://www.acmicpc.net/problem/13904입력첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.출력얻을 수 있는 점수의 최댓값을 출력한다.문제 코드from heapq import heappush, heappophq = []n = int(input())point = 0maxDay = 0for _ in range(n): d, p = map(int, input().split()) home = [-p, d] maxDay = max(maxDay, d) heappush(hq,..
문제 https://www.acmicpc.net/problem/1966 Algorithm Codet = int(input())for _ in range(t): n, m = map(int, input().split()) data = list(map(int, input().split())) result = 1 while data: if data[0] 0 else len(data) - 1 print(result)
문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.코드def get_prefix_sum(N, numbers): prefix_sum = [0] * (N + 1) for i in range(1, N + 1): prefix_sum[i] = prefix_sum[i-1] + numbers[i-1] return prefix_sumd..
https://www.acmicpc.net/problem/1072알고리즘이진탐색을 이용하는 문제이다. Z(승률)이 변하는 최소한의 게임 판수를 구하는데, 이때 승률이 변하지 않는 경우를 확인해주어야 한다.Z 계산시 버림한다고 하였으므로, 99퍼 이상은 아무리 계속 승리를 해도 변하지 않으므로 Threshold를 Z = 99로 잡고 코드를 구성하였다.게임 판수를 이진탐색의 right, 0판을 left로 잡고 이분탐색을 하면서 승률의 변동이 있는지 확인해준다. 승률이 변했다면 판수를 더 줄여서 확인해 보아야하므로 r = mid-1을 통해 다시 이진탐색을 해주고, 승률이 변하지 않았다면 판수를 더 늘려서 확인해 보아야하므로 l = mid+1을 통해 이진탐색을 계속한다.코드import sysinput = sys..
https://www.acmicpc.net/problem/17951입력첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)출력현수가 받을 수 있는 최대 점수를 출력한다. 코드n, k = map(int, input().split())li = list(map(int, input().split()))left = min(li)right = sum(li)cnt = 0while left = mid: cnt += 1 result = 0 if cnt >= k: left = mid + 1 else: ..
문제 https://www.acmicpc.net/problem/1939 Algorithm도시와 도시 사이에 연결된 다리로 옮길 수 있는 최대 중량값은 DFS로 구하면 될 것 같다.- 이진탐색을 통해 중량이 A에서 B로 이동할 수 있는지 탐색- 가능하면 중량을 더하고 다시 탐색- 가능하면 중량을 줄이고 다시 탐색- 탐색이 종료되면 최대 중량을 출력 Codeimport java.io.*;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { static int ans; static List[] list; static boolean[] check; public static void..
문제 https://www.acmicpc.net/problem/16401 Algorithm Code#include #include #include using namespace std;int main(){ int m, n, input; cin >> m >> n; vector snacks; for(int i=0; i> input; snacks.push_back(input); } sort(snacks.begin(), snacks.end()); int low = 1; int high = snacks[n-1]; int result = 0; while(low
2352번: 반도체 설계접근 방법연결선이 꼬이면 안되기 때문에, 가장 긴 증가하는 부분 순열 (LIS) 알고리즘을 사용하기로 결정이때 dp로 접근하게 되면 시간 복잡도가 O(n^2)이기에 시간 초과가 발생했다.여기에서는 시간 복잡도를 O(n log n)으로 줄이기 위해서 이분탐색을 이용하기로 결정한다.vector v(n) -> 연결되어야 하는 포트 번호들을 입력받는 배열vector dp -> 증가하는 부분 수열에 들어갈 수를 최적의 값으로 유지하기 위한 배열int pos -> 반복문을 거치는 현재 원소(v[i])가 dp에 들어갈 위치를 결정하는 역할을 한다.같은 숫자는 존재하지 않기에 binary_search 함수를 구현, dp에 들어갈 위치를 이분 탐색으로 결정, 반환하는 값(ans)이 dp의 사이즈와..