Today's keyword : DFS, DP 📌 문제설명https://www.acmicpc.net/problem/17070📌 문제풀이"파이프 옮기기" 문제는 N x N 격자에서 파이프를 이동시키는 문제입니다. 파이프는 수평, 수직, 대각선으로 놓일 수 있으며, 파이프의 시작 위치는 (0, 0)이고 목표 위치는 (N-1, N-1)입니다. 파이프는 장애물에 의해 이동할 수 없으며, 파이프가 목표 위치에 도달하는 모든 경우의 수를 구하는 것이 목표입니다.풀이방법 1. 메모이제이션과 DFSDFS (Depth-First Search): 재귀적으로 가능한 모든 경로를 탐색하는 방법입니다. 각 위치에서 이동 가능한 모든 방향으로 이동하며, 목표 위치에 도달할 때마다 경우의 수를 증가시킵니다.메모이제이션: 이미 ..

Today's keyword : 구현, 시뮬레이션📌 문제설명https://www.acmicpc.net/problem/13335N개의 트럭이 있고, 각 트럭은 특정한 무게를 가지고 있습니다.다리의 길이는 W이고, 최대 하중은 L입니다.트럭은 다리를 건너야 하며, 다리 위에는 최대 W개의 트럭만 동시에 올라갈 수 있습니다.트럭이 다리를 건너는 데 걸리는 시간은 1초입니다.트럭이 다리를 건너는 동안 다리 위의 트럭의 총 무게는 최대 하중 L을 초과할 수 없습니다.모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 구하는 것이 목표입니다. 📌 문제풀이## 백준 : 트럭 from collections import dequen, w, l = map(int, input().split()) # n : 트럭 개수, w..

Today's keyword : 그리디그리디 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 매 단계에서 가장 최적이라고 생각되는 선택을 하는 방법입니다. 즉, 현재 상황에서 가장 좋은 선택을 하여 최종적인 해답에 도달하는 방식입니다. 그리디 알고리즘은 다음과 같은 특징을 가지고 있습니다 최적 부분 구조: 문제의 최적 해는 부분 문제의 최적 해로 구성됩니다. 즉, 문제를 해결하기 위해 선택한 부분 해가 전체 문제의 최적 해에 기여합니다.탐욕적 선택 속성: 각 단계에서의 선택이 이후의 선택에 영향을 미치지 않으며, 각 단계에서 최적의 선택을 하여 전체 문제를 해결할 수 있습니다.      이 문제가 왜 그리디 알고리즘에 속하는가?마도카의 고양이 문제는 그리디 알고리즘의 특성을 잘 보여주..

Today's keyword : DFS 문제설명https://www.acmicpc.net/problem/25195  방향 그래프에서 1번 정점에서 시작하여 팬클럽 곰곰이를 만날 수 있는지를 확인하는 문제입니다. 팬클럽 곰곰이가 있는 정점이 여러 개 주어지며, 1번 정점에서 시작하여 도달할 수 있는 정점 중 팬클럽 곰곰이가 있는 정점이 포함되어 있는지를 판단해야 합니다. 문제풀이import sysinput = sys.stdin.readlinesys.setrecursionlimit(100001)def dfs(now_v): # 현재 정점이 팬클럽 곰곰이가 있는 정점이거나 이미 방문한 정점이라면 종료 if visited[now_v] or now_v in is_bear: return Fal..

Today's keyword : BFS 문제설명https://www.acmicpc.net/problem/18352이 문제는 주어진 도시와 도로의 정보를 바탕으로, 특정 거리 K에 있는 도시를 찾는 문제입니다.입력 첫 번째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 정보 X가 주어집니다. 다음 M개의 줄에는 도로 정보가 주어지며, 각 줄은 두 도시 A와 B를 나타냅니다. 이는 도시 A에서 도시 B로 가는 도로가 있음을 의미합니다.출력 특정 거리 K에 있는 도시의 번호를 오름차순으로 출력합니다. 만약 그러한 도시가 없다면 -1을 출력합니다.📌문제풀이from collections import dequeimport sys input = sys.stdin.readlineN, M, K, ..

Today's keyword : BFS/DFS 📌 문제설명https://www.acmicpc.net/problem/7562이 문제는 체스판에서 나이트가 특정 위치에서 다른 위치로 이동하는 최소 이동 횟수를 구하는 문제입니다. 나이트는 L자 형태로 이동할 수 있으며, 주어진 체스판의 크기와 시작 및 목표 위치가 주어졌을 때, 나이트가 목표 위치에 도달하기 위해 필요한 최소 이동 횟수를 계산해야 합니다.입력 첫 번째 줄에 테스트 케이스 T가 주어집니다각 테스트 케이스마다 체스판의 크기(I), 나이트의 시작 위치, 나이트의 목표 위치가 주어집니다.출력 : 각 테스트 케이스마다 나이트가 목표 위치에 도달하기 위한 최소 이동 횟수를 출력합니다. 📌 문제풀이from collections import dequeT..

Today's keyword : 그래프 이론 (BFS/DFS) 📌 문제설명https://www.acmicpc.net/problem/2644  📌 문제풀이주어진 두 노드 간의 촌수를 계산하는 문제로, 노드 간의 연결 관계를 그래프로 표현하고, 두 노드 간의 최단 경로를 찾는 것이 목표입니다. 이 문제에서 주의해야 할 점은 그래프가 비어 있거나 연결되지 않은 경우를 처리해야 합니다. 이 경우 -1을 출력해야 합니다. BFS import sysfrom collections import dequesys.setrecursionlimit(10 ** 6) # 재귀 깊이 제한 설정n = int(input())start, end = map(int, input().split())m = int(input())# 그래프..

Today's keyword : 그래프이론 문제설명https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr"모음 사전" 문제는 주어진 모음(A, E, I, O, U)으로 만들 수 있는 모든 가능한 단어를 나열된 사전에서 특정 단어의 순서를 찾는 문제입니다. 단어의 길이는 1부터 5까지이며, 중복된 단어는 허용되지 않습니다. 문제풀이문제풀이1. Product 사용 사전을 구성하는 모음이 5개로 많지 않기 때문에 product을 이용해 모든 가능한 단어를 사전으로 만들어 나열한 후, 주어진 단어의 위치를..

Today's keyword : BFS 📌 개념 설명BFS(너비 우선 탐색) BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 인접한 정점들을 먼저 방문한 후, 그 정점의 인접한 정점들을 탐색하는 방식입니다. 즉, "너비"를 우선적으로 탐색합니다.BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 큐는 FIFO(First In First Out) 방식으로 작동하여, 먼저 들어온 정점이 먼저 나가게 됩니다. 📌 문제 설명https://www.acmicpc.net/problem/24444이 문제는 주어진 그래프에서 너비 우선 탐색(BFS)을 수행하고, 각 정점의 방문 순서를 출력하는 문제입니다.입력첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.다음 m개의 줄에는 간..

Today's keyword : DFS  DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 가능한 깊게 노드를 탐색한 후, 더 이상 갈 수 없게 되면 마지막 분기점으로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 스택을 사용하여 구현할 수 있으며, 재귀적으로도 구현할 수 있습니다. 문제 설명https://www.acmicpc.net/problem/24479백준의 "DFS와 BFS" 문제(문제 번호: 24479)는 그래프 탐색 알고리즘 중 깊이 우선 탐색(DFS)을 구현하는 문제입니다. 주어진 그래프에서 특정 시작 정점으로부터의 방문 순서를 출력하는 것이 목표입니다.입력첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.다음 m개의 줄에는 간선 정보가 주어지며, 각 ..