백준49 [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. [Python][백준 1068] 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net /* 신경써야 할 부분은 바로 : 1. 2% root노드가 0번이 아닐때 발생할수 있다. 2. 78% 루트노드가 리프노드가 될 수 있다. 3. 99% 루트 노드를 삭제하면 0이 나와야한다. 그래서 삭제된 노드와 자식 노드들을 모두 의미없는 값으로 채우고 의미없는 값이 아니며, 자식 노드가 없는 노드의 수를 세면 답이다. */ import sys input = sys.stdin.readline.. 2024. 3. 18. [C++][백준 1406] 에디터 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net /* 쉬운 문제인줄 알았다. 처음에는 string 으로 해보려고 했는데 삭제와 삽입이 문제가 되서 링크드 리스트가 필요하다고 느꼈다 그래서 리스트 컨테이너를 사용해보려고 했지만 생각보다 복잡했다. 그러던 중 스택으로 한번 구현해볼까 하는 생각에 스택으로 구현해보았다. */ #include #include using namespace std; int main() { stack st1; stack st.. 2022. 1. 25. 이전 1 2 3 4 5 다음
