[PG/Python] 거리두기 확인하기
📌 문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 📌 문제 접근 방법 각 대기실마다 함수를 사용하여 거리두기가 잘 되어있는 지 확인..
2022. 1. 8.
[PG/Python] 가장 먼 노드
📌 문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 📌 문제 접근 방법 인접 리스트를 활용해서 그래프 정보를 저장해준 뒤 bfs를 사용했다. bfs에서 방문체크를 할 때, 1번 노드와의 거리를 저장해줬다. (가장 먼 거리가 1일 경우에도 1번 노드는 포함되지 않아야하므로 1번 노드는 -1로 방문체크를 해줬다.) bfs 탐색이 끝난 후, visited를 순회하면서 거리가 가장 먼 노드의 개수를 세어 반환한다. 📌 코드 from collections import deque de..
2021. 12. 9.
[PG/Python] 전력망을 둘로 나누기
📌 문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 📌 문제 접근 방법 인접리스트를 활용해서 연결된 전선 정보를 입력해준다. wires를 한 번 더 반복문을 돌리면서 전선들 중 하나를 끊는다. 이 때 끊긴 두 송전탑을 기준으로 전력망이 가진 송전탑의 개수를 bfs를 활용해서 구해준다. 두 전력망의 송전탑 수와 현재의 answer에 저장된 값을 비교하여 더 작은 값으로 answer 값을 갱신해준다. 끊긴 두..
2021. 11. 14.
[Algorithm] 그래프
그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 ..
2021. 10. 20.