본문 바로가기

알고리즘/백준

 (263)
[백준] 1062번 : 가르침 1062번: 가르침 해당 문제는 조합 문제로 해결 하였습니다. 알파벳의 모든 경우의 수를 구한뒤에, 알파벳으로 읽을 수 있는 단어를 계산합니다. 알파벳을 읽을 수 있는 learned 배열을 통하여 읽을 수 있는 알파벳을 표기하고 단어중에 learned 값이 모두 있다면 카운트를 증가시킵니다. from itertools import combinations N, K = map(int, input().split()) northword = list(['a','n','t','i','c']) alpabat = list(['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z']) words = list() for _ in ..
[백준] 3055번 : 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 해당 문제는 너비우선탐색으로 문제를 해결 하였습니다. 1. Water와 Bacoon을 너비우선탐색하여 업데이트합니다. 2. Water와 Baccon을 비교하여 방문 가능한 그래프를 업데이트합니다. 3. 다시 그래프를 너비우선탐색으로 탐색하여 최소값을 구합니다. from copy import deepcopy from collections import deque from pprint import pprint R ..
[백준] 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해당 문제는 깊이우선탐색 + 다이나믹프로그래밍 으로 문제를 해결 하였습니다. 1. end_nodes를 찾습니다. end_nodes는 루트 노드들 입니다. 2. end_nodes로 부터 시작하여 dp 테이블을 업데이트 합니다. ( 방문 가능한 노드들중 최대값으로 ) 3. dp[W] 값을 출력하여 W의 최대값을 출력합니다. T = int(input()) def dfs(node, graph, d,..
[백준] 2146번 : 다리 만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 너비우선탐색(BFS)로 문제를 해결하였습니다. 문제의 요점은 다리의 최소길이를 구해야하는 문제임으로 BFS탐색을 사용하였습니다. 1. BFS 탐색으로 각각의 섬 그룹핑하기 2. BFS 탐색으로 각각의 섬에서 다른섬까지의 최소길이 구하기 각각의 섬을 BFS 탐색을 통하여 그룹핑을 하였습니다. 저는 각 섬을 1번 2번 3번... N번으로 라벨링하여 섬을 구분하였습니다. def byGroup(i,j): gl..
[백준] 2638번 : 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 위의 문제는 탐색의 문제로 깊이우선탐색과 너비우선 탐색으로 모두 문제를 해결 할 수 있습니다. 1. 치즈의 개수를 구한다. 개수가 0이상이라면 치즈를 녹여야 한다. 그렇지 않으면 종료한다. 2. 치즈를 녹일때 너비우선탐색 혹은 깊이우선탐색으로 녹여야할 치즈 후보를 구한다. 3. 녹여야할 치즈 후보를 현재 그래프에 적용하고, 시간을 증가한다. 4. 1~3까지 계속 반복하여 시간 최종 시..
[백준] 13023번 : ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깊이우선탐색(DFS)로 문제를 해결 하였습니다. 친구의 관계가 A->B->C->D->E와 같은 경우가 존재할경우, DFS탐색을 중지합니다. 사이클이 생기지 않도록 탐색한 친구는 또 탐색하지 않습니다. Set 자료구조를 활용하여 깊이우선 탐색을 한 친구는 Set 자료구조에 추가하여 이미 방문한 친구를 찾을때 O(1) 시간복잡도로 찾을 수 있습니다. import sys sys.setrecursionlimit(100000) N , M = map(int ,input().split()) graph = [[] f..
[백준] 1937번 : 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 깊이우선탐색(DFS)와 메모리제이션 으로 문제를 해결 하였습니다. 깊이우선탐색 선택 이유 : 현재의 위치에서 다음위치로 갈 수 있는 경로가 있을때, 그 다음위치의 최대값 + 1 한 값이 현재위치이기 때문에 좀더 코드적으로 보기 편하다. 한번 탐색한 경로는 이미 최대의 크기를 가지고 있기때문에 탐색할 필요가 없어 메모리에 저장해두어 탐색하지않고 값을 리턴한다. import sys sys...
[백준] 1967번 : 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해당 문제는 깊이 우선탐색으로 문제를 해결 하였습니다. 1. 아무노드로 부터 시작하여 깊이우선탐색을 하여 가장 긴 노드를 찾습니다. 2. 가장 긴 노드로부터 다시 깊이우선탐색을하여 다른 노드까지의 긴 길이를 찾습니다. 가장 긴 길이가 트리 의 지름입니다. 이유 : 트리는 사이클이 없어서, 한 노드로부터 다른 한노드까지의 경로는 단 하나 존재합니다. 따라서 아무 노드로부터 시작하..

티스토리툴바