알고리즘61 [Python][백준 14503] 로봇 청소기 [백준 14503] 로봇 청소기 Python 풀이📌 문제 분석로봇 청소기가 주어진 방에서 청소할 수 있는 칸의 개수를 구하는 문제입니다.방은 2차원 배열로 표현되며, 각 칸은 벽(1) 또는 빈 칸(0)으로 이루어져 있습니다.로봇은 현재 위치에서 청소를 하고, 주변에 청소되지 않은 빈 칸이 있으면 반시계 방향으로 회전하여 이동합니다. 모든 방향이 벽인 경우 후진합니다.🚨 시행착오처음에는 로봇의 이동과 청소 로직을 단순하게 구현했으나, 인덱스 범위 체크와 방향 전환 로직에서 문제가 발생했습니다.로봇이 청소한 칸을 제대로 표시하지 않거나, 후진 로직이 불완전하여 무한 루프에 빠지는 경우가 있었습니다.처음 코드의 문제점인덱스 범위 체크가 부족하여 배열의 경계를 넘어가는 경우가 발생했습니다.방향 전환 로직이 .. 2025. 1. 20. [Python][백준 1759] 암호 만들기 [백준 1759] 암호 만들기 Python 풀이📌 문제 분석주어진 알파벳으로 구성된 암호를 생성하는 문제입니다.암호는 서로 다른 L개의 알파벳 소문자로 구성되어야 하며, 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음이 포함되어야 합니다.생성된 암호는 사전식으로 정렬되어 출력되어야 합니다.🚨 시행착오처음에는 모든 가능한 조합을 생성하기 위해 itertools의 permutations를 사용하려고 했습니다.그러나 이 방법은 중복된 조합을 생성하고, 조건을 체크하는 데 비효율적이라는 문제가 있었습니다.처음 코드의 문제점itertools를 사용하여 모든 순열을 생성하면, 조건을 만족하지 않는 조합도 포함되어 결과가 비효율적이었습니다.또한, 모음과 자음의 개수를 체크하는 로직이 복잡해져 .. 2025. 1. 14. [Python][백준 1148] 단어 만들기 https://www.acmicpc.net/problem/1148 1148번: 단어 만들기 어떤 신문엔 이러한 퍼즐이 있다. 3x3의 표에 영문자가 하나씩 있으며, 이 영문자들을 사용해서 최대한 많은 영단어를 만드는 것이 목표이다. 예를 들면, 아래의 퍼즐판에서는 'LINT', 'TILL', 'BRILLIAN www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 퍼즐에 있는 모든 글자들에 대해 각 글자마다 가능한 단어의 수 체크 2. 가장 많은 단어와 가장 적은 단어를 기록 및 출력 3. 단어의 수 체크할때 ASCII 코드 값 활용해서 배열 활용 간단한 문자열 문제 */ import sys input_func = sys.stdin.readline input_words = [] while T.. 2024. 4. 2. [Python][백준 5972] 택배 배송 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 양방향 가중치 2. 1개 이상의 경로 존재 3. 다익스트라로 접근 */ import heapq def dijkstra(start): distances = {node: float('inf') for node in graph} distances[start] = 0 priority_queue = [(0, start)] while priority_queue: current_.. 2024. 4. 1. [Python][백준 1719] 등산 https://www.acmicpc.net/problem/1486 1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 입력된 알파벳을 숫자로 변환 (ASCII 코드 응용) 2. 변환한 높이정보를 활용해 상하좌우 오버플로 체크 후 해당 위치까지 가는데 걸리는 시간 계산 2.1 높이가 출발 위치보다 높으면 둘의 차의 제곱 2.2 출발 위치보다 낮으면 1 2.3 행렬 형태로 저장된 값을 리스트 형태로 변형 i*(가로열 길이) + j 3. 얻은 값으로 플로이드 워셜.. 2024. 3. 28. [Python][백준 1719] 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 최단거리를 계산한다 2. 최단거리 계산을 위해 비교하며 가장 먼저 거쳐간 집하장을 저장한다. 3. 저장된 집하장 정보가 없다면 현재의 k값을 있다면 원래의 집하장 정보를 저장한다. */ import sys input = sys.stdin.readline INF = float('inf') def floyd_warshall(graph): n = le.. 2024. 3. 26. [Python][백준 1956] 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 일방통행 (양방통행 X) 2. 거리의 합이 가장 작은 사이클을 찾아야 하며, 없으면 -1 출력 3. 플로이드 워셜을 통해 최단 거리를 계산할때 사이클이 있어야 하므로 스스로를 0으로 초기화 하지 않음 4. 나온 결과물 중 INF가 아닌 가장 작은 값을 출력 사이클 만드는 접근법만 생각해내면 간단한 응용이었다. */ impor.. 2024. 3. 26. [Python][백준 21278] 호석이 두 마리 치킨 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 플로이드 워셜을 통해 각 건물간의 거리를 구한다. 2. 치킨집은 총 두개이고 각 치킨집에서 다른 건물까지 걸리는 시간을 비교한다 3. 더 작은 값의 2를 곱한뒤 저장한다 (왕복 소요 시간) 4. 각 치킨집의 위치를 완전탐색으로 돌리며 위의 방법으로 구한 값을 비교한다. 5. 더 작은 값의 치킨집 위치를 같이 저장한다. 플로이드 .. 2024. 3. 23. [Python][백준 2660] 회장뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 입력된 사람들의 친구 관계를 행렬 형태로 저장 2. 최대 회원 수가 50명이므로 시간적 압박은 크지 않다 따라서 플로이드 워셜을 사용했다. 3. 각 사람의 가장 먼 사람을 기준으로 잡고 회원들 중 가장 적은 거리를 구한다 4. 그 거리와 그 거리를 가진 회원의 수 를 구하고 5. 회원들의 리스트를 뽑은 후 정렬 후 출력한다. 플로이드 워셜만 사용할 줄 알면 .. 2024. 3. 22. [Python][백준 1897] 토달기 https://www.acmicpc.net/problem/1897 1897번: 토달기 첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 토달기 가능한 단어가 없을 시 시작한 단어가 정답 2. bfs 로 탐색하며 확인해야 하는 조건들 : - 토달기 단어보다 한글자 많아야 한다. - 토달기 단어를 포함하는 단어 - 중간에 다른 글자 하나를 포함한 토달기 단어 - 투 포인터로 문자열 탐색 - 방문 처리를 통해 방문한 단어 재방문 방지 어려워 보이지만 방법 자체만 알면 그리 어렵진 않다 */.. 2024. 3. 21. [Python][백준 1595] 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 데이터 입력 try catch 문 활용해서 입력없음으로 오류 발생 방지 2. 최대 10000개 노드를 DFS 돌릴 시 시간초과 발생 3. 따라서 가장 긴 거리를 찾는거니 가장 긴 거리를 가질 두 노드 중 하나를 구하고 해당 노드로 탐색을 돌리면 총 두번의 탐색만으로 가장 긴 도로를 찾을 수 있다. */ import sys input = sys.stdin.rea.. 2024. 3. 20. [Python][백준 2251] 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 수통의 최대용량, 수통의 현재 채워진 용량 둘을 구분지어 활용 2. 물을 옮길때 수통이 가득차거나 빌 때까지 옮긴다 3. 도달했던 값은 방문처리로 재방문 방지 4. 결과값들을 정렬 후 출력 문제가 그리 어려워 보이진 않았지만 막상 풀려고 하니 멍해졌다 직접 얼마만큼의 물을 옮겨야 할지 먼저 계산해볼까 했지만 답이 없어보여서 그냥 두 가정 .. 2024. 3. 19. 이전 1 2 3 4 ··· 6 다음