[백준] 4344번: 평균은 넘겠지 [C++]
알고리즘 분류: 수학, 사칙연산 문제 링크: https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 【 풀이 】 테스트 케이스마다 학생 점수의 총평균 중 평균을 넘는 사람의 비율이 얼마나 되는지 구하는 문제이다. 총점수에서 학생 수만큼 나누어 평균을 구하고 평균을 넘는 사람의 수를 구한 다음, 총학생의 수에서 평균을 넘는 사람의 수를 나누고 *100을 해주면 된다. 【 코드 】 #include #include using namespace std; int main(void) { int T; cin >> T; for (int t =..
[백준] 1541번: 잃어버린 괄호 [C++]
알고리즘 분류: 수학, 문자열, 그리디 알고리즘, 파싱 문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 【 풀이 】 문자열을 잘 쪼개서 숫자로 변환시켜 적절히 더하는 문제이다. '-' 기호가 처음 나온 경우, 그 위치 기준 뒤에 있는 모든 숫자들을 빼면 식의 값을 최소로 만들 수 있다. 원리는 다음과 같다. 55 - 50 + 40 => 55 - (50 + 40) 50 - 40 + 30 - 20 + 10 => 50 - (40 +..
[백준] 1260번: DFS와 BFS [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 【 풀이 】 정점, 간선, 번호가 순서대로 주어지면 DFS와 BFS로 정점 방문 순서를 출력하면 되는 문제이다. 단 주의해야 할 점은 DFS와 BFS를 구현하기 전에, 인접리스트를 사용하였다면 인접리스트를 정렬해 주는 작업이 필요한데, 이는 정점 번호가 더 작은 순부터 ..
[백준] 1012번: 유기농 배추 [BFS][C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 【 풀이 】 배추밭을 나타내는 배열(field), 방문한 배추밭을 나타내는 배열(isVisited), 상하좌우 방향을 나타내는 배열(way) 세 개의 2차원 배열을 활용해 bfs로 해결했다. 구체적인 문제 해결 과정은 다음과 같다. 배추밭을 가로로 쭉 돌면서 배추가 심어져 있고 방문한 적 없는 곳의 위치 bfs 함수로 ..
[백준] 17626번: Four Squares [C++]
알고리즘 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘 문제 링크: https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 【 풀이 】 DP 문제이다. 즉 규칙을 먼저 찾는 것이 중요한 문제. n의 제곱수들의 최소 개수를 저장한 배열을 dp라고 가정하면, dp[n]은 항상 최적의 해가 된다고 볼 수 있다. 그리고 dp[제곱수]는 항상 그 값이 1이다. dp[1] =1 dp[2] = dp[1] + dp[1] dp[3..
[백준] 11727번: 2*n 타일링 2 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 【 풀이 】 역시 다른 DP문제와 마찬가지로, 경우의 수를 계산하면서 규칙을 찾는 것이 중요하다. 2*n 직사각형을 채우는 방법의 수를 저장한 배열을 N이라고 했을 때, N[4] 까지의 값들은 다음과 같다. 1 2 3 4 1 3 5 11 여기서, N[n] = N[n-2]*2 + N[n-1] 이라는 점화식을 도출할 수 있다. 즉 이에 따라 12까지의 값을 나열하면 다음과 같다. 3..
