반응형 전체 글163 [Python] Baekjoon - 11725. 트리의 부모 찾기 백준 11725번 트리의 부모 찾기 문제는 노드가 N개인 트리의 간선이 주어질 때 모든 노드의 부모를 구하는 문제다. 그래프 탐색을 통해 해결할 수 있는 문제인데 시간 초과 또는 메모리 초과가 되지 않도록 주의하며 풀어야 한다. 난이도는 실버 2이다. 백준 11725번 트리의 부모 찾기 문제 정보 알고리즘 분류 - 트리 및 그래프 탐색 난이도 - 실버 2 트리의 부모 찾기 문제 요약 노드가 N개이고 1이 루트인 트리의 간선 N-1개가 입력될 때, 2~N번 노드의 부모를 각각 출력하는 문제다. 문제 풀이 과정 방식 1 (시간 초과) 처음에는 edge를 따로 저장하지 않고 입력받을 때마다 이전까지 연결된 트리에 연결하는 방식을 사용했다. 부모가 정해진 노드들의 부모 정보를 저장하는 딕셔너리와, 부모를 아직 .. 2021. 7. 19. [Python] Baekjoon - 13305. 주유소 백준 13305번 주유소 문제는 N개의 도시를 이동하는 동안 필요한 최소 주유비를 구하는 문제다. 가격이 저렴한 주유소에서 최대한 많이 주유하고 가야 하는 문제인데, 그리디 알고리즘을 사용해서 해결할 수 있다. 난이도는 실버 4이다. 백준 13305번 주유소 문제 정보 알고리즘 분류 - 그리디 알고리즘 난이도 - 실버 4 주유소 문제 요약 N개의 도시가 한 줄로 연결되어 있으며 각 도시 사이의 거리와 각 도시의 기름값이 주어질 때, 맨 왼쪽 도시에서 맨 오른쪽 도시까지 가기 위한 최소 주유비를 구하는 문제다. 문제 풀이 과정 가격이 저렴한 주유소에서 최대한 많이 주유하고 가야 한다. 따라서 왼쪽부터 도시를 하나씩 이동하면서 현재까지 기름값이 가장 싼 금액을 곱해가면 된다. 코드 import sys def.. 2021. 7. 19. [Python] Baekjoon - 17136. 색종이 붙이기 백준 17136번 문제 색종이 붙이기는 10x10 크기의 종이에 다양한 크기의 색종이를 붙이는 문제다. 필요한 색종이의 최소 개수를 구하는 문제인데, 백트래킹을 이용해서 색종이를 붙이는 모든 경우를 계산해서 답을 구할 수 있다. 난이도는 골드 2이다. 백준 17136번 색종이 붙이기 문제 정보 알고리즘 분류 - 백트래킹 및 브루트 포스 난이도 - 골드 2 색종이 붙이기 문제 요약 10x10 크기의 종이가 각 칸에 0 또는 1로 채워져 있으며, 1이 쓰인 칸에만 색종이를 붙일 수 있다. 색종이는 5x5, 4x4, 3x3, 2x2, 1x1 각각 5장씩 존재한다. 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수 구하라. 종이를 모두 못 채우면 -1을 반환한다. 문제 풀이 과정 처음에는 그리디 방식으로.. 2021. 7. 19. [Python] Baekjoon - 1449. 수리공 항승 백준 1449번 문제 수리공 항승은 직선 파이프에 N개의 구멍이 났을 때 테이프를 최소 몇 개 붙여 구멍을 모두 막을 수 있는지 구하는 문제다. 이 문제는 그리디 알고리즘과 정렬을 사용해 해결할 수 있다. 난이도는 실버 3이다. 백준 1449번 수리공 항승 문제 정보 알고리즘 분류 - 그리디 알고리즘 및 정렬 난이도 - 실버 3 수리공 항승 문제 요약 직선 파이프에 N개의 구멍이 났을 때, 길이가 L인 테이프로 구멍을 막으려고 한다. 사용해야 하는 테이프의 최소 개수를 구하는 문제다. 문제 풀이 과정 왼쪽에서부터 테이프를 붙여가며 개수를 센다. 현재 상태에서 테이프를 붙여야 하는지 아닌지를 판단해서 붙이기 때문에 그리디 알고리즘이다. 코드 import sys def get_min_tapes(): glob.. 2021. 7. 18. 이전 1 ··· 34 35 36 37 38 39 40 41 다음 반응형
