해킹왕 양선규

자료구조, 정렬 문제이다.메모리 제한이 걸려 있긴 한데, 메모리를 신경쓰지 않아도 풀리긴 한다.난 3가지 방식으로 풀어보았다. import java.io.*;import java.util.*;public class N번째_큰_수_2075 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); int[] table = new int[N*N]; /** 숫자를 하나의 배열로 전부 입력받기 */ int i..

처음 문제를 보고, 이분탐색인가? 그리디인가? 어떤 알고리즘이지? 고민했는데,결국 그냥 구현이었다. import java.io.*;import java.util.*;public class 창고_다각형_2304 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; /** * 가장 작은 창고 면적 구하기 * 한번 내려가면 다시 올라오면 안된다 * * 올라가기: 기존 높이로 쭉 진행하며, 높은 걸 만날때마다 올라간다 * 내려가기: 가장 높은 곳에 도달했다면, 내..

문제 자체는 시뮬레이션인데, 시뮬레이션 그대로 구현하면 무조건 시간 초과가 난다. 시간제한이 0.3초고, 삽입/삭제를 직접 수행할 경우 명령어가 50만개라서 50만 * 10만 하면 500억번 연산이라 자료구조를 잘 활용해야 한다.나는 ArrayDeque 2개를 활용했다. import java.io.*;import java.util.*;public class 에디터_1406_v2 { static ArrayDeque left = new ArrayDeque(); static ArrayDeque right = new ArrayDeque(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRead..

기본적인 피보나치 함수 문제이다. 일반적으로 재귀 또는 DP 형태로 풀 수 있다.이 문제에서는 시간제한이 0.25초로 짧기 때문에 DP로 풀어야 한다. import java.io.*;public class Main { static int zeroResult = 0; static int oneResult = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for (int i = 0; i 첫 번째 시도 코드다. 최대 N이 40이라 ..

그리디 문제이다. 살짝 어려웠다. 난 2가지 방식으로 풀었는데, 의문점이 있다. import sysinput = sys.stdin.readline"""1. 큰 값 순서대로 정렬2. 현재 가장 큰 값 기준으로, 원본 리스트 역순 순회하며 가장 큰 값 찾기3. 찾았다면, 가장 큰 값 포함한 좌측 값 전부 사서 큰값에 팔기4. 원본리스트에서 방금 사용된 값을 전부 없애기5. 반복현재 가장 큰 값 idx가 while문당 1씩 증가하는데, 이거 좀 비효율이다. 이후에 올 큰값들이 지워지면 쓸모없어지기 때문따라서 가장 큰 값 리스트에서도 값들을 지워주고, 항상 0으로 인덱싱 하면 될 것 같은데 귀찮다.[1, 3, 1, 10, 2, 9, 3, 10, 5][10, 9, 5, 3, 2, 1]"""for _ in rang..

그리디 문제이다. 실버 3보다는 좀 더 쉬운 것 같다. 시간복잡도도 고려할 필요 없다. 난 고려하긴 했지만. import sysinput = sys.stdin.readline"""0이 앞에 최대한 많아야 한다1은 앞부터 지우고0은 뒤부터 지우면 되지않나1. 리스트로 받아서 , 지우지 말고 -1로 교체 (지우는 연산 오버헤드 방지)2. 앞부터 -1이 아닐 경우 출력"""S = list(map(int, input().strip()))"""0, 1 개수 세기"""count = [0] * 2 # 0의 개수, 1의 개수 저장할 리스트for num in S: if num == 0: count[0] += 1 else: count[1] += 1"""앞부터 1 지우기"""delete..

구현, 정렬 문제이다. 입력값이 다양하게 주어져서 헷갈리고, 관리해야 하는 데이터가 많아 헷갈린다.그러나 정렬 조건만 제대로 숙지한다면 크게 어렵지 않게 풀 수 있는 문제이다. import sysinput = sys.stdin.readline"""k개의 문제를 풀면 0점 ~ 100점 획득함 -> 팀ID/문제번호/점수 저장한 문제를 여러 번 제출하면, 최고점수가 최종점수 -> 제출안하면 0점팀의 점수는 각 문제 최종 점수의 합점수가 동일한 팀이 있을 경우1. 점수가 같으면, 제출 횟수가 적은 팀이 이긴다2. 점수와 제출 횟수가 같으면, 마지막 제출 시간이 빠른 팀이 이긴다정렬 조건: 점수 높은순, 제출횟수 적은순, 제출시간 빠른순"""for _ in range(int(input())): """ ..

구현, 문자열 문제이다. 비슷한 단어가 될 수 있는 조건을 정확히 찾으면 쉬운 문제인데, 조건 하나를 빠뜨려서 조금 헤맸다. from collections import defaultdictimport sysinput = sys.stdin.readline"""길이가 2이상 차이나면 제외.1. 길이가 1차이나는 경우, 나머지 문자의 개수가 전부 같다면 비슷한 단어이다.2. 길이가 같은 경우, 모든 문자가 같으면 비슷한 단어이다.3. 길이가 같은 경우, 하나의 문자가 다르다면 비슷한 단어이다.-> 이 3가지 외에 만족하는 케이스는 없다."""N = int(input())ref = input().strip()ref_count = defaultdict(int)for key in ref: ref_count[k..

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다. import sysinput = sys.stdin.readline"""N: 식탁의 길이K: K 이하 거리 햄버거 먹기 가능table: 사람과 햄버거의 위치사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?K가 최대 10이니 가능할거같다. K 햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다."""def can_eat(idx, K): # 기준 (사람 또는 햄버거) point = table[idx] # idx 뒤로 K거리만큼 잘라낸다 (슬라이..

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다. import sysinput = sys.stdin.readline"""1. 모든 요청을 줄 수 있다면 다 준다2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다"""N = int(input())reqs = list(map(int, input().split()))budget = int(input())def calc(limit, arr): """ 상한가를 고려해, 지급해야 할 금액 계산 limit: 상한가 ..