백준 17298. 오큰수 첫 번째 시도 from collections import deque import sys input = sys.stdin.readline ans = [] t = int(input()) dq = deque((map(int, input().split()))) for i in range(t): cmp = dq.popleft() res = [] for elem in dq: if elem > cmp: res.append(elem) if len(res): ans.append(res[0]) else: ans.append(-1) print(*ans) 위 풀이로 접근하게 되면 O(N^2)이므로 시간 안에 문제를 풀 수 없다. 따라서 다른 풀이가 필요하다. 두 번째 시도 import sys inpu..
Koala - 10기
2346번: 풍선 터뜨리기 (acmicpc.net) 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 코드 해설 풍선의 수 N, 풍선 안 쪽지에 적힌 수를 입력 받는 덱 next를 입력받음 arr는 1 ~ N개의 풍선을 순서대로 덱으로 구현 arr 내의 원소가 하나라도 있다면 while문 반복 터트릴 풍선을 항상 arr의 index 0으로 데려올 것이기 때문에 풍선의 번호를 출력 후 arr에서 popleft() next에서도 없애야하기 때문에 popleft와 동시에 값을 temp에 저장 ..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 전형적인 bfs 문제를 약간 꼬아서 낸 것이다. 최단 거리이지만 기존의 상하좌우가 아닌 특별한 기준에 따라 bfs를 돌아야한다. 코드 # 맥주 마시면서 걸어가기 # 복습 횟수:1, 00:30:00, 복습필요X import sys from collections import deque si = sys.stdin.readline T = int(si()) def bfs(): visited = ..
https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 해석 해당 문제는 구간을 주고, 그 구간 내에서 특정 조건을 만족하는 경우를 '세어' 달라고 했다. 만약 일반적인 경우처럼 크게 입력값을 받는 loop로 묶고, 그 안에서 입력받은 것에 따라 x부터 y까지 슬라이싱을 하고, 슬라이싱한 배열을 sum 함수로 돌린다면 시간복잡도가 O(Q*N*(y-x))이다. 최악의 경우 이미 0.5초를 훌쩍 넘겨 버리므로, 다른 방안을 고려해야 한다. 마침 ..
1. 문제 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 2. 해결방안 당연한 말이지만 .. 누적합을 사용했다 prefix_sum 이라는 배열을 통해 원소를 하나씩 탐색하며 그 원소를 이전까지 더해준 값에 더해서 넣어줬다 ~ ! 그리고 i~j 까지의 합은 prefix_sum[j] - prefix_sum[i-1] !! 3. 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) nums = list(map(int,i..
Problem Solution 1. 이름 길이를 저장할 변수 len과 점수를 저장할 sum과 이름을 저장할 name을 선언한다. 2. 이름의 길이와 이름을 입력 받는다. 3. 이름의 길이만큼 for 반복문을 활용하여 반복 수행하도록 한다. 3-1. tmp라는 변수를 만들고 이름의 한 글자에서 'A'를 뺀 다음 1을 더한 값을 저장한다. 3-2. sum에 tmp값을 더한다. 4. sum값을 출력한다. Answer #include #include using namespace std; int main() { int len; int sum = 0; string name; cin >> len >> name; for(int i = 0; i < len; i++) { int tmp = name[i]-'A'+1; sum..
문제 링크 https://www.acmicpc.net/problem/17951 17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다. www.acmicpc.net 코드 n,k = map(int,input().split()) score = list(map(int,input().split())) start,end = min(score),sum(score)# 받을 수 있는 최저점수, 받을 수 있는 최대점수 result = 0 while start=mid:#받을 수 있는 최대점수를 넘으면 그룹으로 나눈다. partial_sum=0 group+=1 if group>=k:#그룹이 k 이상이면 mid..
https://www.acmicpc.net/problem/1184 문제 분석 난이도 플래티넘5 분류 누적합, 해시맵, 브루트포스 문제 문제 풀이 풀이 단순히 좌표 8개를 구해주는 경우 O(N^8) (50^8)으로 시간초과가 발생한다. 임의의 한 점을 잡고 그 점에 대해서 (좌상단,우하단), (우상단, 좌하단) 이렇게 탐색을 진행해주면 O(N^4)까지 줄일 수 있다. 임의의 기준점에 맞게 누적합을 잘 이용해 풀어주면 된다. 소스코드 from sys import stdin from collections import defaultdict from math import comb input=stdin.readline def getval(sx,sy,ex,ey): return presum[ey][ex]-presum[..
문제 https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 www.acmicpc.net Algorithm 이진탐색으로 해결했다. 여기서 이진탐색으로 구하고자 하는 값은 파닭에 넣을 파 한 조각의 길이이다. 파를 mid만큼 자를 때 만들 수 있는 파닭의 수 K는 각각의 파의 길이 O를 파닭에 넣을 파 한 조각의 길이의 추정값 mid로 나눈 몫의 합이고 라면에 넣을 파의 양은 O를 mid로 나눈 나머지의 합이다. 주문받은 파닭의 수가 ..
풀이방법 : 이분탐색 문제이다 먼저 배열을 입력받고 sort를 사용하여 오름차순으로 정렬한다 구현한 이분탐색코드 binary_search()함수를 활용해서 배열에서 해당된 값을 찾는다 binary_search()함수의 반환값을 출력한다 해당 값이 존재하면 1, 존재하지 않으면 0 나의 코드 : #include #include using namespace std; int a[100005]; int n; int binarysearch(int target) { int st = 0; int en = n - 1; while (st target) en = mid - 1; else return 1; } return 0; // st>en일경우 탈출 } int main(void) { ios::sync_with_stdio..
현재 가지고 있는 랜선의 갯수와 만들어야 하는 랜선의 갯수가 주어지고 이 후 차례로 현재 가지고 있는 랜선의 길이가 각 줄마다 입력된다. 이 때 원하는 랜선의 갯수를 최대의 길이로 만드는 법을 구해야 한다. 이 때 답에 해당하는 랜선의 길이는 원하는 랜선의 갯수마다 달라지고 주어지는 랜선의 갯수마다 달라져 쉽게 계산하는 방법은 떠오르지 않아 가능한 랜선의 길이를 탐색하는 이진탐색을 사용하였다. 모든 수를 탐색은 하지만 원하는 특정값 하나만 찾으면 되는 경우였기에 계산이 줄어드는 이진 탐색을 택하였다. import sys def main(): k, n = map(int, sys.stdin.readline().split()) line = [] for _ in range(k): line.append(int(s..
17179번: 케이크 자르기 (acmicpc.net) 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 소스코드 코드설명 N,M,L과 M개의 자를 수 있는 지점을 나타내는 정수 리스트 pnt, N명의 예상 친구 수를 나타내는 정수 리스트 frd 입력 frd 내의 자르는 횟수마다 반복 자를 수 있는 케이크의 길이를 기준으로 설정해 start는 1, end는 가장 긴 L, 답을 저장할 ans는 0으로 설정 mid는 start와 end 중간값, count는 fun(mid)..
