Beelog

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제는 위와 같으며, dfs를 통해 문제를 해결하였습니다. 모든 컴퓨터가 연결되어 있는지 한번씩은 확인을 해야하므로 이를 확인할 수 있는 boolean 타입의 배열을 생성합니다. 이 배열을 순서대로 반복하면서 해당 위치의 컴퓨터를 아직 방문하지 않은 경우 dfs를 통해 연결된 모든 컴퓨터를 방문처리합니다. 그러고 나면 하나의 네트워크를 확인한 것이므로 answer를 증가..

www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제는 위와 같으며, DFS 를 통해 연관된 동영상들의 유사도를 확인하여 K보다 크거나 같은 경우 방문한 것으로 표시하고 그 수를 출력하는 방식으로 문제를 해결하였습니다. 먼저 예시로 주어진 동영상들의 연관 관계를 그래프로 나타내면 다음과 같습니다. 이후 주어지는 Q 질문과 결과를 하나씩 살펴보면 다음과 같습니다. 1. 유사도가 1 이상인 동영상이 추천될 때,..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제는 위와 같으며, BFS 를 통해 문제를 풀 수 있습니다. 먼저 이 문제는 BFS 를 수행하는데 연결이 끝나려면 최종적으로는 사이클이 만들어져야 한다는 것입니다. 1 => 3 => 3 2 => 1 => 3 => 3 3 => 3 4 => 7 => 6 => 4 5 => 3 => 3 또한, 이미 1부터 시작하여 3을 확인하고 3이 사이클을 이룬다는 것을 확인한 뒤에는 2를 확인한 경우도 1까지 확인한 경우와 뒷부분 사..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제는 위와 같으며, DFS 방식을 통해 같은 색으로 연관된 구역을 찾아 그 수를 세는 방식으로 문제를 해결하였습니다. 적록색약인 경우와 아닌 경우가 있으므로, DFS 를 두번 처리하는 방식으로 문제를 해결하였습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 적록색약이 아닌 경우 같은 색으로 칠해진 구역..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제는 위와 같으며, 지도의 정보를 이차원 배열로 저장하고 각 섬을 방문한 적이 있는지 확인하는 이차원 배열을 만든 후, 기본적인 DFS 를 통해 연결된 땅을 모두 방문처리하고 나서 섬의 개수를 증가시키는 방식으로 섬이 몇개인지 확인할 수 있습니다. 파이썬 코드는 다음과 같습니다. import sys sys.setrecursionlimit(10000) # 재귀함수 범위 제한 수정 # 상하좌우, 대각선까지 ..