백준
-
[백준] Java - 줄 세우기메모/알고리즘 2022. 6. 1. 23:52
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 백준의 위상정렬 문제 줄 세우기의 자바 풀이다. 위와 같이 순서가 정해져 있고 사이클이 없는 그래프를 정렬하는 알고리즘이 위상정렬이다. "진입 차수"와 "인접 리스트"를 통해서 문제를 해결할 수 있었다. 위의 그림에서 6을 보면 4와 5로부터 진입하는 것을 볼 수 있다. 2개의 노드가 6으로 진입하므로 진입 차수는 2이다. 반대로 1이나 2는 진입차수가 0이다. 인접리스트를 통해 연결된 다음 노드를 저장하고 진입차수가 ..
-
[백준] Python - 알파벳메모/알고리즘 2022. 4. 13. 10:41
1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백준의 그래프 탐색 문제 알파벳이다. 이 문제는 DFS와 BFS 두 가지 방법으로 접근했다. DFS 같은 경우는 재귀를 사용하여 visited 집합에 방문 여부를 저장하는 방식을 사용했다. DFS와 BFS가 모두 인접 행렬/인접 리스트 각각에서 시간 복잡도가 같은 걸로 알고 있는데 DFS 방식은 PyPy3로 해결할 수 있었고 Python3로는 시간초과가 발생했다. BFS를 사용한 방식은 조금의 변형이 있었다. 일반적으로 우리는 FloodFill과 같은 알..
-
[백준] Python - 바이러스메모/알고리즘 2022. 4. 11. 23:29
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 백준의 그래프 문제 바이러스다. 1번 PC와 네트워크로 연결된 PC들이 주어지고 1번을 제외한 바이러스로 감염시킬 수 있는 PC의 수를 세는 문제이다. DFS나 Union-Find를 사용하면 풀 수 있을 것이라 생각했고 DFS를 사용해서 풀 수 있었다. for i in range(1, c+1): #다음 이동할 컴퓨터 if G[v][i] and visited[i] == 0: # 네트워크 연결이 되어 있는지, 방문한 적이 있는지 visited[i] = 1 infect +..
-
[백준] Python - 안전 영역메모/알고리즘 2022. 3. 25. 15:25
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 음식물 피하기와 마찬가지로 Flood Fill 알고리즘을 알아보고자 푼 문제다. 똑같이 별 다를 건 없고 BFS를 통해 해결했다. 이 문제의 경우 한 가지를 고려해야한다. 바로 강수량이다. 처음에 지역의 높이를 입력하면서 동시에 가장 높은 지역을 확인한다. 가장 높은 지역만큼 비가 온다면 그 높이를 초과하는 강수량은 확인할 필요가 없다. 따라서 비가 안오는 경우인 0부터 가장 높은 높이 -1 까지의 강수량을 가정하고 문제를 푼다. 예를 들어 가장 높은 곳의 높이가 9라..
-
[백준] Python - 친구 네트워크메모/알고리즘 2022. 3. 25. 15:20
4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net Union-Find를 사용하는 분리집합 문제이다. 항상 보면 BFS/DFS 같은 문제나 분리 집합 문제들은 기본적인 형태가 유사한 것 같다. 다만 이 문제는 한가지 고려 사항이 있다. 친구 관계가 입력으로 주어지는데 이 친구들의 이름이 문자열로 입력된다. 여기서 나는 두 가지를 고려했다. 1. 부모 노드를 배열이 아닌 딕셔너리로 저장할 것 2. 이름을 정수로 매핑할 딕셔너리를 새로 생성할 것 부모 노드를 문자열 딕셔너리를 통해서만 확인하면 시간초과가 ..