기록

문제 보기 [사용한 알고리즘] - 정렬 [알고리즘] - 내부 라이브러리 sort, set 사용 [코드] import sys if __name__ == "__main__": n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) # 중복 제거 arr = list(set(arr)) # 정렬 arr.sort() print(" ".join(map(str, arr)))

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색), 브루트 포스 [알고리즘] 1. BFS 알고리즘을 사용하여 평면상에 존재하는 모든 섬에 해당하는 좌표를 구합니다. - island[0] : 0번 섬에 해당하는 좌표값 저장 2. 각 섬들 사이에 발생할 수 있는 모든 거리를 탐색하여 최소 거리 값을 구합니다. 3. 최소 거리 값 - 1을 출력합니다. [코드] from collections import deque import sys dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(start): q = deque() result = list() q.append((start[0], start[1])) result.append((start[0], start[1])) maps[..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. 로봇의 현재 위치와 바라보는 방향을 큐에 삽입합니다. 2. 현재 위치와 바라보는 방향을 기준으로 명령 1(Go k)을 수행합니다. - 1, 2, 3칸 이동이 가능한지 확인하고 이동이 가능하다면 이동한 위치와 현재 방향을 큐에 삽입합니다. 3. 현재 위치와 바라보는 방향을 기준으로 명령 2(Turn dir)를 수행합니다. - 동, 서, 남, 북 중 현재 방향을 제외한 방향 중 방문하지 않은 곳이 있다면 방향을 바꾼 후 큐에 삽입합니다. 4. 위 과정을 도착 지점을 찾을 때까지 수행합니다. [코드] from collections import deque import sys dx = [None, 0, 0, 1, -1] dy = [None,..

문제 보기 [사용한 알고리즘] 플로이드-워셜(Floyld-Warshall) [알고리즘] 1. 입력값을 이용해 무방향 그래프를 구현합니다. 2. 플로이드-워셜 알고리즘을 통해 각 회원들이 모든 회원가 친구가 되기 위한 최소 단계를 구합니다. 3. 각 회원 중 모든 회원가 친구가 되기 위한 최소 점수를 가진 회원들을 찾습니다. 4. 회장 후보의 점수와 후보의 수를 출력하고, 다음 줄에 회장 후보를 오름차순으로 모두 출력합니다. [코드] import sys INF = 1e10 if __name__ == "__main__": n = int(sys.stdin.readline()) graph = [[INF for _ in range(n + 1)] for _ in range(n + 1)] for i in range(..

문제 보기 [사용한 알고리즘] 위상 정렬(Topological) [알고리즘] 1. 선행 관계가 없는 작업을 큐에 삽입합니다. 2. 큐에 있는 원소를 하나씩 꺼내어 연결된 선행 관계를 제거합니다. - 선행 관계를 제거한 결과 해당 작업이 더 이상 선행 관계가 없으면 큐에 삽입합니다. - 최대 시간 저장 배열에 저장된 시간과 현재까지 사용한 시간 중 최댓값을 저장합니다. 3. 모든 선행 관계가 사라질 때까지 위 과정을 반복합니다. ※ 최대 시간 저장 배열을 따로 두는 이유 예를 들어 3번 작업이 1번, 2번 작업과 선행 관계가 있을 때 1번 + 3번, 1번 + 2번 작업 중 최댓값이 3번 작업 처리 시간입니다. 만약 최대 시간 저장 배열을 따로 두지 않으면 가장 마지막에 계산한 값이 최종 시간이 되기 때문에..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. 빨간 구슬과 파란색 구슬의 위치를 찾습니다. 2. 현재 구슬 위치에서 상, 하, 좌, 우로 움직일 수 있는 모든 상황을 탐색합니다. - 파란색이 구멍에 빠지는 경우 무시합니다. - 빨간색만 구멍에 빠지면 1을 리턴합니다. - 모두 구멍에 빠지지 않으면 움직인 위치를 큐에 삽입하여 계속 탐색할 수 있도록 합니다. 3. 위 과정을 10번 이하로 움직일 때까지 반복합니다. [코드] from collections import deque import sys dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(red_x, red_y, blue_x, blue_y): q = deque() q.append((red_x..

문제 보기 [사용한 알고리즘] 다익스트라, 이분 탐색 [알고리즘] 알고리즘 전체 과정을 대략적으로 말씀드리면 이분 탐색을 통해 케이블 기준 가격을 정한 후 다익스트라를 수행함으로써 1번과 N번 컴퓨터를 이을 수 있는지 판단합니다. 세부적인 과정은 다음과 같습니다. 1. 이분 탐색을 수행하기 위해 left, right 값을 0과 1000001로 초기화합니다. 2. left와 right를 통해 mid 값을 구한 후 다익스트라를 수행합니다. 3. 다익스트라 수행은 기존의 다익스트라와 달리 최소 거리를 구하는 것이 아니라 1번과 N번을 연결할 수 있는지 구하는 것이 핵심입니다. 따라서 거리 값은 mid 값을 넘긴 케이블의 수입니다. - 만약 distance[n] 값이 k보다 크면 공짜로 제공하는 케이블선 k개로..

문제 보기 [사용한 알고리즘] 다이나믹 프로그래밍 [알고리즘] 1. 체크 포인트 사이의 거리를 구하여 distance 2차원 배열에 저장합니다. - distance[i][j] : i번째 체크포인트와 j번째 체크포인트 사이의 거리입니다. 2. dp 2차원 배열을 INF(=1e10) 값으로 초기화합니다. - dp[k][n] : 체크포인트를 최대 k개 건너뛸 수 있는 상황에서 n번째 체크포인트까지 달릴 수 있는 최소거리입니다. 3. 3차원 반복문을 통해서 dp 배열을 채워나갑니다. - k값이 1일 때부터 순차적으로 dp 배열을 채워나갑니다. - 현재 체크포인트까지 달릴 수 있는 최소거리는 k값을 적게 사용한 곳에서 현재 위치로 이동한 거리와 동일하게 k값을 사용한 곳에서 현재 위치로 이동한 거리를 비교하여 최..

문제 보기 [사용한 알고리즘] 정렬, 구현 [알고리즘] 1. 공을 크기 순으로 오름차순 정렬합니다. 2. 0번 인덱스 공부터 순차적으로 탐색합니다. - 현재 인덱스까지 공 무게의 총합을 total 변수에 저장합니다. - 각 색깔별로 공 무게 누적합을 ball_size_sum 딕셔너리에 저장합니다. - 현재 인덱스까지 공 무게 총합 - 현재 색깔 공 무게 누적합은 현재 인덱스 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합입니다. ※ 단순한 2중 for문으로 구현하면 n이 200,000으로 큰 수이기 때문에 시간 초과가 발생합니다. 따라서 안쪽의 for문의 횟수를 줄이기 위해 바깥쪽 for문의 인덱스를 순차적으로 증가시키면서 안쪽의 for문은 while문으로 변경하여 불필요한 반복은 수행하지 않도록 구..

문제 보기 [사용한 알고리즘] Union-Find [알고리즘] 1. 친구의 친구는 친구이기 때문에 서로 친구들인 모임을 Union-Find를 이용해서 찾습니다. 2. 해당 모임에서 친구 비용이 가장 작은 학생을 친구로 만듭니다. 3. 위 과정을 모든 학생과 친구를 맺을 때까지 반복합니다. 4. 모든 학생과 친구를 맺는 비용이 현재 가지고 있는 비용보다 적으면 친구로 만드는데 드는 최소비용을 출력합니다. 만약 현재 가지고 있는 비용이 모든 학생과 친구를 맺는 비용보다 적다면 Oh no를 출력합니다. [코드] import sys def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return pare..