문제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..

문제https://www.acmicpc.net/problem/16724 사용 알고리즘DFS 풀이고려사항1. 현재 지나고 있는 경로의 상태- 아직 방문한 적이 없는 곳인지- 지금 현재 만들고 있는 경로에 있는지- 이전에 safe zone으로 갈 수 있는 곳으로 판명한 곳인지 후기1. 이 문제의 keypoint는 사이클을 추적하는 것이다.갈 수 있는 방향이 한 개로 한정되어 있으며, 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.이러한 조건들로 인해 풀이가 간단해졌다. 2. 방문하지 않은 곳만 DFS를 시작하였다.2-1) visited[ci][cj] == 0 인 경우방문하지 않은 곳이기 때문에 진행 중인 경로로 1로 설정하고 스택에 넣어준다.이후 방향에 따라 이동을 진행한다.2-2) visited[ci]..

문제https://www.acmicpc.net/problem/20057 사용 알고리즘구현, 시뮬레이션 풀이고려사항1. 반시계 방향으로 이동2.방향전환 시 날라가는 모래 percentage 변화3. 다른 칸으로 이동한 모래양, 밖으로 버려지는 모래양, 알파 값으로 이동할 모래 양 후기1. 토네이도 방향전환은 기준(N // 2, N // 2)부터 시작한다.방향을 제공하며 step을 확인하며 방향 변화 여부를 확인하고, flag를 확인하며 step의 수를 늘린다.우선 가야하는 step은 방향전환 2번마다 1씩 증가한다.때문에 Flag를 두어 방향 전환 시마다 토글 형식으로 변경하고 확인하였다.이전에 달팽이 문제를 풀어보아 동일한 방식으로 접근하였다.하지만 달팽이에 더 좋은 풀이가 있었는데 그 방식은 사용하지 ..