https://www.acmicpc.net/problem/1874 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..
분류 전체보기
0. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 풀이 트럭이 다리에 올랐다가 다시 내려오는 과정에서 stack 자료 구조를 떠올렸지만 stack 자료 구조 자체에 (트럭, 상태) 값을 들여보내는 로직으로 한참 생각하다가 아이디어는 결국 인터넷에서 빌리고 만 문제였다 ㅠ.. 0과 트럭 무게를 이용하여 다리 위의 실제 트럭 상태를 저장하며 푸는 아이디어가 매우 중요하다 ! 2. 코드 아래는 시간초과 코드이다. from coll..
https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 알고리즘 분류 구현 자료 구조 그리디 알고리즘 시뮬레이션 우선순위 큐 문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후..
문제 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 커서를 기준으로 왼쪽, 오른쪽을 나누어 저장하기 위해 deque를 생성한다. (왼쪽 deque | 오른쪽 deque) 입력받은 문자열을 for문으로 하나씩 확인한다. - 왼쪽 deque이 비어있지 않고, '-'라면 왼쪽 deque를 pop 한다. - 왼쪽 deque이 비어있지 않고, ''라면 오른쪽 deque에서 popleft 한 값을 왼쪽 deque에 append 한다. - 위..
문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net Algorithm 1. num이하 숫자까지 스택에 넣기 2. num이랑 스택 맨 위 숫자가 동일하다면 제거 3.else문을 통해 스택 수열을 만들 수 없으므로 False 4. 스택 수열을 만들 수 있는지 여부에 따라 출력 Code count = 1 temp = True stack = [] op = [] N = ..
문제 해설 절대값 힙이라는 자료구조를 우선순위 큐로 만들어 구현했습니다. c++의 우선순위 큐는 가장 큰 값이 출력이 되는데, 절댓값이 가장 작은 값을 출력해야기에 -를 붙혀 push하였습니다. 그리고 연산자 오버로딩으로 절댓값이 같을 때 더 작은 수를 출력하도록 했습니다. 코드 #include using namespace std; struct cmp { bool operator()(int a, int b) { if (abs(a) == abs(b)) return a abs(b); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); priority_queue pq; int N; ci..
https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알..
문제 https://www.acmicpc.net/problem/1614 1614번: 영식이의 손가락 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으니 더 이상 사용할 수 없다. www.acmicpc.net 코드 #include using namespace std; #define LL long long int main() { LL f = 0; LL n = 0; cin >> f; cin >> n; LL ans = 0; if (n != 0) { if (f == 1 || f == 5) { ans += n * 8; if (f == 1) { cout
1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 코드 from heapq import heappush, heappop hq=[] n=int(input()) for _ in range(n): x=int(input()) heappush(hq, x) #마지막에 합쳐지는수는 어차피 동일 #대신 초반부터 적게 합치고 합쳐야함. ans=0 while(len(hq) !=1): a = heappop(hq) b = heappop(hq) ans += a+b..
문제 https://www.acmicpc.net/problem/14935 14935번: FA 정수 x가 FA수 라면 FA를 출력하고, 아니라면 NFA를 출력한다. www.acmicpc.net 문제 풀이 FA식을 반복하다 보면 무조건 한 자리수가 되며 한 자리수가 되면 값이 일정해진다. 자기자신 *1(한 자리수) = 자기자신 따라서 모든 수가 FA수이다. Code x = input() print("FA")
https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 코드 import sys n, k = map(int,sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) result = list() result.append(sum(a[:k])) for i in range(n - k): result.append(result[i] - a[i] + a[k+i])..
https://www.acmicpc.net/problem/15810 문제 전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다. 풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다. 대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다! 각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까? 풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다. 모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 ..
