본문 바로가기

BOJ157

[C++] 백준 1935번 : 후위 표기식2 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 문제 풀이 대표적인 스택 문제이다. 보통 중위 표기식을 후위 표기식으로 바꿀 때에는 연산자를 스택에 넣어서 구현한다. 하지만 이렇게 계산하는 경우에는 스택에 피연산자를 넣어야 한다. 반복문을 통해서 String을 돌아볼 건데 str[i]가 연산자라면 스택 맨위의 피연산자 두 개를 가져와서 연산을 해준다. 스택은 먼저 들어간 data가 나중에 나오는 구조이기 때문에 나중에 pop 하는 값.. 2021. 9. 28.
[C++] 백준 1158번 : 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 풀이 https://codinghejow.tistory.com/91와 같은 문제이다! 느낀 점 이번에 코테 준비를 하면서 다시 풀어봤던 문제이다. 이번에 한번 정리함으로써 큐에 대한 이해도가 확실하게 향상된 것 같다. 코드 #include #include using namespace std; int n, k; queue q; void func(int n, int k) { for (int i = 1; i 2021. 9. 24.
[C++] 백준 16236번 : 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 문제에서 중요한 것은 2가지이다. 바로, BFS 구현과 우선순위를 정하는 것. 아기 상어의 정보와 물고기의 정보를 구조체로 구현했다. 구조체라는 틀에서 모든 정보를 가지기 위함이다. 함수 BFS에서는 배열 dx와 dy를 통해서 상하좌우를 한 칸씩 탐색한다. 탐색 도중에 나올 수 있는 경우는 4가지로, 1. 빈 칸인 경우 : 방문했음을 체크하고, 이동거리만 추가해준다. 2. 아기상.. 2021. 9. 15.
[C++] 백준 18111번 : 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 기본적인 브루트 포스 문제이다. 기준이 되는 높이에서 걸리는 시간을 구해서 계속 비교해 가장 작은 값을 출력하면 된다. 입력받을 때 최소 높이와 최대 높이를 구해 놈으로 반복 횟수를 최소화할 수 있다. 최소가 되는 시간이 여러 경우가 있을 수 있어 그 중 가장 높은 높이일 때를 출력해야 한다. (제거 시간 + 쌓는 시간)이 최소 시간과 같을 때도 최신화 함으로 가장 높은 높이를 출력할.. 2021. 8. 30.
[C++] 백준 2805번 : 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 이전 문제(BOJ 1654 : 나무 자르기)와 비슷한 문제이다. 다른 점은 딱 맞아떨어지지 않는다는 것이다. 적어도 M미터의 높이의 나무를 가져가야 한다. 즉, 1미터의 나무가 필요할 때 {1, 2, 2} 높이의 나무들이 주어진다면 1미터의 높이에서 잘라야 한다. 느낀 점 삼항 연산자를 사용해서 중간의 번거로운 계산을 줄였다! 이전과 코드가 똑같아.. 2021. 8. 5.
[C++] 백준 1654번 : 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 N개의 랜선을 만드는데 그 길이를 최대로 만들어야 한다. 브루트 포스로 풀 수 있지만 무조건 시간 초과가 발생한다. 이진 탐색으로 탐색 횟수를 줄여야 한다. 가장 긴 길이와 가장 짧은 길이(1) 사이에 답이 존재한다. 이분 탐색을 통해서 그 중간 값과 비교할 텐데 잘랐을 경우 N개가 되는 값이 여러 개 존재한다. 그중에서 최댓값을 찾아야 해서 잘랐을 때 N개.. 2021. 8. 5.

티스토리툴바