분류 전체보기
-
[백준] 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..
-
[백준] 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의 경우 합치려는 두 대상의..
-
13기 SW 마에스트로 1, 2차 코딩테스트 후기메모/기록하기 2022. 3. 19. 16:34
12기 때 지원했을 때는 하필 1차 코딩테스트 날 다른 일이 겹쳐서 아쉽게도 제대로 코테를 치지 못했다. 이번에는 제대로 한번 해보고자 백준, 프로그래머스에서 계속 문제를 풀어보면서 준비를 했다. 웹은 아예 포기했다. 솔직히 어떻게 나올지도 몰랐고 뭘 준비해야할지도 몰라서 알고리즘하고 SQL 만 준비하기로 했다. 1차는 정말 쉬웠던 것 같다. 물론 못 푼 문제도 있었지만 내가 그냥 풀이를 몰라서 못풀었다는 느낌이 강했다. 어떤 유형인지 바로 캐치 했다면 누구나 풀었을 것 같다. 뭐 그래도 1차는 약간 반신반의 하긴 했지만 무난하게 통과한 것 같다. 오늘, 2차를 치면서 시간이 조금 부족했다고 느껴졌다. 워낙 알고리즘에 약한 나이기도 하고... 전에 본 문제가 나와서 금방 풀 줄 알았는데 어떻게 풀지는 다..