본문 바로가기

백준

 (223)
백준3986 - 좋은단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 문제 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 www.acmicpc.net 스택을 활용하여 푸는 문제이다. 문자를 한 개씩 스택에 넣고 top에서 같은 문자를 만나면 빼주는 형식으로 구현하였다. 좋은 단어의 경..
백준2870 - 수학숙제 https://www.acmicpc.net/problem/2870 2870번: 수학숙제 문제 상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다. 선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다. 글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 www.acmicpc.net 생각보다 조건이 까다로웠던 문제다. 파이썬으로 처리하면 간단했을 것 같다. 맨앞에 0처리를 해줘야 하였고 0으로만 이루어진 문자열은 0을..
백준17213 - 과일서리 https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다. www.acmicpc.net 수학적 요소를 중시하는 문제이다. 처음에는 브루트 포스를 사용하려 했지만 문제를 잘 읽어보니 중복조합을 사용하면 될 것 같았다. N개의 요소 중 M개를 중복하여 선택하는 문제이다. N개의 요소는 모두 적어도 1개를 뽑아..
백준11729 - 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 재귀 호출에서 가장 기초가 되는 문제이다. 탑이 세 개가 존재하는데 첫번째 탑에 n개의 판이 작은 원판에서 큰 원판까지 ..
백준1541 - 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 그리디 문제 중 쉬운 편에 속했다. 0~9사이의 숫자와 -와 +가 임의로 주어졌을 때 괄호를 이용하여 최솟값을 찾는 문제이다. 더하기를 더하기끼리 최대한 묶은 후 뺄셈을 해주면 되는 문제다. ​ 예시를 들어 설명을 하자면 다음과 같다. 1. a - b + c - d + e 인 경우 a - (b + c) - (d + e) = a - b..
백준2012 - 등수 매기기 https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 그리디 알고리즘으로 풀었다. 1등부터 n등까지 학생들을 배치해야 하는데 학생들의 불만을 최소화하여 줄을 세우는 문제다. 입력받은 수를 소팅한 후 1등부터 n등까지 차례대로 빼주어 절댓값을 취해 답에 더해주면 된다. #include #include #include #include using namespace std; int main() { int n; vector v; //등수를 입력받을 변수 long l..
백준1389 - 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net 플루이드 와샬을 이용하면 쉽게 풀리는 문제이다. x와 y가 친구 사이일 때 모든 사람들이 친구가 되는데 비용을 갱신한다. 그리고 최소비용을 가진 ..

티스토리툴바