문제 풀이/백준(BOJ)201 [C++] 백준 11279번 : 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제 풀이 힙을 구현하는 문제이다. 우선순위 큐를 사용하면 간단하게 해결할 수 있다. 느낀 점 기본적인 자료구조이다. 코드 #include #include using namespace std; int n; priority_queue pq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; while (n--) {.. 2021. 11. 12. [C++] 백준 14425번 : 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 풀이 기본 자료구조 문제이다. n번 입력받은 문자열 중 m번 입력한 문자열이 있는지 체크하는 문제이다. Set으로 구현하면 매우 쉽다! 느낀 점 기본적인 자료구조 문제이다. 코드 #include #include #include using namespace std; int n, m, cnt = 0; set s; int main() { ios_base::sync_.. 2021. 11. 6. [C++] 백준 2075번 : N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 우선순위 큐로 풀 수 있는 문제이다. 우선순위 큐를 올림차순으로 구현한다. N개의 숫자만 가지고 있으면 되기 때문에 큐의 크기가 N보다 커지면 가장 작은 값을 pop 하면 된다. 올림차순이라서 단순하게 pop만 하면 되고 모든 반복이 끝나면 top을 출력하면 된다. 느낀 점 처음에는 모든 값을 우선순위 큐에 넣었지만 메모리 초과가 발생하였다. N개의 숫자만 가지고 있으면 되는 점을 이해하면 쉽.. 2021. 10. 26. [C++] 백준 7662번 : 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제풀이 멀티셋, 우선순위 큐로 풀 수 있는 문제이다. 명령어는 두 가지로 우선순위 큐에 값을 집어넣는 'I'와 값을 pop 하는 'D'가 있다. 우선순위 큐를 통해서 구현했기 때문에 각각 maxheap, minheap으로 구현했다. (내림차순, 오름차순) 큐가 두개라서 값을 pop 할 때 두 개의 큐에서 모두 처리가 돼야 하기 때문에 상태를 나타내는 배열을 추가했다. 'I' 명령어는 단순하게.. 2021. 10. 26. [C++] 백준 1620번 : 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 풀이 맵으로 해결 가능한 문제이다! 포켓몬의 이름과 번호를 받는 맵과 반대로 구현된 맵 두 개를 구현해서 해결했다. 느낀 점 어렵지 않은 문제였다. 다만 두 개를 구현했다는 점에서 메모리적 측면에서 잘 구현했는지 모르겠다. 코드 #include #include #include #include using namespace std; int n, m; map dogam.. 2021. 10. 19. [C++] 백준 1918번 : 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 문제 풀이 스택의 대표적인 문제이다! 피연산자는 단순히 스트링에 추가해주면 된다. 연산자인 '+', '-', '/', '*', '(', ')' 에 대해선 추가적인 작업이 필요하다. 1. '(' 은 무조건 스택에 push 한다. 2. 각 연산자마다 우선순위가 존재한다. '*', '/' 이 가장 높고, 괄호들이 가장 낮다. 3. 스택의 top보다 지금 확인하는 연산자의 우선순위가 높다면 그냥.. 2021. 10. 17. 이전 1 ··· 13 14 15 16 17 18 19 ··· 34 다음