문제1026번: 보물문제 이해길이가 N인 정수 배열 A와 BS = A[0] × B[0] + ... + A[N-1] × B[N-1]S의 값을 최소화하기 위해 A의 수 재배열, B의 수는 재배열 XA의 수를 재배열하나 A, B의 수를 재배열하나 결과는 달라지지 않음A의 수는 모든 B의 수와 연산이 될 수 있기 때문풀이B의 가장 큰 수를 A의 가장 작은 수와 곱하게 만들어 최솟값 계산A와 B를 모두 조작해도 관계없기 때문에 A와 B를 정렬하여 계산A를 내림차순으로 정렬B를 오름차순으로 정렬A와 B의 각 원소의 곱을 계산코드import sysinput = sys.stdin.readlinen = int(input())A = sorted(list(map(int, input().split())), reverse=Tr..
그리디개념 정리그리디 알고리즘현재 상황에서 지금 당장 좋은 것만 고르는 방법매 순간 가장 좋은 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 문제 유형다른 알고리즘에 비해 "사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형"다익스트라 알고리즘 (최단 경로)과 같은 특이 케이스를 제외하고는 암기로 대처하기가 어려움보통 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구예제 : 거스름돈문제당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할..
문제17299번: 오등큰수문제 이해크기가 N인 수열 A = A1, A2, A3, ..., AN이고, 각 원소 Ai에 대한 오등큰수 NGF(i)를 구함Ai가 수열 A에 등장한 횟수 = F(Ai)Ai의 오등큰수는 오른쪽에 있고 수열 A에서 등장한 횟수가 F(Ai) 보다 큰 수 중 가장 왼쪽에 있는 수, 없으면 -1문제 예시 설명N = 7 # 수열의 크기A = [1, 1, 2, 3, 4, 2, 1] # 크기가 N인 수열 AF(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1 # 각 숫자가 등장한 횟수A1 = 1, 오른쪽에 F(1)보다 큰 수는 없으므로 -1A2 = 1, 오른쪽에 F(1)보다 큰 수는 없으므로 -1A3 = 2, 오른쪽에 F(2)보다 큰 수는 1A4 = 3, 오른쪽에 F(3)..
문제24511번: queuestack문제 이해queuestack : 1, 2, ..., N번의 자료구조(큐 or 스택)가 나열되어 있으며 각 자료구조에는 한 개의 원소가 들어 있음queuestack의 작동x0 입력x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x1x1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x2...xn-1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 xnxn 반환입력받은 M개의 정수(C)를 queuestack에 차례로 삽입했을 때의 반환값(xn)을 출력출력 예시자료구조가 어떤 형태인지 글로는 한 번에 와닿지는 않는다. 첫 번째 출력 예시로 확인해 보자.N = 4A = [0, 1, 1, 0]B ..