코후닝

알고리즘 분류: 수학, 문자열, 그리디 알고리즘, 파싱 문제 링크: 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 +..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: 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를 구현하기 전에, 인접리스트를 사용하였다면 인접리스트를 정렬해 주는 작업이 필요한데, 이는 정점 번호가 더 작은 순부터 ..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 【 풀이 】 배추밭을 나타내는 배열(field), 방문한 배추밭을 나타내는 배열(isVisited), 상하좌우 방향을 나타내는 배열(way) 세 개의 2차원 배열을 활용해 bfs로 해결했다. 구체적인 문제 해결 과정은 다음과 같다. 배추밭을 가로로 쭉 돌면서 배추가 심어져 있고 방문한 적 없는 곳의 위치 bfs 함수로 ..

알고리즘 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘 문제 링크: 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..

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: 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..

알고리즘 분류: 누적 합 문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 【 풀이 】 1~4: (1~4) 2~5: (1~5) - (1~1) 3~6: (1~6) - (1~2) 즉 1~1, 1~2, 1~3, 1~4... 1~end까지의 구간합들을 sum이라는 배열에 따로 저장한다. 그리고 sum[end] - sum[start-1] 을 출력해 주면 끝. 만약 다음에 입력받는 end 변수가 전의 변수보다 더 크다면 ..