1. BFS란? BFS란 루트 노드(Node)에서 시작하여 인접한 노드를 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 이때 한 번 방문한 정점은 다시 방문하지 않는다. 노드 사이의 최단 경로를 구하고자 할 때, 혹은 임의의 경로를 찾고자 할 때 BFS를 이용한다. 2. BFS를 코드로 구현하려면? 1️⃣ 시작하는 정점을 큐에 삽입하여 방문했다는 표시를 남긴다. 2️⃣ 큐의 제일 앞에 있는 원소를 삭제한 후, 해당 원소에 연결돼 있으면서 아직 방문하지 않은 정점을 큐에 삽입한다. 3️⃣ 큐가 비어있을 때까지 2️⃣를 반복한다. 이때 모든 정점(Node)을 한 번, 모든 간선(Edge)을 두 번씩 방..
해당 게시글에서는 [백준] 10844 쉬운 계단 수 문제를 해설하고 Python을 이용하여 풀고자 한다. 🤔 접근법 문제 풀이 방식을 빠르게 알고싶다면 💡문제 풀이 부분 부터 봐주세요 :) 10844 문제는 DP(다이나믹 프로그래밍)에 대한 문제로 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법하는 방식의 알고리즘이다. 문제 접근 방식은 유사한 DP 문제를 많이 풀어봐서 그다지 어렵지 않았다. 다른 때와 똑같이 규칙을 찾기위해 N에 따른 값들을 분석했다. N이 1인 경우와 2인 경우를 나열해보면 어렵지 않게 규칙을 찾을 수 있다. N이 1인 경우: 1, 2, 3, 4, 5, 6, 7, 8, 9 N이 2인 경우: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67,..
해당 게시글에서는 [백준] 1431 시리얼 번호 문제를 해설하고 Python을 이용하여 풀고자 한다. 🤔 접근법 1341번 문제는 정렬에 관한 문제이다. 애초에 문제에서 정렬이라고 밝히고 있기 때문에 정렬 문제라는 걸 아는 건 크게 어렵지 않을 것이다. 시리얼번호 A가 시리얼번호 B의 앞에 오는 조건은 다음과 같이 해석할 수 있다. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 👉 문자열의 길이에 따라 정렬 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 👉 각 자리 숫자의 모든 합에 따라 정렬 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 👉 사전..
해당 게시글에서는 [백준] 2447 별 찍기 - 10 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 2447번 문제는 별 찍기 문제이다. 처음에 문제를 읽었을 때 단번에 이해가 되지 않았다. 지문과 예제를 동시에 보며 조금 고민하고 나서야 문제가 이해됐다. 단계별로 풀어보기 카테고리를 통해서 들어왔기 때문에 해당 문제가 재귀(recursion)와 관련된 문제인 걸 알고 있었다. 그래서 재귀적으로 해당 문제를 풀기 위해 근접한 입력값들에 대해 어떤 규칙이 있는지 생각해 봤으며, 그 결과 다음과 같은 결론을 내릴 수 있었다. N을 출력하기 위해선 N//3의 출력 결과가 필요하다. N을 출력할 때는 N/3의 출력을 3번씩 3줄에 걸쳐 출력하면 된다. 이때 2줄의 2번째 출력은 공백이어야 ..
