728x90
728x90

algorithm 230

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 정리 - 기본적인 특징과 유의 사항에 대해서

깊이 우선 탐색과 너비 우선 탐색에 대해 간단하게 비교하여 정리하고자 한다. 두 알고리즘은 생각보다 알고리즘 문제 풀이에서 많이 볼 수 있고, 각각의 응용 방식을 통해 나오는 코딩 테스트 문제가 많기 때문에 참고해두는 것이 좋고, 기본적인 구현 방식은 알고 접근하는 것이 좋다. 기본적인 구현 코드는 백준 온라인 저지의 1260번 DFS와 BFS 을 구현하는 코드이다. DFS(Depth-First Search) Stack으로 구현할 수 있고, 함수 호출도 Stack처럼 이뤄지기 때문에 대부분 재귀 함수로 구현된 코드들이 많다. DFS는 미로 찾기로 치면, 막히는 곳까지 계속 파고 드는 Leaf-wise한 방식이다. 분기점이 나오면 길 하나를 선택하고 더 이상 진행하지 못하는 시점까지 진행한다고 보면 이해하..

BOJ] 11559 Puyo Puyo(연세대학교 프로그래밍 경시대회 C번)

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 입력 12*6의 문자가 주어진다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.(모두 대문자로 주어진다.) 입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태(즉 뿌요 아래에 빈 칸이 있는 경우는 없음) 이다. 출력 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) 문제 접근 간단한 BFS이고, 부숴지는 벽돌이 4개 이상 나오면 벽돌을 부..

백준] 3943 - 헤일스톤 수열(ACM-ICPC Regionals)

시간 제한 : 1초 메모리 제한 : 128MB 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000) 출력 각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다. 소스코드 #include #include using namespace std; int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int T; cin >> T; while (T--) { int n, heils, max; cin >> n; heils = max = n; while (heils!=1) { ..

백준] 1541 - 잃어버린 괄호

시간 제한 : 2초 메모리 제한 : 128MB 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 출력 첫째 줄에 정답을 출력한다. 소스코드 #include #include #include using namespace std; int main(void) { int len, start, end; string str, substr=""; vector intArr; vector opArr; cin >> str; len = str.length(); start = 0; for (int i = 0; i < l..

백준] 2303 - 숫자 게임(한국정보올림피아드 2005;KOI 2005 초등부)

시간 제한 : 2초 메모리 제한 : 128MB 입력 첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다. 출력 게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다. 소스코드 #include #include #include using namespace std; struct user { vector card; int su; int idx; }; bool compare(const struct user a, const struct u..

백준] 2583 - 영역 구하기(한국정보올림피아드 2006; KOI 2006)

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 출력첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다. 소스코드#include #include #include #include usin..

백준] 5556 - 타일(일본정보올림피아드 2011;JOI 2011)

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 한 변의 길이 N이 주어진다. (1 ≤ N ≤ 109) 둘째 줄에는 창영이가 제거한 타일의 개수 K가 주어진다. (1 ≤ K ≤ 1000) 다음 줄부터 K개 줄에는 창영이가 제거한 타일의 위치 ai bi가 제거한 순서대로 주어진다. (1 ≤ ai ≤ N, 1 ≤ bi ≤ N) 타일은 왼쪽에서 ai번째, 위에서 bi번째에 있다. 같은 타일을 두 번 이상 제거하는 경우는 없다. 출력창영이가 제거한 순서대로 타일의 색상을 출력한다. 빨간색은 1, 파란색은 2, 노란색은 3을 출력한다. 소스코드#include using namespace std; int main(void) { int N, K, half; cin >> N >> K; half = N / 2..

백준] 1406 - 에디터(CHCI 2004)

시간 제한 : 0.3초메모리 제한 : 512MB 입력첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1≤N≤500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다. 출력첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다. 소스코드#include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cout.tie(NULL); st..

백준] 14582 - 오늘도 졌다(2017 고려대학교 프로그래밍 대회)

시간 제한 : 1초메모리 제한 : 64MB 입력첫 번째 줄에는 9개의 정수가 주어지는데, 오늘 경기에서 울림 제미니스가 1회 초, 2회 초, ..., 9회 초에 낸 득점이 주어진다.두 번째 줄에도 9개의 정수가 주어지는데, 스타트링크 걸리버스가 1회 말, 2회 말, ..., 9회 말에 낸 득점이 주어진다.한 팀이 한 회에 낸 득점은 모두 0 이상 20 이하이며, 스타트링크 걸리버스의 총 득점이 울림 제미니스의 총 득점보다 많다.경기는 1회 초->1회 말->2회 초->...->9회 초->9회 말 순서로 진행된다. 출력만약 울림 제미니스가 역전패를 했다면 'Yes'를 출력한다.그렇지 않으면 'No'를 출력한다 소스코드#include #include using namespace std; int main(voi..

728x90