알고리즘 Algorithm/백준 (BaekJoon) (9) 썸네일형 리스트형 백준 11866 : 요세푸스 문제 0 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 N과 K를 입력한 후, 1부터 N까지의 수 중 K번째인 수를 제거한 후 나머지 수도 반복하여 제거된 순서를 출력하는 문제입니다. 풀이 C++ stl에 있는 queue를 사용했습니다. K번째 수가 아니면 앞에 있는 수를 push한 후 pop을 합니다. K번째 수이면, 숫자를 출력한 후 pop을 진행합니다. 출력 양식을 맞추기 위해 숫자 출력과 pop을 한 후에 queue가 비어있으면 ","을 출력하지 않았습니다. 소스 코드 #include #include using namespace std; int main() { queue q; int N, K; scanf("%d%d", &N, &K); for (int i = 1; i 백준 2164 : 카드2 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 N을 입력한 후 1부터 N까지의 숫자가 써있는 카드를 가지고 맨 위 카드를 버린뒤 그 다음 맨위의 카드는 맨 아래로 이동하는 행위를 반복합니다. 이후 마지막에 남은 카드를 출력하는 문제입니다. 풀이 C++ STL에 있는 queue를 사용하였습니다. for문을 사용하여 queue의 size가 1이 될때까지 반복하였습니다. queue를 pop함으로써 카드를 버리고 front의 있는 값을 push하고 pop을 함으로써 맨 뒤로 이동시켰습니다. 소스 코드 #include #include using namespace std; int main() { queue q; int N; scanf("%d", &N); for (int i = 1; i 백준 18258 : 큐 2 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 입력 받을 케이스의 개수를 입력한 뒤 push, pop, empty, size, front, back 중 하나를 입력하여 queue에 대한 연산을 수행합니다. 풀이 C++ STL에 있는 queue를 사용하였습니다. 소스 코드 #include #include #include using namespace std; int main() { queue q; string str; char ptr[6]; int N = 0, num(0); scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%s", ptr); str = ptr; if(str == "push") { scanf("%d", &num); q.push(num).. 백준 17298 : 오큰수 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 N의 크기를 가지는 수열 A에 대해서 i번째의 수열의 오른쪽 수 중 가장 가까운 큰 수를 구하는 것입니다. 예를 들어, 3 5 2 7이라는 수열 A에 대해서 3의 오큰수는 오른쪽 수 5, 2, 7 중 가장 가까운(즉, 가장 왼쪽에 있는) 큰 수인 5입니다. 구할려는 오큰 수가 없을 시 -1을 반환합니다. 또한, 이 문제의 시간 복잡도는 \(O((nlogn))\)이하여야 합니다. 풀이 스택에 수를 넣는 대신 인덱스를 넣어서 바로 오른쪽에 오큰 수가 있는지 판단하는 방법으로 진행합니다. 바로 오른쪽에 있는 오큰수가 스택에 쌓여있는 모든 수의 오큰 수가 됩니다. 예를 들어, 9 5 4 8이라는 수열로 오큰 수를 구할 시 인덱스 2까지 push한 다음 바.. 백준 1874 : 스택 수열 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 1부터 n까지 차례대로 push또는 pop을 하여 입력한 수열과 똑같은지 비교하는 문제입니다. 즉 43을 만들기 위해 1부터 4까지는 push를 하고 pop을 2번 진행하면 됩니다. 이러한 진행 상황을 push는 '+', pop은 '-'으로 출력합니다. 풀이 1부터 차례대로 push를 하고 push를 한다는 '+'기호는 vector에 push_back합니다. 그리고 수열과 같은 수가 나타나면 즉시 pop을 하여 꺼내고 다음 수를 비교합니다. 이 점을 반복문으로 구현하였고, 스택이 비어있을 때 vector에 있는 요소들을 출력합니다. n이 될 때까지 진행하면서 비어있지 않는다는 뜻은 수열을 만들 수 없다는 뜻이 됩니다. 소스 코드 #include #.. 백준 4949 : 균형잡힌 세상 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 백준 9012 : 괄호와 유사한 문제입니다. 이전 문제와 다른 점은 대괄호가 추가되었다는 것입니다. 풀이 공백을 포함하여 문자를 입력받아야하기 때문에 getline함수를 이용하였습니다. 이전 문제와 똑같은 원리로 비어있음을 판단하여 괄호가 짝이 맞았는지 안맞았는지를 판단하였습니다. 소스 코드 #include #include #include using namespace std; bool check(const string &str); int main() { string str; while (1) { getline(cin, str); if(str[0] == '.') break; if(check(str)) cout 백준 9012 : 괄호 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 괄호 문자열(PS)은 '('와 ')'로만 이루어진 문자열이고, 그 중에서 올바른 괄호 문자열(VPS)은 '('와 ')'가 한 쌍을 이룬 괄호 문자열입니다. 올바른 괄호 문자열이면 "YES"를 아니면 "NO"를 출력해야 합니다. 풀이 스택(stack)을 활용하기로 했습니다. '('는 push를 하고 ')'를 만날 시 pop을 합니다. '('와 ')'는 한 쌍을 이루니 올바른 괄호 문자열(VPS)이면 스택은 비어있어야 합니다. 소스 코드 #include #include #include using namespace std; bool chec.. 백준 10773 : 제로 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 0을 입력 받을 시 최근에 저장된 숫자를 제거해야 하기 때문에 스택의 활용에 대한 문제입니다. 입력받은 숫자가 0이면 pop을 하고 아니면 push를 하여 스택에 저장합니다. 풀이 STL에 있는 stack을 이용하여 풀었습니다. 0을 입력받으면 pop메서드를 호출하고 아닐 시 push메서드를 호출하여 데이터를 저장하고 top메서드로 최근 숫자를 불러와서 sum변수에 저장하고 pop을 하였습니다. 소스코드 #include #include using namespace std; int main() { stack s; int K, input; int sum = 0; cin >> K; for (int i = 0; i > inp.. 이전 1 2 다음