✔ 문제 난이도 : 골드4 🥇 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✔ 문제 풀이 N x N의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제입니다. 🤔 처음 접근 처음 접근할 때에는 첫번째 퀸을 두고 그 퀸의 공격범위를 모두 체크(방문처리)한 후 공격범위가 아닌 부분 부터 두번째 퀸을 두고 공격범위를 체크하며 나아가다 퀸 N개 즉 깊이(depth)가 N이 되었을때 리턴하여 백트래킹을 수행하려고 했습니다. 하지만 공격범위를 모두 체크하는 과정에서 이중 for문을 사용하였고 재귀호출이 끝..
🤔 Brute force 브루트포스 알고리즘? '무식한 힘' 으로 해석할 수 있겠습니다, 이 뜻 처럼 주어진 문제를 무식하게 하나하나 탐색하는 알고리즘 입니다. 모든 경우의 수를 전부 탐색하여 조건에 맞는 답을 찾기 때문에 정확한 답을 보장합니다. 하지만 모든 경우의 수를 탐색하기 때문에 시간복잡도가 높다는 단점이 있습니다. 그렇기 때문에 브루트포스 알고리즘은 시간복잡도를 고려하여 사용해야합니다. 또한 브루트포스 알고리즘은 정형화된 틀이 없기때문에 주어진 문제 유형에 따라 다양한 방법으로 풀이합니다. 단순 Brute force ( for문 ) 재귀호출 비트마스크 순열 DFS / BFS 💡 하지만 비효율적으로 보이는 브루트포스 알고리즘을 왜 사용할까요? 입력되는 범위가 작고, 탐색해야할 경우의 수가 적은 ..
✔ 문제 난이도 : 골드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는 찾으려는 해에 도착하면 탐색을 종료하기 때문입니다. 최..
