메모/알고리즘
-
[백준] 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. 4. 1. 00:40
코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 정렬을 이용하는 문제다. 최소 힙을 사용해서 지속적으로 최소값 2개를 빼오고 그 결과를 다시 넣는 형태로 구현했다. 여기까지의 구현은 정말 누구나 생각할 수 있고 쉬운 난이도인데 -1을 출력하는 조건에서 살짝 고민을 했다. K 이상의 맵기를 만들 수 없는 상황이면 2개의 최소값을 뽑아 올 수 없는 상황이라고 생각하고 여러 번 조건을 바꿔봐도 마지막 TC에서 오답처리 되길래 다른 사람의 코드를 보니 Index Error로 예외처리를 해주는 것을 확인했..
-
[백준] 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. 이름을 정수로 매핑할 딕셔너리를 새로 생성할 것 부모 노드를 문자열 딕셔너리를 통해서만 확인하면 시간초과가 ..
-
[백준] Python - 여행 가자메모/알고리즘 2022. 3. 25. 15:15
1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Union-Find를 쓸 수 있는 기본적인 분리 집합 문제이다. 여행을 가려는 사람은 왔던 도시를 다시 거칠 수 있고 입력의 마지막으로 주어진 모든 도시를 갈 수만 있으면 된다. 기본적인 Union-Find를 사용하여 부모 노드를 연결하고 같은 부모를 가진 집합이라면 서로 연결되었다고 볼 수 있다. GitHub - Floodnut/algorithm: 알고리즘 풀이 모음 알고리즘 풀이 모음. Contribute to Floodnut/algorithm develop..