✔ 문제 난이도 : 골드4 🥇 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net ✔ 문제 풀이 실제 스도쿠 규칙과 같이 가로줄, 세로줄, 작은 정사격형 안의 수들이 1부터 9까지 하나씩 있어야합니다. 숫자가 입력 되었을 때 가로줄, 세로줄, 작은 정사각형을 탐색하여 중복된 숫자가 있는지 체크하는 로직은 쉽게 머리속에 떠올릴 수 있었지만, 어떤 흐름으로 어떤 조건을 사용하여 재귀호출하며 백트래킹 과정을 거칠지는 많이 고민이 필요한 문제였습니다. 🔎 isChecked 가로와 세로체크는 모든 9개의 범위를 탐색하여 ..
✔ 문제 난이도 : 골드4 🥇 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✔ 문제 풀이 N x N의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제입니다. 🤔 처음 접근 처음 접근할 때에는 첫번째 퀸을 두고 그 퀸의 공격범위를 모두 체크(방문처리)한 후 공격범위가 아닌 부분 부터 두번째 퀸을 두고 공격범위를 체크하며 나아가다 퀸 N개 즉 깊이(depth)가 N이 되었을때 리턴하여 백트래킹을 수행하려고 했습니다. 하지만 공격범위를 모두 체크하는 과정에서 이중 for문을 사용하였고 재귀호출이 끝..
✔ 문제 난이도 : 골드5 🥇 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ✔ 문제 풀이 주어진 예제 처럼 첫째 줄에 NxN의 배열에 해당하는 N이 주어지고 각 칸에 R,G,B중 하나를 색칠한 그림이 둘째 줄부터 주어집니다. 이때 각 색들이 차지하는 구역과, 적록색약인 사람이 봤을 때의 구역을 구하는 문제입니다. 적록색약은 R(빨강)과 G(초록)이 잘 구분되지 않기 때문에 같은 구역으로 생각하여 카운트하도록 코드를 짠다면 쉽게 풀 수 있습니다. 💡 단순하게 R과 G일 경우 조건을 주어 탐색을 진행하려..
🤔 Floyd-Warshall 플로이드-와샬 알고리즘? 그래프에 있는 모든 정점에 대해 각 정점들이 다른 정점들까지 도달하기 위해 필요한 모든 최단 거리를 구할때 사용합니다. 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징이 있습니다. 즉, 정점 A, 정점B 까지의 최단 거리를 구하기 위해 중간에서 거쳐갈 수 있는 모든 정점들을 확인해보고 그 중 최단 거리의 경로를 찾습니다. (플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬로 표현하여 최단 거리를 계산합니다.) ✔ 시간복잡도 3중 for문을 통해 거쳐가는 정점을 이용하여 그래프를 탐색하기 때문에 O(n^3)의 시간복잡도를 갖습니다. ✔ 탐색 방법 문제와 함께 플로이드-와샬 알고리즘의 탐색방법을 살펴보..
🤔 DFS ( Depth First Search ) 깊이 우선 탐색? 그래프 탐색 알고리즘으로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘 입니다. 즉 그래프 형태의 자료구조에서 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 그림처럼 한 방향으로 인접한 노드가 없을 때까지 탐색한 후 이전 노드로 돌아가서 다음 인접한 노드를 탐색하며 이 과정을 반복합니다. 장점 현재 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있습니다. 단점 DFS를 통해 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 찾으려는 해에 도착하면 탐색을 종료하기 때문입니다. 최..
