본문 바로가기

그래프17

[Python] 백준 14502번 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 그래프 탐색 + 브루트 포스 문제이다. 벽을 단 3개만 설치해서 얻을 수 있는 최선의 경우를 찾아야 한다. 완전 탐색을 통해서 3개를 설치했을 때 발생하는 모든 경우를 따지고, bfs를 사용해서 주어진 경우를 따져서 안전 구역의 개수를 따져주면 된다. 주의해야 할 점은 깊은 복사를 사용하지 않으면 원본이 훼손된다는 점이다! ✔️ 느낀 점 이렇게 따지는 경우를 어떻게 해야 할지 몰랐는데 단순하게 .. 2023. 2. 22.
[Python] 소프티어 : 이미지 프로세싱 https://softeer.ai/practice/info.do?idx=1&eid=627&sw_prbl_sbms_sn=156768 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 아주 가벼운 그래프 탐색 문제이다 (BFS) BFS로 풀었고 DFS도 가능하다. ✔️ 느낀 점 많이 그래프 탐색을 풀어봤다면 어렵지 않은 문제이다. 💻 코드 import sys input = sys.stdin.readline moves = [(1,0), (0,1), (-1,0), (0,-1)] h, w = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(h)] q = int(inpu.. 2023. 2. 20.
[Python] 백준 1446번 : 지름길 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 💡 문제 풀이 다익스트라 문제이다. 그리디로도 풀 수 있을 것 같다. 다익스트라 알고리즘을 구현할 줄 알고, 알고리즘을 적용할 노드를 어떻게 설정할지 고민해야 한다. 일반적인 문제와 다르게 특정 노드가 주어지지 않아 고속도로의 길이만큼 노드가 주어졌다고 생각해야 한다. ✔️ 느낀 점 오랜만에 다익스트라 문제를 풀어보기 위해서 쉬운 문제로 갔는데 생각보다 쉽게 접근이 되지 않았다. 파이썬.. 2023. 1. 31.
[Python] 프로그래머스 : 게임 맵 최단거리 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 가벼운 BFS 문제이다. 최단거리를 따져야 하므로 생각할 것이 많다. 나는 이동할 수 있는 위치에 이동했을 때 최솟값을 넣어주는 방식으로 구현했다. 그리고 상대의 위치는 항상 끝에 있으므로 따로 계산안하고 넘겨주었다. ✔️ 느낀 점 오랜만에 시작한 알고리즘이라서 파이썬 문법에 익숙하지 못하다는게 느껴졌다. 문법에 대한 기억을 되살리는 것이 좋아보이고 새로운 것을 공부하기보단 공부한 것.. 2023. 1. 29.
[Python] 백준 1197번 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 💡 문제 풀이 최소 신장 트리 문제이다. 크루스칼로 해결했다. 가장 기본적인 문제로 알고리즘의 개념만 잘 숙지하고 있다면 해결할 수 있다. ✔️ 느낀 점 다음에는 크루스칼 외에 프림 알고리즘으로도 풀어봐야겠다. 💻 코드 import sys input = sys.stdin.readline V, E = map(int, input().split()) edg.. 2022. 9. 4.
[Python] 백준 2458번 : 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 💡 문제 풀이 플로이드-워샬 알고리즘 문제이다. 특정 경로로 이동할 수 있는지 여부를 플로이드-워샬로 처리하고 값을 따진다. 여기서 자기 키 순서는 (자기보다 작은 사람 수 + 자기보다 큰 사람 수) == N-1 이면 알 수 있다. 예를 들어서, 6명이 있다면 작은 사람이 3명, 큰 사람이 2명 있다면 자기 키 순서는 3등이라는 것을 알 수 있다. ✔️ 느낀 점 안 좋아하는 유형의 문제라서 30분을.. 2022. 9. 2.

티스토리툴바