본문 바로가기

Programming/백준 문제풀이

 (21)
백준 1874번 스택 수열 _ STACK (c++) 문제: https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 이번에 다룰 1874번 문제는 앞선 포스팅에서 10828번의 스택을 구현할 때 만들어둔 스택 클래스를 그대로 가져다가 활용해서 풀 수 있는 문제이다. 아래 링크를 참조하면 된다. 2020/03/05 - [Programming/백준 문제풀이] - 백준 10828, 18258번 _ Stack과 Queue C++로..
백준 10828, 18258번 _ Stack과 Queue C++로 구현하기. Stack 스택 구현 문제: https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net Queue 큐 구현 문제: https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제..
백준 2981번 검문 _ 최대공약수 (c++) 문제: https://www.acmicpc.net/problem/2981 2981번: 검문 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 www.acmicpc.net 이 문제.. 시작부터 정답률과 정답자 수를 보니 심상치 않았다.. 2981번 검문 문제의 핵심은 이 문제를 수학적으로 어떻게 풀 지 정..
백준 1005번 ACM craft _ 위상정렬 (c++) 문제: https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 이 문제는 필자에게는 개인적으로 처음 백준 사이트에서 1000번(백준 첫 시작문제)부터 차례대로 차근차근 풀어가야지! 하고 ..
백준 1912번 수열합 _ 동적계획법 DP (C++, python) 문제: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이번 문제는 간단한 동적계획법을 이용하여 푸는 수열합 문제입니다! 난이도에 비해서 정답률이 굉장히 낮은 편인데요, 아마도 DP, 동적계획법에 익숙하지 않으신 분들은 쉽게 접근하기 힘들었을 수 있을 것 같아요. 동적계획법은 특별한 알고리즘이 아니에요. 복잡하거나 계산이 까다로운 문제를 작은 부분문제로 나누어보는 것을 말한답니다. 그런데 이는 mergesort처럼 분할정복 알고리즘과도 비슷해보이는데요, ..
백준 2580번 스도쿠_ 백트래킹(BackTracking) (c++) 문제: https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 이번 문제는 백트래킹에 관한 문제입니다! 백트래킹은 단순히 모든 경우의 수를 조사하는 브루트포스(무차별대입)과는 다른 개념이에요. ..
백준 10989번 _ counting sort (c++) 문제: https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 우리가 아는 정렬알고리즘들로는 웬만하면 모두 메모리초과가 날 것이라고 감히 확신해본다. 10000이하의 수라고 했으니 short로 배열을 만든다해도 주어진 10,000,000개를 저장할 수 있는 배열만 만들어도, 대략 20Mb가 되어버린다. 애초에 메모리제한이 8Mb라는 건, 우리가 아는 배열에 저장해서 nlogn의 시간복잡도로 계산하는 그런 문제가 아니란 뜻! 그렇다면 해결책은 바로 counti..
백준 2798번 _ BlackJack 블랙잭 / Brute Force 브루트포스 (C++) 문제: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 필자는 호주워홀시절 카지노에서 블랙잭으로 꽤나 큰 돈을 잃어본 적이 있다... 또르륵.. 여튼 오늘도 각설하고, 또 백준이 블랙잭을..

티스토리툴바