https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이) 어제 풀었던 문제와 같이, 매개 변수 탐색 알고리즘을 사용해야 한다. 트리 길이를 입력받을 때 제일 큰 값을 end의 값으로 설정해두고, start를 0으로 설정한다. 그리고 구한 start와 end 값으로 이분탐색을 해 나가면서 최댓값을 찾아내면 된다. #include #include #include #include using namespace st..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 단순히 이분탐색이겠지 했는데, 매개 변수 탐색이라는 알고리즘을 사용해서 푸는 문제였습니다. 매개 변수 탐색은 추후에 자료구조에 정리해서 올릴 예정입니다. 여기서 코드는 다 짯는데 계속 틀려서 무슨 문제인지 확인해본 결과 K=3 N=3 300 300 300 이 입력될 경우, 단순하게 end = max 로 코드를 짤 경우 299가 출력되는 결과가 존재하더라구요. 그래서 e..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 생각보다 쉽게 풀려서 다행인 문제였습니다. 단순하게 덱을 어떻게 쓸 줄 안다면 쉽게 푸실 수 있는 문제인 것 같습니다. 여기서 여건은 문자열 파싱을 어떻게 하느냐가 제일 중요했던 것 같습니다. 파싱 함수는 인터넷에 돌아다니는 함수를 긁어서 사용했습니다. #include #include #include #include #include using namespace std; vector split(string str, char delimiter); int m..
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 어제부터 다시 시작한 하루 필수 1문제를 시작했습니다. 확실히 오랜만에 푸는거라 머리가 제대로 안돌아가더라구요. 이 문제는 인덱스를 구해서 이분법을 통해 풀었습니다. 중앙 보다 작은 인덱스면 2번, 크면 3번이 작동하도록 했습니다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false)..
단순히 K번째가 아닌 숫자는 다시 Queue에 pop해서 push 해주면 되는 문제이다. K번째 일 경우에는 pop을 해준다 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cout.tie(nullptr); queue t1; int i = 1, count = 0; int N, K; cin >> N >> K; for (int i = 1; i
그냥 단순한 Queue를 쓸 수 있냐고 물어보는 문제입니다. 문장에 나와있는 그대로를 코드로 구현하면 되는 간단한 문제입니다. https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net #include #include using namespace std; int main() { ios::sync_with_stdio(false); cout.tie(nullptr); queue t1; int n; cin >> n; for (int i = 1; i
https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net Stack STL를 활용하여 풀었습니다. 중요한 부분은 Check 부분인데, len 값과 bal.top()이 같을 경우에 더해주고, 나머지는 이미 더한 값이기 때문에 나눠줍니다. 이부분을 이해하는 것이 제일 중요했던 것 같습니다. #include #include #include using namespace std; stack bal; char len = 0; int total = 0; int t..
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net Stack STL를 활용하여 풀었습니다. 길이를 활용하여 '(' 뒤에 바로 ')'가 나오면 stack의 사이즈를 체크하여 잘려진 만큼 더하였고, 그 이외의 경우에는 그냥 pop을 하여 막대기에서 제외하였습니다. 의사코드 더보기 if( c == '(' ){ 푸쉬하여 넣고 갯수를 하나 늘린다. 그리고 (를 넣엇다는 것을 체크해준다. } else if ( c == ')' ){ if( '('뒤에 바로 오는지 체크 ..