문제 https://www.acmicpc.net/problem/2140 2140번: 지뢰찾기 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는 www.acmicpc.net 풀이 이 문제는 구현 + 그리디 알고리즘 문제이다. 배열의 테두리에서 지뢰를 넣을 수 있는 곳을 모두 체크해야 한다. 이때 8방향을 조사해서 지뢰를 넣을 수 있는 곳은 '*'로 표시해두고, 넣을 수 없는 곳이라면 '-'로 표시해두었다. 또한 이미 '*'로 표시되어 있다면 넣을 수 있는 지뢰의 개수를 1씩 감소시켰다. 마지막에 '*' 개수를 세고, 주의해야 할 점은 '#'으로 남아 있는 부분도 c..
그리디(Greedy) 알고리즘이란? 그리디 알고리즘은 "매 선택에서 그 순간 당장 최적인 답을 선택" 하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그리디 알고리즘은 최적 부분 구조(optimal substructure)를 가진 문제를 해결하는데 강점이 있다. 최적 부분구조란 매 순간의 최적해의 합이 문제에 대한 최적해여야 한다는 의미이다. 예를 들어 누군가 A도시에서 B도시를 거쳐 C도시로 간다고 하자. A도시에서 B도시를 갈 때 가장 짧은 거리인 150km 경로를 선택하고, B도시에서 C도시로 갈 때 가장 짧은 거리인 140km 경로를 선택하면, 전체적으로도 최적의 경로가 된다. 매 순간 최적 경로의 합이 전체 경로의 최적 경로가 되었다. 이러한 최적 부분 구조를 가진 문제는 그리디 알고리즘으..