문제https://school.programmers.co.kr/learn/courses/30/lessons/81302 사용 알고리즘DFS 풀이고려사항1. 현재 사람의 위치에서 맨해튼 거리가 2 이내 사람 존재 여부- O(빈 책상)인 경우 계속 탐색- X(파티션)는 갈 수 없음 후기1. 이 문제의 keypoint는 재귀 관리이다.재귀의 경우 하위 호출에서 결과가 나왔더라도다시 빠져나오는 과정 중에 상위 호출에서 다시 값이 갱신 될 수 있기 때문에 처리에 주의가 필요하다.재귀, DFS에서는 매번 이 과정이 까다롭다. 2. 이번 문제 역시 맨해튼 거리가 2이기 때문에 깊이가 깊진  않지만 그래도 재귀 방식이기 때문에 2번째 깊이에서 나온 결과가 빠져나오면서 첫번째 깊이에서초기화 되는 것을 방지하기 위해 시간이..

문제https://www.acmicpc.net/problem/4195 사용 알고리즘Union-Find 풀이고려사항1. 친구 리스트에 존재 여부2. 친구 연결 후기1. 이 문제의 keypoint는 union-find를 딕셔너리를 통해 진행하는 것이다.보통은 숫자로 진행했지만, 이 문제의 경우 문자열로 받기 때문에 딕셔너리를 통해 진행했다. 2. 우선 친구 딕셔너리(parents)에 존재 여부를 확인 후 존재하지 않는다면root를 자신으로 친구 딕셔너리에 등록, size 딕셔너리에 1로 세팅한다. 3. 이후 기존 union-find 알고리즘을 진행한다.- 현재 분리 집합의 root를 find 함수를 통해 구해준 후- 서로 같은 집합이 아닐 경우 union을 통해 서로 분리 집합을 합쳐준다.4. 이때 실시간으..

문제https://www.acmicpc.net/problem/1043 사용 알고리즘Union-Find 풀이고려사항1. 해당 파티에 진실을 아는 사람이 존재하는지- 기존 진실을 아는 사람- 기존 진실을 아는 사람이 참여한 파티에 참여한 사람들 후기1. 이 문제의 keypoint는 리스트 형태를 Union-Find 진행하는 것이다.이런 형태는 기준이 있으면 좋겠다고 판단했다.때문에 기준(root)을 진실을 알고있는 가장 첫번째 사람으로 정하고 시작했다. 2. 진실을 알고 있는 사람이 0명일 경우 모든 파티에서 거짓말을 할 수 있다.하지만, 1명 이상일 경우 Union-Find를 시작한다.3. 우선 진실을 알고 있는 사람들을 하나의 집합으로 묶는다.이때 위의 기준을 정한대로 가장 첫번째 사람을 기준으로 나머지..

문제https://www.acmicpc.net/problem/24542 사용 알고리즘Union-Find 풀이고려사항1. 분리 집합 만들기- 중간에 root가 변경 될 수 있기 때문에 다 만들고 최종 갱신 필요2. 집합 별 인원 수 확인 후기1. 이 문제는 Union-Find의 가장 기초 문제로 생각된다.2. 부모(root) 리스트를 만들어주고 배열 합칠 때 성능 향상을 위한 size 리스트를 만들어준다.3. 이후 M개의 숫자 쌍을 입력받으면- Find : 부모를 확인하여 같은 집합인지 확인 후- Union : 같은 집합이 아닐 경우 서로 집합을 합치며 부모를 갱신한다.- 이때 작은 집합을 큰 집합에 합침으로  집합 간의 균형을 맞추고 트리의 높이를 최소화하여 성능을 향상시킨다. 4. 이후 경우의 수는 해..

문제https://www.acmicpc.net/problem/13414 사용 알고리즘구현 풀이고려사항1. 이미 수강신청 대기에 있는 학생인지 후기1. 처음에는 리스트를 만들어 remove와 append로 관리하였다.현재 수강신청을 누른 학생이 이미 이전에 누른 이력이 있다면 리스트에서 제거 후다시 맨 뒤에 넣어주는 방식을 선택했다.2. 하지만 이 방식은 시간초과가 발생하였다.- 학생이 있는지 확인하는 작업: 최악의 경우 O(N)- 학생을 제거하는 작업: 최악의 경우 O(N)- 학생을 추가하는 작업: O(1)-> 따라서 전체 시간 복잡도는 O(N**2) 3. 때문에 딕셔너리를 활용한 방식으로 변경하였다.딕셔너리를 들어온 순서로 갱신해주고value를 기준으로 정렬 후 K개를 뽑아주는 방식을 선택하였다.이때,..

알고리즘 개념유니온 파인드(Union-Find) 알고리즘은 분리 집합을 관리하는 알고리즘으로그래프 형태의 자료들의 연결 정보를 알고 싶을 때 사용된다.이 알고리즘의 핵심 목표는 합치기(Union)와 찾기(Find) 작업을 효율적으로 수행하는 것이다.주로 그래프에서 연결된 컴포넌트 관리 나 사이클 검출에 활용된다.    - 집합 소속 여부 판단 & 사이클 검출 : 임의의 두 노드의 연결 여부(집합 소속 여부) 확인        - 단, 무방향 그래프에서만 적용 가    - 경로 압축 : 그래프 내 노드 간의 경로 최적화  위의 경우 3과 5가 같은 그룹인지 알려면왼쪽의 경우 자신의 부모만 기록되어 있으므로 연결여부 확인이 따로 필요하다.이때 재귀 호출을 통해 루트 노드를 찾을 때 탐색 시간이 소요된다.un..