전체 보기
[1021번] 회전하는 큐
백준 1021번: 회전하는 큐 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 큐(Queue)는 다들 아시죠? 큐의 특징은 FIFO(First In First Out)입니다. 그렇기 때문에 pop하면 무조건 맨 앞 원소가 나오게 되고, push하면 무조건 맨 뒤에 원소가 들어가게 되죠. 하지만 이번에는 이 큐의 오퍼레이션을 추가한 자료구조가 있습니다. Queue Member Functions: push(value), pop()..
[2164번] 카드2
백준 2164번: 카드2 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net 유명한 자료구조 중 하나인 큐(Queue)를 이용해서 푸는 문제입니다. 단순히 제시해준 규칙을 잘 구현하기만 하면 풀 수 있는 문제입니다. [소스 보기]
[1992번] 쿼드트리
백준 1992번: 쿼드트리 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net 분할 정복(Divide-&-Conquer)의 대표적인 문제 중 하나입니다. 이전에 포스팅했던 [2630번] 색종이 만들기와 같은 알고리즘을 씁니다. 다만 이번에는 개수를 세는 것이 아니라 4등분 후 해당 면이 모두 같은 숫자로 채워져 있다면 그 숫자가 그 분면을 대표하는 숫자라 할 수 있겠죠. 그래서 그 숫자로 압축을 하는 것입니다. 재귀 함수를 쓰고 출력 형식만 ..
[2630번] 색종이 만들기
백준 2630번: 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net 가장 기본적인 Divide-&-Conquer(분할 정복) 문제 중 하나라고 할 수 있습니다. 한 변의 길이가 $2^n$인 정사각형을 입력받은 후에 정확히 4등분을 해서 온전히 0 또는 1로 이루어진 색종이를 얻습니다. 그리고 0으로만 이루어진 색종이와 1로만 이루어진 색종이의 개수를 각각 세기만 하..
[1012번] 유기농 배추
백준 1012번: 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 이번 문제는 Graph를 다루는 문제입니다. 예전에 이와 매우 유사한 문제를 만난 적이 있죠? [2667번] 단지번호붙이기 이번에도 BFS를 이용해서 1로 이루어진 구역..
[1712번] 손익분기점
백준 1712번: 손익분기점 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 www.acmicpc.net 단순히 계산하는 문제입니다. 조건에만 잘 맞춰서 결과를 반환하면 됩니다. [소스 보기]
[2798번] 블랙잭
백준 2798번: 블랙잭 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 기존에 저희가 알고 있던 블랙잭이라는 게임의 조건을 조금 바꾼 문제라고 할 수 있습니다. 처음에 저는 $N$개의 카드 중에서 3개를 뽑아야 한다는 조건 때문에 조합의 개념으로 생각..
[4447번] 좋은놈 나쁜놈
백준 4447번: 좋은놈 나쁜놈 4447번: 좋은놈 나쁜놈 문제 비키니시티에 초능력을 가진 수퍼 히어로들로 바글바글하다. 스폰지밥과 패트릭은 주어진 문자열로 좋은놈과 나쁜놈을 골라내려 한다. 스폰지밥: 우와, 문자열에서 강한 힘이 느껴지는데! 근데 좋은 놈인지 나쁜 놈인지 알 길이 없네. 패트릭: 아니, 쉬운 것 같은데? 그냥 이름에서 'g'의 개수와 'b'의 개수만 세면 돼. 'g'가 더 많으면 좋은 놈. 'b'가 더 많으면 나쁜 놈. 위대하신 히어로 중의 히어로 'Algorithm Crunching Man' www.acmicpc.net 단순히 한 줄 string을 입력받은 뒤 각 문자에 대해 g(G), b(B)의 개수를 셉니다. 이후 그 개수를 비교해 출력만 해주면 되는 간단한 문제입니다. [소스 보기]
[4153번] 직각삼각형
백준 4153번: 직각삼각형 4153번: 직각삼각형 문제 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오. 입력 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. 출력 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다. 예제 입력 1 복사 6 8 www.acmicpc.net 피타고라스의 직각삼각형 공식입니다. c^2 = a^2 + b^2 ( c >= a, b / a + b >= c ). 다들 아시죠?ㅎㅎ [소스 보기]