문제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개를 뽑아주는 방식을 선택하였다.이때,..

문제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를 두어 방향 전환 시마다 토글 형식으로 변경하고 확인하였다.이전에 달팽이 문제를 풀어보아 동일한 방식으로 접근하였다.하지만 달팽이에 더 좋은 풀이가 있었는데 그 방식은 사용하지 ..

문제https://www.acmicpc.net/problem/24444 사용 알고리즘BFS 풀이고려사항1. 양방향 그래프2. 각 노드에서 다음 갈 수 있는 노드 오름차순으로 방문 후기1. 가장 기본적인 BFS 알고리즘에 정렬만 들어간 문제이다.2. 그래프를 만들때 인덱스가 헷갈리지 않게 V+1으로 초기 세팅하여 각 수와 인덱스 번호를 맞췄다.3. deque와 visited를 활용하여 기본 BFS를 진행하였다. 코드import sysfrom collections import dequeinput = sys.stdin.readlineV, E, S = map(int, input().split())gp = [[] for _ in range(V + 1)]# 그래프 초기 세팅for _ in range(E): s..

문제https://school.programmers.co.kr/learn/courses/30/lessons/64062 사용 알고리즘이분탐색 풀이고려사항1. 기준이 되는 수보다 같거나 작은 수의 연속 갯수2. 기준을 이진탐색으로 탐색 후기1. 이 문제의 keypoint는 시간관리이다. 2. 처음 슬라이싱을 활용하여 for문으로 문제를 접근하였다.엄청 단순하고 빨리 풀었지만, 효율성 테스트에서 모두 시간초과가 발생하였다.주어진 조건의 범위를 보고 이진탐색도 생각하였지만,이진탐색보다 슬라이싱을 먼저 선택한 이유는이진탐색은 매번 배열을 확인하여 시간 관리 측면에서 좋지 않을 것이라고 생각했다.이는 for문에서의 시간 복잡도만 생각하고 슬라이싱하여 max를 구하는 시간을 고려하지 않아서이다.max를 하는 경우 O..