코딩테스트 검색 결과

해당 글 93건

[BOJ 1389] 케빈 베이컨의 6단계 법칙(C++)

케빈 베이컨의 6단계 법칙(Silver 1) 문제 전체 문제 보기 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근법 모든 사람에 대해서 각 사람들까지 관계 단계를 모두 계산해야 합니다. 이럴 경우 플로이드 워셜 알고리즘을 사용할 수 있습니다. 모든 사람들 관계에 대한 2차원 테이블을 만듭니다. 그리고 플로이드 워셜 알고리즘을 활용하여 관계의 최단 거리를 구합니다. 이 거리들의 합이 바로 케빈 베이컨의 수가 됩니다. 이 수가 가장 작은 사람을 출력하면 정답을..
Algorithms/Graph 2021. 9. 22. 16:24

[BOJ 1107] 리모컨(C++)

리모컨(Gold 5) 문제 전체 문제 보기 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 접근법 이번 문제는 완전 탐색(Brute Force)으로 풀 수 있는 문제입니다. Brute Force 문제를 접했을 때 Brute Force로 풀수 있는지 가늠해 보고 판단하는 것이 중요합니다. 이번 문제는 다음과 같이 탐색하면 충분히 완전 탐색이 가능합니다. 0번 채널 ~ 1,000,000 채널까지 탐색을 진행 각 채널이 고장나지 않은 버튼들로 만들 수 있는지 확인 만들 수 있는 채널이라면, 해당 채..
Algorithms/Brute Force 2021. 9. 22. 15:15

[BOJ 9663] N-Queen(C++)

N-Queen (Gold 5) 문제 전체 문제 보기 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근법 N-Queen 문제는 Backtracking을 활용하여 풀 수 있습니다. Backtracking의 알고리즘은 항상 다음과 같은 패턴으로 구현할 수 있습니다. 탈출 조건 확인 반복문을 활용한 모든 브랜치 탐색 조건에 만족하는 브랜치만 재귀적으로 탐색 N-Queen 문제 또한 위의 방식으로 풀이할 수 있습니다. 일반적인 Backtracking 알고리즘보다 유효성 검사 부분이 까다롭고 가지치기를 효과적으로 하기 위한 접근법이..
Algorithms/Backtracking 2021. 9. 20. 19:06

[BOJ 18870] 좌표 압축(C++)

좌표 압축(Silver 2) 문제 전체 문제 보기 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 접근법 이번 문제는 sort 알고리즘을 두 번 적용하여 아래와 같이 해결할 수 있습니다. 입력받은 수 들을 오름 차순으로 정렬한다. 각 수들에게 0부터 순차적으로 순위를 매긴다. (크기가 같은 수는 같은 순위를 가집니다.) 다시 입력받은 순서대로 오름차순 정렬한다. 순서대로 순위를 출력한다. 자료구조 선택 각 수들은 순위와 입력받은 순서 데이터를 추가로 가져야 합니..
Algorithms/Sort 2021. 9. 20. 14:25