백준
-
[백준] Python - 여행 가자메모/알고리즘 2022. 3. 25. 15:15
1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Union-Find를 쓸 수 있는 기본적인 분리 집합 문제이다. 여행을 가려는 사람은 왔던 도시를 다시 거칠 수 있고 입력의 마지막으로 주어진 모든 도시를 갈 수만 있으면 된다. 기본적인 Union-Find를 사용하여 부모 노드를 연결하고 같은 부모를 가진 집합이라면 서로 연결되었다고 볼 수 있다. GitHub - Floodnut/algorithm: 알고리즘 풀이 모음 알고리즘 풀이 모음. Contribute to Floodnut/algorithm develop..
-
[백준] Python - 음식물 피하기메모/알고리즘 2022. 3. 25. 15:11
1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net FloodFill 알고리즘을 공부해보려고 문제 몇 개를 풀기로 했다. 새로운 알고리즘은 아니고 기존의 DFS/BFS 등을 통해서 풀 수 있는 쉬운 문제였다. 2차원 배열을 생성해서 각 좌표 별 정보를 저장한다. 현재 좌표 기준으로 상하좌우 좌표 중 2차원 배열의 범위 내에 있으면서 음식물이 존재한다면 한 덩어리로 간주하고 Deque에 추가한다. 기존의 BFS를 해결할 수 있는 방법을 통해서 가장 큰 덩어리의 사이즈를 구하..
-
[백준] Python - 집합의 표현메모/알고리즘 2022. 3. 24. 13:10
1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net DisJoint Set과 Union-Find에 대해 공부하기 위해서 새로 문제를 선택했다. DisJoint Set은 서로소 집합 또는 분리 집합이라고 한다. 자식이 자신의 부모를 가리키는 형태로 존재하고 집합 간의 교집합은 존재하지 않는다. 이 문제의 경우 Union과 Find를 구현하는 기본적인 문제이다. 입력으로 주어진 값에 따라 합집합을 수행할 것인지 값을 찾을 것인지 선택한다. Union의 경우 합치려는 두 대상의..
-
[백준] Python - 카드메모/알고리즘 2022. 1. 29. 23:59
11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 이전 포스팅의 포켓몬 마스터 이다솜, 듣보잡과 함께 정말 쉬웠던 문제 중에 하나다. 솔직히 말하면 이 정도 난이도로는 연습은 별로... defaultdict를 활용해서 정수 값을 저장했다. 다음엔 다른 문제를 풀어봐야겠다.
-
[백준] Python - 나는야 포켓몬 마스터 이다솜메모/알고리즘 2022. 1. 29. 23:57
1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이를 안적어도 될 정도로 너무 쉬웠다... defaultdict를 활용하여 포켓몬 마다의 값을 저장했다. GitHub - Floodnut/Algorithm: 알고리즘 풀이 모음 알고리즘 풀이 모음. Contribute to Floodnut/Algorithm development by creating an account on GitHub. github.com