![]()
문제 https://www.acmicpc.net/problem/1918 풀이 중위표기식에서 후위표기식으로 변환하는 것은 스택을 활용하여 풀 수 있다. 후위표기식의 방식에 따라, 계산할 문자를 먼저 문자열에 두고 기호는 스택에 넣어두었다가 출력하면 된다. 하지만, 연산자의 우선순위에 의해 추가적으로 고려해주어야 한다. 우선순위가 더 낮은 연산자가 나오면 더 높은 연산자를 먼저 처리해준다. 또한, 괄호가 나오는 경우 괄호가 닫히는 순간에 괄호가 시작되었던 부분까지 고려하여 변환하면 된다. 코드 formula = input() precedence = {'+': 1, '-': 1, '*': 2, '/': 2} stack = [] postfix = '' for c in formula: if c.isalpha():..
문제 https://www.acmicpc.net/problem/2789 2789번: 유학 금지 아주 멀리 떨어져 있는 작은 나라가 있다. 이 나라에서 가장 공부를 잘하는 학생들은 모두 다른 나라로 유학을 간다. 정부는 최고의 학생들이 자꾸 유학을 가는 이유를 찾으려고 했다. 하지만, www.acmicpc.net 소스코드 word = input() cambridge_letters = set("CAMBRIDGE") filtered_word = "" for letter in word: if letter not in cambridge_letters: filtered_word += letter print(filtered_word) 문제풀이 1. 사용자로부터 입력 단어를 받아 'word'변수에 저장 2. "CAMB..
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/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 커서를 기준으로 왼쪽, 오른쪽을 나누어 저장하기 위해 deque를 생성한다. (왼쪽 deque | 오른쪽 deque) 입력받은 문자열을 for문으로 하나씩 확인한다. - 왼쪽 deque이 비어있지 않고, '-'라면 왼쪽 deque를 pop 한다. - 왼쪽 deque이 비어있지 않고, ''라면 오른쪽 deque에서 popleft 한 값을 왼쪽 deque에 append 한다. - 위..
![]()
문제 해설 절대값 힙이라는 자료구조를 우선순위 큐로 만들어 구현했습니다. 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/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가 풍선 하나를 만드는 데 ..
![]()
문제 https://www.acmicpc.net/problem/11441 풀이 주어진 구간의 합 구하기는 누적합을 활용하여 풀 수 있다. 누적합을 구한 뒤, 주어진 구간에 맞춰 일부 구간을 빼주면 된다. 만약 구간이 1부터 시작이 아닌 3~4라면, 1~4에서 1~2를 빼주면 남은 것은 3~4이다. 해당 원리로 주어진 구간에 대해 계산해주면 된다. 코드 N = int(input()) A = [0] + list(map(int, input().split())) M = int(input()) sections = [list(map(int, input().split())) for _ in range(M)] psum = [0]*(N+1) for i in range(1,N+1): psum[i] = psum[i-1]+A..
