https://www.acmicpc.net/problem/5430 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케..
Koala - 10기/코딩테스트 준비 스터디
풀이 주어진 문자열의 괄호쌍이 맞는지확인하는 문제이다. 변수 t를 입력받는다. t는 이후에 입력될 문자열의 개수를 나타낸다. bool isValid = true;를 통해 문자열의 괄호 짝이 맞는지를 저장하는 변수를 초기화합니다. str[i]가 '('인 경우, 스택에 '('를 push한다. str[i]가 ')'인 경우, 스택이 비어있거나 top이 '('가 아닌 경우, isValid를 false로 변경하고 break한다. 그렇지 않은 경우, 스택에서 '('를 pop한다. for문이 끝난 후, 스택이 비어있지 않은 경우, isValid를 false로 변경한다. isValid가 true인 경우, "YES"를 출력하고 그렇지 않은 경우, "NO"를 출력한다. 코드 #include #include #include ..
백준 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..
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..
문제 링크 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..
